本文實例講述了Python利用前序和中序遍歷結果重建二叉樹的方法。分享給大家供大家參考，具體如下：
題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。
這道題比較容易，前序遍歷的結果中，第一個結點一定是根結點，然后在中序遍歷的結果中查找這個根結點，根結點左邊的就是左子樹，根結點右邊的就是右子樹，遞歸構造出左、右子樹即可。示意圖如圖所示：
利用前序和中序遍歷的結果重建二叉樹
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
|
# coding: utf-8'''題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。'''class Node: def __init__(self, data, left, right): self.data = data self.left = left self.right = rightdef construct_tree(pre_order, mid_order): # 忽略參數合法性判斷 if len(pre_order) == 0 : return None # 前序遍歷的第一個結點一定是根結點 root_data = pre_order[0] for i in range(0, len(mid_order)): if mid_order[i] == root_data: break # 遞歸構造左子樹和右子樹 left = construct_tree(pre_order[1 : 1 + i], mid_order[:i]) right = construct_tree(pre_order[1 + i:], mid_order[i+1:]) return Node(root_data, left, right)if __name__ == '__main__': pre_order = [1, 2, 4, 7, 3, 5, 6, 8] mid_order = [4, 7, 2, 1, 5, 3, 8, 6] root = construct_tree(pre_order, mid_order) print root.data print root.left.data print root.right.data print root.left.left.data print root.left.left.right.data print root.right.right.left print root.right.left.data |
希望本文所述對大家Python程序設計有所幫助。
