本文實例講述了Python實現二叉樹及遍歷方法。分享給大家供大家參考，具體如下：
介紹：
樹是數據結構中非常重要的一種，主要的用途是用來提高查找效率，對于要重復查找的情況效果更佳，如二叉排序樹、FP-樹。另外可以用來提高編碼效率，如哈弗曼樹。
代碼：
用Python實現樹的構造和幾種遍歷算法，雖然不難，不過還是把代碼作了一下整理總結。實現功能：
① 樹的構造
② 遞歸實現先序遍歷、中序遍歷、后序遍歷
③ 堆棧實現先序遍歷、中序遍歷、后序遍歷
④ 隊列實現層次遍歷
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#coding=utf-8class Node(object): """節點類""" def __init__(self, elem=-1, lchild=None, rchild=None): self.elem = elem self.lchild = lchild self.rchild = rchildclass Tree(object): """樹類""" def __init__(self): self.root = Node() self.myQueue = [] def add(self, elem): """為樹添加節點""" node = Node(elem) if self.root.elem == -1: # 如果樹是空的，則對根節點賦值 self.root = node self.myQueue.append(self.root) else: treeNode = self.myQueue[0] # 此結點的子樹還沒有齊。 if treeNode.lchild == None: treeNode.lchild = node self.myQueue.append(treeNode.lchild) else: treeNode.rchild = node self.myQueue.append(treeNode.rchild) self.myQueue.pop(0) # 如果該結點存在右子樹，將此結點丟棄。 def front_digui(self, root): """利用遞歸實現樹的先序遍歷""" if root == None: return print root.elem, self.front_digui(root.lchild) self.front_digui(root.rchild) def middle_digui(self, root): """利用遞歸實現樹的中序遍歷""" if root == None: return self.middle_digui(root.lchild) print root.elem, self.middle_digui(root.rchild) def later_digui(self, root): """利用遞歸實現樹的后序遍歷""" if root == None: return self.later_digui(root.lchild) self.later_digui(root.rchild) print root.elem, def front_stack(self, root): """利用堆棧實現樹的先序遍歷""" if root == None: return myStack = [] node = root while node or myStack: while node: #從根節點開始，一直找它的左子樹 print node.elem, myStack.append(node) node = node.lchild node = myStack.pop() #while結束表示當前節點node為空，即前一個節點沒有左子樹了 node = node.rchild #開始查看它的右子樹 def middle_stack(self, root): """利用堆棧實現樹的中序遍歷""" if root == None: return myStack = [] node = root while node or myStack: while node: #從根節點開始，一直找它的左子樹 myStack.append(node) node = node.lchild node = myStack.pop() #while結束表示當前節點node為空，即前一個節點沒有左子樹了 print node.elem, node = node.rchild #開始查看它的右子樹 def later_stack(self, root): """利用堆棧實現樹的后序遍歷""" if root == None: return myStack1 = [] myStack2 = [] node = root myStack1.append(node) while myStack1: #這個while循環的功能是找出后序遍歷的逆序，存在myStack2里面 node = myStack1.pop() if node.lchild: myStack1.append(node.lchild) if node.rchild: myStack1.append(node.rchild) myStack2.append(node) while myStack2: #將myStack2中的元素出棧，即為后序遍歷次序 print myStack2.pop().elem, def level_queue(self, root): """利用隊列實現樹的層次遍歷""" if root == None: return myQueue = [] node = root myQueue.append(node) while myQueue: node = myQueue.pop(0) print node.elem, if node.lchild != None: myQueue.append(node.lchild) if node.rchild != None: myQueue.append(node.rchild)if __name__ == '__main__': """主函數""" elems = range(10) #生成十個數據作為樹節點 tree = Tree() #新建一個樹對象 for elem in elems: tree.add(elem) #逐個添加樹的節點 print '隊列實現層次遍歷:' tree.level_queue(tree.root) print '\n\n遞歸實現先序遍歷:' tree.front_digui(tree.root) print '\n遞歸實現中序遍歷:' tree.middle_digui(tree.root) print '\n遞歸實現后序遍歷:' tree.later_digui(tree.root) print '\n\n堆棧實現先序遍歷:' tree.front_stack(tree.root) print '\n堆棧實現中序遍歷:' tree.middle_stack(tree.root) print '\n堆棧實現后序遍歷:' tree.later_stack(tree.root) |
總結：
樹的遍歷主要有兩種，一種是深度優先遍歷，像前序、中序、后序；另一種是廣度優先遍歷，像層次遍歷。在樹結構中兩者的區別還不是非常明顯，但從樹擴展到有向圖，到無向圖的時候，深度優先搜索和廣度優先搜索的效率和作用還是有很大不同的。
深度優先一般用遞歸，廣度優先一般用隊列。一般情況下能用遞歸實現的算法大部分也能用堆棧來實現。
我印象中是有遞歸構造樹的方法，卻一直想不出該怎么構造。后來仔細想了一下，遞歸思想有點類似深度優先算法，而樹的構造應該是廣度優先的。如果用遞歸的話一定要有個終止條件，例如規定樹深等。不然構造出來的樹會偏向左單子樹或者右單子樹。所以一般樹的構造還是應該用隊列比較好。
以上說的不夠嚴謹，有錯誤之處，歡迎指正！
希望本文所述對大家Python程序設計有所幫助。
