Python实现二叉树的前后序遍历

二叉树的结构：

前中后序遍历对应的规则：

先序遍历

先序遍历的原则是：先根、再左、再右。
即：ABCDEFGH

中序遍历

中序遍历的原则是：先左、再根、再右。
即：BDCEAFHG

后序遍历

后序遍历的原则是：先左、再右、再根。
即：DECBHGFA

1.  
   # 首先定义树的根节点
2.  
   class Node(object):
3.  
   """docstring for Node"""
4.  
    
5.  
   def __init__(self, elem=0, left=None, right=None):
6.  
   self.elem = elem
7.  
   self.lchild = left
8.  
   self.rchild = right
9.  
    
10.  
     
11.  
    # 定义一棵二叉树
12.  
    class BinaryTree(object):
13.  
    """docstring for BinaryTree"""
14.  
     
15.  
    def __init__(self):
16.  
    # 根节点
17.  
    self.root = None
18.  
     
19.  
    def add(self, item):
20.  
    # 向树中插入元素, 使用队列存储元素, 读取与弹出
21.  
    node = Node(item)
22.  
    if self.root is None:
23.  
    self.root = node
24.  
    return
25.  
    # 用顺序表实现队列, 先入先出FIFO
26.  
    # 首先传入根节点信息
27.  
    queue = [self.root]
28.  
     
29.  
    while queue:
30.  
    cur_node = queue.pop(0)
31.  
     
32.  
    # 若当前节点的左孩子为空, 将节点赋给当前节点左孩子
33.  
    if cur_node.lchild is None:
34.  
    cur_node.lchild = node
35.  
    return
36.  
    # 若当前节点左孩子不为空, 左孩子添加到当前节点中
37.  
    else:
38.  
    queue.append(cur_node.lchild)
39.  
     
40.  
    # 接下来同样判断右孩子
41.  
    if cur_node.rchild is None:
42.  
    cur_node.rchild = node
43.  
    return
44.  
    else:
45.  
    queue.append(cur_node.rchild)
46.  
     
47.  
    def breadth_travel(self):
48.  
    """广度遍历: 方法同add, 是一种反过来的操作
49.  
    """
50.  
    # 使用队列
51.  
    queue = [self.root]
52.  
    ret = []
53.  
    if self.root is None:
54.  
    return
55.  
    while queue:
56.  
    cur_node = queue.pop(0)
57.  
    # 打印结点值
58.  
    # print(cur_node.elem, end=" ")
59.  
    ret.append(cur_node.elem)
60.  
    if cur_node.lchild:
61.  
    queue.append(cur_node.lchild)
62.  
    if cur_node.rchild:
63.  
    queue.append(cur_node.rchild)
64.  
    print(ret)
65.  
     
66.  
    def pre_order(self, node):
67.  
    """前序遍历: 递归方法"""
68.  
    # if node is None:
69.  
    # return
70.  
    # print(node.elem, end=" ")
71.  
    # self.pre_order(node.lchild)
72.  
    # self.pre_order(node.rchild)
73.  
    ret = []
74.  
     
75.  
    def recur_0(node):
76.  
    if node:
77.  
    ret.append(node.elem)
78.  
    recur_0(node.lchild)
79.  
    recur_0(node.rchild)
80.  
    recur_0(node)
81.  
    print(ret)
82.  
     
83.  
    def in_order(self, node):
84.  
    """中序遍历"""
85.  
    # if node is None:
86.  
    # return
87.  
    # self.in_order(node.lchild)
88.  
    # print(node.elem, end=" ")
89.  
    # self.in_order(node.rchild)
90.  
    ret = []
91.  
     
92.  
    def recur_1(node):
93.  
    if node:
94.  
    recur_1(node.lchild)
95.  
    ret.append(node.elem)
96.  
    recur_1(node.rchild)
97.  
    recur_1(node)
98.  
    print(ret)
99.  
     
100.  
     def post_order(self, node):
101.  
     """后序遍历"""
102.  
     # 递归遍历跳出的条件
103.  
     # if node is None:
104.  
     # return
105.  
     # self.pre_order(node.lchild)
106.  
     # self.pre_order(node.rchild)
107.  
     # print(node.elem, end=" ")
108.  
     ret = []
109.  
      
110.  
     def recur(node):
111.  
     if node:
112.  
     recur(node.lchild)
113.  
     recur(node.rchild)
114.  
     ret.append(node.elem)
115.  
     recur(node)
116.  
     print(ret)
117.  
      
118.  
     def pre_order_1(self, node):
119.  
     """前序遍历(中左右): 非递归, 需要使用栈(递归的本质是栈实现)来实现"""
120.  
     # 定义一个栈
121.  
     st = []
122.  
     # 定义顺序数组
123.  
     result_arr = []
124.  
     if node:
125.  
     st.append(node)
126.  
     while st:
127.  
     node = st.pop()
128.  
     # 中
129.  
     result_arr.append(node.elem)
130.  
     # 右
131.  
     if node.rchild:
132.  
     st.append(node.rchild)
133.  
     # 左
134.  
     if node.lchild:
135.  
     st.append(node.lchild)
136.  
     print(result_arr)
137.  
      
138.  
     def in_order_1(self, node):
139.  
     """中序遍历(左中右), 需要指针(由于遍历的节点顺序和处理的节点顺序不同)"""
140.  
     st = []
141.  
     result_arr = []
142.  
     cur_node = node
143.  
     while cur_node or st:
144.  
     if cur_node:
145.  
     # 利用指针访问结点,访问到最底层数据
146.  
     # 结点入栈
147.  
     st.append(cur_node)
148.  
     # 左
149.  
     cur_node = cur_node.lchild
150.  
     else:
151.  
     cur_node = st.pop()
152.  
     # 中
153.  
     result_arr.append(cur_node.elem)
154.  
     # 右
155.  
     cur_node = cur_node.rchild
156.  
     print(result_arr)
157.  
      
158.  
     def in_order_2(self, node):
159.  
     """中序遍历(左中右), 通解"""
160.  
     st = []
161.  
     result_arr = []
162.  
     if node:
163.  
     st.append(node)
164.  
     while st:
165.  
     node = st[-1]
166.  
     if node:
167.  
     st.pop()
168.  
     if node.rchild:
169.  
     st.append(node.rchild)
170.  
     st.append(node)
171.  
     # 空节点入栈作为标记
172.  
     st.append(None)
173.  
     if node.lchild:
174.  
     st.append(node.lchild)
175.  
     else:
176.  
     # 空节点出栈
177.  
     st.pop()
178.  
     node = st[-1]
179.  
     st.pop()
180.  
     result_arr.append(node.elem)
181.  
     print(result_arr)
182.  
      
183.  
     def post_order_1(self, node):
184.  
     """后序遍历(左右中), 可以直接由前序遍历得到"""
185.  
     # 定义一个栈
186.  
     st = []
187.  
     # 定义顺序数组
188.  
     result_arr = []
189.  
     if node:
190.  
     st.append(node)
191.  
     while st:
192.  
     node = st.pop()
193.  
     # 中
194.  
     result_arr.append(node.elem)
195.  
     # 左
196.  
     if node.lchild:
197.  
     st.append(node.lchild)
198.  
     # 右
199.  
     if node.rchild:
200.  
     st.append(node.rchild)
201.  
     print(result_arr[::-1])
202.  
      
203.  
     def post_order_2(self, node):
204.  
     """后序遍历(左右中), 可以直接由前序遍历得到"""
205.  
     # 定义一个栈
206.  
     st = []
207.  
     # 定义顺序数组
208.  
     result_arr = []
209.  
     while st or node:
210.  
     while node:
211.  
     st.append(node)
212.  
     # 遍历二叉树直到结点不再含有左节点(右节点)
213.  
     node = node.lchild if node.lchild else node.rchild
214.  
     node = st.pop()
215.  
     # 最后加入中结点
216.  
     result_arr.append(node.elem)
217.  
     # 判断并开始遍历右节点(node指向右节点), 然后继续进行入栈操作(while内循环)
218.  
     node = st[-1].rchild if st and st[-1].lchild == node else None
219.  
     print(result_arr)
220.  
      
221.  
      
222.  
     if __name__ == '__main__':
223.  
     tree = BinaryTree()
224.  
     for i in range(9):
225.  
     tree.add(i)
226.  
     print("广度遍历: ")
227.  
     tree.breadth_travel()
228.  
     print("\n深度遍历: ")
229.  
     print("前序遍历: 递归")
230.  
     tree.pre_order(tree.root)
231.  
     print("中序遍历: 递归")
232.  
     tree.in_order(tree.root)
233.  
     print("后序遍历: 递归")
234.  
     tree.post_order(tree.root)
235.  
     print()
236.  
     print("前序遍历: 非递归")
237.  
     tree.pre_order_1(tree.root)
238.  
     print("中序遍历: 非递归")
239.  
     tree.in_order_1(tree.root)
240.  
     print("中序遍历: 非递归, 不需要指针")
241.  
     tree.in_order_2(tree.root)
242.  
     print("后序遍历: 非递归, 修改自前序")
243.  
     tree.post_order_1(tree.root)
244.  
     print("后序遍历: 非递归, 直接写")
245.  
     tree.post_order_2(tree.root)
246.  
      
247.  
     """
248.  
     广度遍历:
249.  
     0 1 2 3 4 5 6 7 8
250.  
     深度遍历:
251.  
     前序遍历: 递归
252.  
     0 1 3 7 8 4 2 5 6
253.  
     中序遍历: 递归
254.  
     7 3 8 1 4 0 5 2 6
255.  
     后序遍历: 递归
256.  
     7 8 3 4 1 5 6 2 0
257.  
     前序遍历: 非递归
258.  
     [0, 1, 3, 7, 8, 4, 2, 5, 6]
259.  
     中序遍历: 非递归
260.  
     [7, 3, 8, 1, 4, 0, 5, 2, 6]
261.  
     后序遍历: 非递归
262.  
     [7, 8, 3, 4, 1, 5, 6, 2, 0]
263.  
     """

这篇好文章是转载于：学新通技术网