本文結合實例介紹了二叉樹和遍歷方法在Python中的實現。分享給妳，供妳參考，如下:
簡介:
樹是壹種非常重要的數據結構，主要用來提高搜索效率，比較適合重復搜索，比如二叉排序樹和FP- tree。另外還可以用來提高編碼效率，比如哈弗曼樹。
代碼:
用Python實現樹的構造和幾種遍歷算法並不難，但代碼是總結的。實現功能:
①樹的結構
(2)遞歸實現壹階遍歷、中階遍歷和末階遍歷。
(3)棧實現了壹階遍歷、中階遍歷和後序遍歷。
④隊列實現分層遍歷。
#編碼=utf-8
類節點(對象):
" ""節點類" " "
def init(self，elem=-1，lchild=None，rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
類別樹(對象):
" ""樹類" " "
定義初始化(自身):
self.root = Node()
self.myQueue = []
定義添加(self，elem):
" ""向樹中添加節點" " "
節點=節點(元素)
If self.root.elem == -1: #如果樹是空的，給根節點賦值。
self.root = node
self.myQueue.append(self.root)
否則:
TreeNode = self.myQueue[0] #此節點的子樹不是偶數。
如果treeNode.lchild == None:
treeNode.lchild = node
self . my queue . append(treenode . l child)
否則:
treeNode.rchild = node
self . my queue . append(treenode . rchild)
Self.myQueue.pop(0) #如果節點有右子樹，則丟棄該節點。
def front_digui(self，root):
" ""用遞歸實現樹的優先遍歷" " "
如果root == None:
返回
打印root.elem，
self.front_digui(root.lchild)
self . front _ di GUI(root . r chid)
def middle_digui(self，root):
" ""用遞歸實現樹的中序遍歷" " "
如果root == None:
返回
self.middle_digui(root.lchild)
打印root.elem，
self . middle _ di GUI(root . r chid)
def later_digui(self，root):
" ""用遞歸實現樹的後序遍歷" " "
如果root == None:
返回
self.later_digui(root.lchild)
self . later _ di GUI(root . r chid)
打印root.elem，
def front_stack(self，root):
" ""用棧實現樹的優先遍歷" " "
如果root == None:
返回
myStack = []
節點=根
while node或myStack:
While node: #從根節點開始，壹直尋找它的左子樹。
打印node.elem，
myStack.append(節點)
node = node.lchild
node = myStack.pop() #while的結尾表示當前節點為空，即前壹個節點沒有左子樹。
Node = node.rchild #開始查看它右邊的子樹。
def middle_stack(self，root):
" ""使用堆棧實現樹的中間順序遍歷" " "
如果root == None:
返回
myStack = []
節點=根
while node或myStack:
While node: #從根節點開始，壹直尋找它的左子樹。
myStack.append(節點)
node = node.lchild
node = myStack.pop() #while的結尾表示當前節點為空，即前壹個節點沒有左子樹。
打印node.elem，
Node = node.rchild #開始查看它右邊的子樹。
def later_stack(self，root):
" ""使用堆棧對樹進行後序遍歷" " "
如果root == None:
返回
myStack1 = []
myStack2 = []
節點=根
myStack1.append(節點)
While myStack1: #這個While循環的作用是找出後序遍歷的逆序，存儲在myStack2中。
node = myStack1.pop()
if node.lchild:
mystack 1 . append(node . l child)
if node.rchild:
mystack 1 . append(node . rchild)
myStack2.append(節點)
而myStack2: #將myStack2中的元素推出堆棧，這是後序遍歷順序。
打印myStack2.pop()。elem，
定義級別_隊列(自身，根):
" ""使用隊列實現樹的分層遍歷" " "
如果root == None:
返回
我的隊列= []
節點=根
myQueue.append(節點)
當我的隊列:
node = myQueue.pop(0)
打印node.elem，
if node.lchild！=無:
myQueue.append(node.lchild)
if node.rchild！=無:
myQueue.append(node.rchild)
if name == 'main ':
" ""主要功能" " "
Elems = range(10) #生成十個數據作為樹節點。
Tree = Tree() #創建新的樹對象。
對於elem中的elem:
Tree.add(elem) #逐個添加樹的節點。
'打印'隊列實現分層遍歷:'
樹.級別_隊列(樹.根)
'打印'
遞歸實現優先遍歷:'
tree.front_digui(tree.root)
'打印'
順序遍歷的遞歸實現:'
tree.middle_digui(tree.root)
'打印'
遞歸實現後序遍歷:'
tree.later_digui(tree.root)
'打印'
堆棧實現優先遍歷:'
tree.front_stack(tree.root)
'打印'
堆棧實現中的順序遍歷:'
tree.middle_stack(tree.root)
'打印'
堆棧實現後序遍歷:'
Tree.later_stack(tree.root)摘要:
樹的遍歷主要有兩種，壹種是深度優先遍歷，像前序、中序、後序；另壹種是廣度優先遍歷，像層次遍歷。在樹結構中，兩者的區別不是很明顯，但是當樹擴展到有向圖和無向圖時，深度優先搜索和廣度優先搜索的效率和作用還是有很大區別的。
深度優先級壹般是遞歸，寬度優先級壹般是排隊。壹般來說，大多數可以遞歸實現的算法也可以通過棧來實現。
印象中有壹種遞歸的方法可以構造壹棵樹，但是壹直搞不清楚怎麽構造。後來仔細考慮，遞歸的思路有點類似深度優先算法，樹的構造應該是廣度優先。如果使用遞歸，必須有終止條件，比如指定樹的深度。否則，構造的樹將偏向左側單子葉植物或右側單子葉植物。因此，在壹般樹的構造中最好使用隊列。