Python程序计算给定树的非叶节点的数量

当需要查找树中的非叶节点数时，创建一个“Tree_structure”类，定义用于设置根值和添加其他值的方法。提供了各种选项供用户选择。基于用户的选择，对树元素执行操作。

以下是类似操作的演示−

示例

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

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

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

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

   def count_non_leaf_node(self):
      nonleaf_count = 0
      if self.children != []:
         nonleaf_count = 1
      for child in self.children:
         nonleaf_count = nonleaf_count + child.count_non_leaf_node()
      return nonleaf_count

tree = 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])
      newNode = Tree_structure(data)
      suboperation = my_input[2].strip().lower()
      if suboperation == 'at':
         tree = newNode
      elif suboperation == 'below':
         position = my_input[3].strip().lower()
         key = int(position)
         ref_node = None
         if tree is not None:
            ref_node = tree.search_val(key)
         if ref_node is None:
            print('没有这个关键字。')
            continue
         ref_node.add_vals(newNode)

   elif operation == 'count':
      if tree is None:
         print('树是空的')
      else:
         count = tree.count_non_leaf_node()
         print('非叶节点数为：{}'.format(count))

   elif operation == 'quit':
      break

输出

菜单（假定没有重复的键）
在根处添加 <data>
在 <data> 下面添加 <data>
计数
退出
您要执行什么操作？在根处添加 34
您要执行什么操作？在 34 下面添加 78
您要执行什么操作？在 78 下面添加 56
您要执行什么操作？在 56 下面添加 90
您要执行什么操作？计数
非叶节点数为：3
您要执行什么操作？退出