构建二叉树：使用中序或后序遍历作为输入的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