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
您要执行什么操作?退出
解释
-
创建“Tree_structure”类。
-
设置’key’为True,将树的子项设置为空列表。
-
它具有一个“set_root”函数,有助于为树设置根值。
-
定义了一个名为‘add_vals’的方法,有助于将元素添加到树中。
-
定义了另一个名为“search_val”的方法,有助于在树中搜索元素。
-
定义另一个名为“count_non_leaf_nodes”的方法,有助于获取树的非叶节点计数。
-
它是一个递归函数。
-
提供了四个选项,如“在根处添加”、“在下面添加”、“计数”和“退出”。
-
根据用户给出的选项,执行相应的操作。
-
此输出显示在控制台上。