以中序或后序遍历为输入构建二叉树的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):
ifself.leftis not None:
self.left.inorder_traversal()
print(self.key, end=' ')
ifself.rightis not None:
self.right.inorder_traversal()
def post_order_traversal(self):
ifself.leftis not None:
self.left.post_order_traversal()
ifself.rightis 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”函数，用于将左右节点设置为“无”。
它有一个“set_root”方法，可以帮助设置二叉树的根。
另一种名为“inorder_traversal”的方法执行有序遍历，i.eLeft→Node→Right。
定义了另一个名为“post_order_traversal”的方法，它有助于按后序遍历树，i.eLeft→Right→Node。
定义了一个名为“construct_btree”的方法，该方法有助于使用先前指定的元素构建二叉树。
定义了一个名为“search_elem”的方法，它有助于搜索特定元素。
创建了“BinaryTree_struct”类的对象。
'construct_btree'方法用于通过获取先前指定的元素来构造二叉树。
在这棵树上执行后序遍历和按序遍历。
相关输出显示在控制台上。