数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：基于中序或后序遍历构建二叉树
当需要通过输入中序或后序遍历来构建二叉树时，我们会定义一个类，该类包含设置根元素、执行中序遍历和执行后序遍历的方法。可以通过创建类的实例来使用它。
下面是相同内容的演示 -
示例
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def inorder_traversal(self):
if self.left is not None:
self.left.inorder_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder_traversal()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print()输出
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
解释
创建具有所需属性的“BinaryTree_struct”类。
它有一个“init”函数，用于将左右节点设置为“None”。
它有一个“set_root”方法，用于设置二叉树的根。
另一个名为“inorder_traversal”的方法执行中序遍历，即左→节点→右。
定义了另一个名为“post_order_traversal”的方法，用于以后序方式遍历树，即左→右→节点。
定义了一个名为“construct_btree”的方法，用于使用之前指定的元素构建二叉树。
定义了一个名为“search_elem”的方法，用于搜索特定元素。
创建“BinaryTree_struct”类的对象。
使用“construct_btree”方法通过之前指定的元素构建二叉树。
对该树执行后序遍历和中序遍历。
在控制台上显示相关的输出。
更新于: 2021年4月15日
356 次查看
广告