Python二叉树递归和遍历

Posted on Edited on In ,

描述树

有这么一个二叉树

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
13
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
51
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

关注公众号 尹安灿