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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2020数据结构小学期（三）——由遍历序列恢复二叉树算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1563字，纯文字阅读大概需要3分钟。

内容图文

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)

 

内容总结

以上是互联网集市为您收集整理的2020数据结构小学期（三）——由遍历序列恢复二叉树算法全部内容，希望文章能够帮你解决2020数据结构小学期（三）——由遍历序列恢复二叉树算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---