Python实现二叉树遍历的递归和非递归算法

发表于 | 更新于 | 分类于 | 阅读次数
字数统计 1.3k | 阅读时长 6

本文主要用python实现二叉树的4种遍历算法，除层次遍历外，前序、中序和后序遍历分别包含递归和非递归2种实现方式。

前序遍历

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
# -----------前序遍历 ------------
   # 递归算法
   def pre_order_recursive(self, T):
       if T == None:
           return
       print(T.root, end=' ')
       self.pre_order_recursive(T.lchild)
       self.pre_order_recursive(T.rchild)

   # 非递归算法
   def pre_order_non_recursive(self, T):
       """借助栈实现前驱遍历
       """
       if T == None:
           return
       stack = []
       while T or len(stack) > 0:
           if T:
               stack.append(T)
               print(T.root, end=' ')
               T = T.lchild
           else:
               T = stack[-1]
               stack.pop()
               T = T.rchild

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -----------中序遍历 ------------
    # 递归算法
    def mid_order_recursive(self, T):
        if T == None:
            return
        self.mid_order_recursive(T.lchild)
        print(T.root, end=' ')
        self.mid_order_recursive(T.rchild)

    # 非递归算法
    def mid_order_non_recursive(self, T):
        """借助栈实现中序遍历
        """
        if T == None:
            return
        stack = []
        while T or len(stack) > 0:
            if T:
                stack.append(T)
                T = T.lchild
            else:
                T = stack.pop()
                print(T.root, end=' ')
                T = T.rchild

后序遍历

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
# -----------后序遍历 ------------
    # 递归算法
    def post_order_recursive(self, T):
        if T == None:
            return
        self.post_order_recursive(T.lchild)
        self.post_order_recursive(T.rchild)
        print(T.root, end=' ')

    # 非递归算法
    def post_order_non_recursive(self, T):
        """借助两个栈实现后序遍历
        """
        if T == None:
            return
        stack1 = []
        stack2 = []
        stack1.append(T)
        while stack1:
            node = stack1.pop()
            if node.lchild:
                stack1.append(node.lchild)
            if node.rchild:
                stack1.append(node.rchild)
            stack2.append(node)
        while stack2:
            print(stack2.pop().root, end=' ')
        return

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -----------层次遍历 ------------
    def level_order(self, T):
        """借助队列（其实还是一个栈）实现层次遍历
        """
        if T == None:
            return
        stack = []
        stack.append(T)
        while stack:
            node = stack.pop(0)  # 实现先进先出
            print(node.root, end=' ')
            if node.lchild:
                stack.append(node.lchild)
            if node.rchild:
                stack.append(node.rchild)

完整代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
class NodeTree:
    def __init__(self, root=None, lchild=None, rchild=None):
        """创建二叉树
        Argument:
            lchild: BinTree
                左子树
            rchild: BinTree
                右子树

        Return:
            Tree
        """
        self.root = root
        self.lchild = lchild
        self.rchild = rchild


class BinTree:

    # -----------前序遍历 ------------
    # 递归算法
    def pre_order_recursive(self, T):
        if T == None:
            return
        print(T.root, end=' ')
        self.pre_order_recursive(T.lchild)
        self.pre_order_recursive(T.rchild)

    # 非递归算法
    def pre_order_non_recursive(self, T):
        """借助栈实现前驱遍历
        """
        if T == None:
            return
        stack = []
        while T or len(stack) > 0:
            if T:
                stack.append(T)
                print(T.root, end=' ')
                T = T.lchild
            else:
                T = stack[-1]
                stack.pop()
                T = T.rchild

    # -----------中序遍历 ------------
    # 递归算法
    def mid_order_recursive(self, T):
        if T == None:
            return
        self.mid_order_recursive(T.lchild)
        print(T.root, end=' ')
        self.mid_order_recursive(T.rchild)

    # 非递归算法
    def mid_order_non_recursive(self, T):
        """借助栈实现中序遍历
        """
        if T == None:
            return
        stack = []
        while T or len(stack) > 0:
            if T:
                stack.append(T)
                T = T.lchild
            else:
                T = stack.pop()
                print(T.root, end=' ')
                T = T.rchild

    # -----------后序遍历 ------------
    # 递归算法
    def post_order_recursive(self, T):
        if T == None:
            return
        self.post_order_recursive(T.lchild)
        self.post_order_recursive(T.rchild)
        print(T.root, end=' ')

    # 非递归算法
    def post_order_non_recursive(self, T):
        """借助两个栈实现后序遍历
        """
        if T == None:
            return
        stack1 = []
        stack2 = []
        stack1.append(T)
        while stack1:
            node = stack1.pop()
            if node.lchild:
                stack1.append(node.lchild)
            if node.rchild:
                stack1.append(node.rchild)
            stack2.append(node)
        while stack2:
            print(stack2.pop().root, end=' ')
        return

    # -----------层次遍历 ------------
    def level_order(self, T):
        """借助队列（其实还是一个栈）实现层次遍历
        """
        if T == None:
            return
        stack = []
        stack.append(T)
        while stack:
            node = stack.pop(0)  # 实现先进先出
            print(node.root, end=' ')
            if node.lchild:
                stack.append(node.lchild)
            if node.rchild:
                stack.append(node.rchild)

    # ----------- 前序遍历序列、中序遍历序列 —> 重构二叉树 ------------
    def tree_by_pre_mid(self, pre, mid):
        if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
            return
        T = NodeTree(pre[0])
        index = mid.index(pre[0])
        T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
        T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
        return T

    # ----------- 后序遍历序列、中序遍历序列 —> 重构二叉树 ------------
    def tree_by_post_mid(self, post, mid):
        if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
            return
        T = NodeTree(post[-1])
        index = mid.index(post[-1])
        T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
        T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
        return T


if __name__ == '__main__':
    # ----------- 测试：前序、中序、后序、层次遍历 -----------
    # 创建二叉树
    nodeTree = NodeTree(1,
                        lchild=NodeTree(2,
                                        lchild=NodeTree(4,
                                                        rchild=NodeTree(7))),
                        rchild=NodeTree(3,
                                        lchild=NodeTree(5),
                                        rchild=NodeTree(6)))
    T = BinTree()
    print('前序遍历递归\t')
    T.pre_order_recursive(nodeTree)  # 前序遍历-递归
    print('\n')
    print('前序遍历非递归\t')
    T.pre_order_non_recursive(nodeTree)  # 前序遍历-非递归
    print('\n')
    print('中序遍历递归\t')
    T.mid_order_recursive(nodeTree)  # 中序遍历-递归
    print('\n')
    print('中序遍历非递归\t')
    T.mid_order_non_recursive(nodeTree)  # 中序遍历-非递归
    print('\n')
    print('后序遍历递归\t')
    T.post_order_recursive(nodeTree)  # 后序遍历-递归
    print('\n')
    print('后序遍历非递归\t')
    T.post_order_non_recursive(nodeTree)  # 后序遍历-非递归
    print('\n')
    print('层次遍历\t')
    T.level_order(nodeTree)  # 层次遍历
    print('\n')

    print('==========================================================================')

    # ----------- 测试：由遍历序列构造二叉树 -----------
    T = BinTree()
    pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
    post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']

    newT_pre_mid = T.tree_by_pre_mid(pre, mid)  # 由前序序列、中序序列构造二叉树
    T.post_order_recursive(newT_pre_mid)  # 获取后序序列
    print('\n')

    newT_post_mid = T.tree_by_post_mid(post, mid)  # 由后序序列、中序序列构造二叉树
    T.pre_order_recursive(newT_post_mid)  # 获取前序序列

运行结果

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
前序遍历递归	
1 2 4 7 3 5 6 

前序遍历非递归	
1 2 4 7 3 5 6 

中序遍历递归	
4 7 2 1 5 3 6 

中序遍历非递归	
4 7 2 1 5 3 6 

后序遍历递归	
7 4 2 5 6 3 1 

后序遍历非递归	
7 4 2 5 6 3 1 

层次遍历	
1 2 3 4 5 6 7 

==========================================================================
C B E H G I F D A 

A B C D E F G H I

------ 本文结束------
bluesliuf wechat
坚持技术分享，欢迎大家扫码交流！