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('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('count')
print('quit')

while True:
   my_input = input('What operation would you like to perform ? ').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('No such key.')
            continue
         ref_node.add_vals(newNode)

   elif operation == 'count':
      if tree is None:
         print('The tree is empty ')
      else:
         count = tree.count_non_leaf_node()
         print('The number of non-leaf nodes are : {}'.format(count))

   elif operation == 'quit':
      break

输出

Menu (this assumes no duplicate keys)
add <data> at root
add <data> below <data>
count
quit
What operation would you like to perform ? add 34 at root
What operation would you like to perform ? add 78 below 34
What operation would you like to perform ? add 56 below 78
What operation would you like to perform ? add 90 below 56
What operation would you like to perform ? count
The number of non-leaf nodes are : 3
What operation would you like to perform ? quit

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

解释

  • 创建“Tree_structure”类。

  • 它将“key”设置为True，并将一个空列表设置为树的子节点。

  • 它有一个“set_root”函数，有助于设置树的根值。

  • 定义了一个名为“add_vals”的方法，有助于向树中添加元素。

  • 定义了一个名为“search_val”的方法，有助于在树中搜索元素。

  • 定义了一个名为“count_non_leaf_nodes”的方法，有助于获取树的非叶子节点的数量。

  • 这是一个递归函数。

  • 提供了四个选项，例如“添加到根节点”、“添加到下方”、“计数”和“退出”。

  • 根据用户提供的选项，执行相应操作。

  • 此输出显示在控制台上。

更新于: 2021年4月15日

170 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告