构建二叉树：使用中序或后序遍历作为输入的Python程序

当需要通过使用中序或后序遍历输入来构建二叉树时，定义一个类，该类具有设置根元素，执行中序遍历，执行后续遍历的方法。可以通过创建该类的实例来使用它。

以下是相同操作的演示 −

更多Python相关文章，请阅读：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’方法通过使用先前指定的元素构建二叉树。

• 在此树上执行后续遍历和中序遍历。

• 在控制台上显示相关输出。