UU Blog

Python二叉树递归和遍历

描述树

有这么一个二叉树

binary tree

上面图片由graphviz生成,描绘该树的.dot文件内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
digraph G {
node [shape = record ,height=.1];
node0[label = "<f0> |<f1> A|<f2> "];
node1[label = "<f0> |<f1> B|<f2> "];
node2[label = "<f0> |<f1> C|<f2> "];
node3[label = "<f0> |<f1> D|<f2> "];
node4[label = "<f0> |<f1> E|<f2> "];
node5[label = "<f0> |<f1> F|<f2> "];
node6[label = "<f0> |<f1> G|<f2> "];
node7[label = "<f0> |<f1> H|<f2> "];
node8[label = "<f0> |<f1> I|<f2> "];
"node0":f0 -> "node1":f1;
"node0":f2 -> "node2":f1;
"node1":f2 -> "node3":f1;
"node2":f0 -> "node4":f1;
"node2":f2 -> "node5":f1;
"node4":f0 -> "node6":f1;
"node5":f0 -> "node7":f1;
"node5":f2 -> "node8":f1;
}

生成树图:dot -Tgif btree.dot -o btree.gif

该树用Python描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode(object):
def __init__(self,data,left=None,right=None):
self.data = data
self.left = left
self.right = right

def __str__(self):
return str(self.data)

def create_btree():
A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in 'ABCDEFGHI']
A.left = B
A.right = C
B.right = D
C.left = E
C.right = F
E.left = G
F.left = H
F.right = I
return A

TreeNode用来描述二叉树结构。create_btree函数用来生成上图描述的树,并返回根节点。

深度优先搜索

递归遍历二叉树

前序遍历

1
2
3
4
5
6
7
# Depth-first Search
def preorder(node):
if node is None:
return
print(node.data)
preorder(node.left)
preorder(node.right)

中序遍历

1
2
3
4
5
6
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.data)
inorder(node.right)

后序遍历

1
2
3
4
5
6
def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.data)

迭代遍历二叉树

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
def preorder_iter(root):
s = []
node = root
while True:
while node:
print(node)
s.append(node)
node = node.left

if not s:
break
node = s.pop().right

广度优先搜索

层序遍历

用队列实现,子节点插后面,子节点的子节点也插在队列后面,从队列左边访问,永远都是层数高的在前面,实现层序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Breadth-first Search
from collections import deque

def level_order(node):
s = deque()
while True:
print(node)
if node.left:
s.append(node.left)
if node.right:
s.append(node.right)
if not s:
break
node = s.popleft()

运行、结果

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == '__main__':
root = create_btree()
print('preorder:')
preorder(root)
print('inorder:')
inorder(root)
print('postorder:')
postorder(root)
print('preorder_iter')
preorder_iter(root)
print('level_order')
level_order(root)

结果:

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
preorder:
A
B
D
C
E
G
F
H
I
inorder:
B
D
A
G
E
C
H
F
I
postorder:
D
B
G
E
H
I
F
C
A
preorder_iter
A
B
D
C
E
G
F
H
I
level_order
A
B
C
D
E
F
G
H
I

参考资料

Tree Traversal
Binay Tree

给作者打一针鸡血