2020数据结构小学期（三）——由遍历序列恢复二叉树算法

3、由遍历序列恢复二叉树

输入：遍历序列

功能要求：输出二叉树形态或输出二叉树的三种遍历序列

源码：

 1 class TreeNode():
 2     def __init__(self, val, left=None, right=None):
 3         self.val = val
 4         self.left = left
 5         self.right = right
 6 
 7 
 8 def post_print(root):
 9     if root:
10         post_print(root.left)
11         post_print(root.right)
12         print(root.val, end=" ")
13 
14 
15 def restore_tree(pre_order, in_order):
16     if len(pre_order) == 0:
17         return None
18     elif len(in_order) == 1:
19         return TreeNode(in_order[0])
20     else:
21         root = pre_order[0]
22         depth = in_order.index(root)
23         temp = TreeNode(root)
24         temp.left = restore_tree(pre_order[1:depth + 1], in_order[:depth])
25         temp.right = restore_tree(pre_order[depth + 1:], in_order[depth + 1:])
26     return temp
27 
28 
29 if __name__ == '__main__':
30     pre_str = input("请输入先序遍历序列：")
31     in_str = input("请输入中序遍历序列：")
32     # pre_order = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
33     # in_order = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
34     pre_order = []
35     in_order = []
36     for char in pre_str:
37         pre_order.append(char)
38     for char in in_str:
39         in_order.append(char)
40     temp = restore_tree(pre_order, in_order)
41     print("先序遍历：")
42     for char in pre_order:
43         print(char, end=" ")
44     print()
45     print("中序遍历：")
46     for char in in_order:
47         print(char, end=" ")
48     print()
49     print("后序遍历：")
50     post_print(temp)