#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Mon May 13 15:48:30 2019@author: lg """class Node():#節(jié)點類def __init__(self,data = -1):self.data = dataself.left = Noneself.right = None class Tree():#樹類def __init__(self):self.root = Node()def add(self,data):# 為樹加入節(jié)點node = Node(data)if self.root.data == -1: #如果樹為空，就對根節(jié)點賦值self.root = nodeelse:myQueue = []treeNode = self.rootmyQueue.append(treeNode)while myQueue: #對已有的節(jié)點進行層次遍歷treeNode = myQueue.pop(0)if not treeNode.left:treeNode.left = nodereturnelif not treeNode.right:treeNode.right = nodereturnelse:myQueue.append(treeNode.left)myQueue.append(treeNode.right)def pre_order_recursion(self,root): #遞歸實現(xiàn)前序遍歷if not root:returnprint( root.data,)self.pre_order_recursion(root.left)self.pre_order_recursion(root.right)def pre_order_stack(self,root): #堆棧實現(xiàn)前序遍歷（非遞歸）if not root:returnmyStack = []node = rootwhile myStack or node:while node: #從根節(jié)點開始，一直尋找他的左子樹print (node.data,)myStack.append(node)node = node.leftnode = myStack.pop() #while結(jié)束表示當(dāng)前節(jié)點node為空，即前一個節(jié)點沒有左子樹了node = node.right #開始查看它的右子樹def in_order_recursion(self,root): #遞歸實現(xiàn)中序遍歷if not root:returnself.in_order_recursion(root.left)print( root.data,)self.in_order_recursion(root.right)def in_order_stack(self,root): #堆棧實現(xiàn)中序遍歷（非遞歸）if not root:returnmyStack = []node = rootwhile myStack or node: #從根節(jié)點開始，一直尋找它的左子樹while node:myStack.append(node)node = node.leftnode = myStack.pop()print(node.data,)node = node.rightdef post_order_recursion(self,root): #遞歸實現(xiàn)后序遍歷if not root:returnself.post_order_recursion(root.left)self.post_order_recursion(root.right)print( root.data,)def post_order_stack(self, root): # 堆棧實現(xiàn)后序遍歷（非遞歸）# 先遍歷根節(jié)點，再遍歷右子樹，最后是左子樹，這樣就可以轉(zhuǎn)化為和先序遍歷一個類型了，最后只把遍歷結(jié)果逆序輸出就OK了。if not root:returnmyStack1 = []myStack2 = []node = rootwhile myStack1 or node:while node:myStack2.append(node)myStack1.append(node)node = node.rightnode = myStack1.pop()node = node.leftwhile myStack2:print( myStack2.pop().data,)def level_order_queue(self,root): #隊列實現(xiàn)層次遍歷（非遞歸）if not root :returnmyQueue = []node = rootmyQueue.append(node)while myQueue:node = myQueue.pop(0)print( node.data,)if node.left:myQueue.append(node.left)if node.right:myQueue.append(node.right)if __name__ == '__main__':#主函數(shù)datas = [2,3,4,5,6,7,8,9]tree = Tree() #新建一個樹對象for data in datas:tree.add(data) #逐個加入樹的節(jié)點print ('遞歸實現(xiàn)前序遍歷：')tree.pre_order_recursion(tree.root)print( '\n堆棧實現(xiàn)前序遍歷')tree.pre_order_stack(tree.root)print ("\n\n遞歸實現(xiàn)中序遍歷：")tree.in_order_recursion(tree.root)print ("\n堆棧實現(xiàn)中序遍歷：")tree.in_order_stack(tree.root)print ('\n\n遞歸實現(xiàn)后序遍歷：')tree.post_order_recursion(tree.root)print('\n堆棧實現(xiàn)后序遍歷：')tree.post_order_stack(tree.root)print('\n\n隊列實現(xiàn)層次遍歷：')tree.level_order_queue(tree.root)

總結(jié)

以上是生活随笔為你收集整理的python 二叉树遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。