实现使用后序遍历深度优先搜索遍历的Python程序

当需要使用后序遍历深度优先搜索时，可以创建一个树类，并添加元素，对特定元素进行搜索和执行后序遍历等方法。创建该类的实例，即可访问这些方法。

下面是一个示例 −

更多Python相关文章，请阅读：Python 教程

例子

class Tree_Struct:
   def __init__(self, key=None):
      self.key = key
      self.children = []

   def add_elem(self, node):
      self.children.append(node)
 
   def search_elem(self, key):
      if self.key == key:
         return self
      for child in self.children:
         temp = child.search_elem(key)
         if temp is not None:
            return temp
      return None

   def postorder_traversal(self):
      for child in self.children:
         child.postorder_traversal()
      print(self.key, end=' ')

my_instance = None

print('菜单（假设没有重复键）')
print('在根节点添加<data>')
print('在<data>下方添加<data>')
print('深度优先搜索')
print('退出')

while True:
   my_input = input('你要执行什么操作？').split()

   operation = my_input[0].strip().lower()
   if operation == 'add':
      data = int(my_input[1])
      new_node = Tree_Struct(data)
      suboperation = my_input[2].strip().lower()
      if suboperation == 'at':
         my_instance = new_node
      else:
         position = my_input[3].strip().lower()
         key = int(position)
         ref_node = None
         if my_instance is not None:
            ref_node = my_instance.search_elem(key)
         if ref_node is None:
            print('没有这个键')
            continue
         ref_node.add_elem(new_node)

   elif operation == 'dfs':
      print('后序遍历结果为：', end='')
      my_instance.postorder_traversal()
      print()

   elif operation == 'quit':
      break

输出结果

菜单（假设没有重复键）
在根节点添加<data>
在<data>下方添加<data>
深度优先搜索
退出
你要执行什么操作？在根添加5
你要执行什么操作？在5下添加9
你要执行什么操作？在9下添加2
你要执行什么操作？dfs
后序遍历结果为：5
你要执行什么操作？quit

解释

• 创建了’Tree_struct’类并添加了必要的属性。

• 它具有一个’init’函数，用于创建一个空列表。

• 它有一个’add_elem’方法，用于帮助将元素添加到树中。

• 另一个名为’后序遍历(postorder traversal)’的方法执行后序遍历。

• 定义了一个名为’search_elem’的方法，用于搜索特定元素。

• 创建一个实例，并将其指派为’None’。

• 获取用户输入以执行所需操作。

• 根据用户的选择执行操作。

• 根据用户的选择，执行操作。

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