Python程序构建树并执行插入、删除、显示操作

当需要构建二叉树并执行插入元素、删除元素和显示树中元素的操作时，需要在类中定义方法。实例化类并用它来访问元素并执行操作。

下面是一个示例：

例子

class Tree_struct:
   def __init__(self, data=None, parent=None):
      self.key = data
      self.children = []
      self.parent = parent

   def set_root(self, data):
      self.key = data

   def add_node(self, node):
      self.children.append(node)

   def search_node(self, key):
      if self.key == key:
            return self
      for child in self.children:
            temp = child.search_node(key)
            if temp is not None:
               return temp
      return None

   def remove_node(self):
      parent = self.parent
      index = parent.children.index(self)
      parent.children.remove(self)
      for child in reversed(self.children):
            parent.children.insert(index, child)
            child.parent = parent

   def bfs(self):
      queue = [self]
      while queue != []:
            popped = queue.pop(0)
            for child in popped.children:
               queue.append(child)
            print(popped.key, end=' ')

my_instance = None

print('菜单（假定没有重复关键字）')
print('在根节点添加')
print('在下添加')
print('删除')
print('显示')
print('退出')

while True:
   do = input('您想做什么？').split()

   operation = do[0].strip().lower()
   if operation == 'add':
      data = int(do[1])
      new_node = Tree_struct(data)
      suboperation = do[2].strip().lower()
      if suboperation == 'at':
         my_instance = new_node
      elif suboperation == 'below':
         position = do[3].strip().lower()
         key = int(position)
         ref_node = None
         if my_instance is not None:
            ref_node = my_instance.search_node(key)
         if ref_node is None:
            print('没有这个关键字。')
            continue
         new_node.parent = ref_node
         ref_node.add_node(new_node)

   elif operation == 'remove':
      data = int(do[1])
      to_remove = my_instance.search_node(data)
      if my_instance == to_remove:
         if my_instance.children == []:
            my_instance = None
         else:
            leaf = my_instance.children[0]
            while leaf.children != []:
               leaf = leaf.children[0]
            leaf.parent.children.remove_node(leaf)
            leaf.parent = None
            leaf.children = my_instance.children
            my_instance = leaf
      else:
         to_remove.remove_node()

   elif operation == 'display':
      if my_instance is not None:
         print('广度优先搜索遍历为：', end='')
         my_instance.bfs()
         print()
      else:
         print('树为空')

   elif operation == 'quit':
      break

输出

菜单（假定没有重复关键字）
在根节点添加
在下添加
删除
显示
退出
您想做什么？add 5 at root
您想做什么？add 6 below 5
您想做什么？add 8 below 6
您想做什么？remove 8
您想做什么？display
广度优先搜索遍历为：5 6
您想做什么？quit

说明

• 创建一个名为“Tree_struct”的类，具有必需的属性。

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

• 定义另一个名为“set_root”的方法来指定树的根。

• 定义另一个名为“add_node”的方法，用于将节点添加到树中。

• 定义另一个名为“search_node”的方法，用于搜索特定元素。

• 定义一个名为“remove_node”的方法，从树中删除元素。

• 定义另一个名为“bfs”的方法，用于在树上执行广度优先搜索。

• 创建一个实例并将其分配给“None”。

• 接受用户输入要执行的操作。

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

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