Khi được yêu cầu đếm số lượng nút lá trong Cây, một lớp ‘Cấu trúc cây’ sẽ được tạo, các phương thức để thêm giá trị gốc và các giá trị con khác được xác định. Các tùy chọn khác nhau được đưa ra mà người dùng có thể chọn. Dựa trên lựa chọn của người dùng, hoạt động được thực hiện trên các phần tử Cây.
Dưới đây là một minh chứng về điều tương tự -
Ví dụ
class Tree_structure:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root_node(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(key)
if temp is not None:
return temp
return None
def count_leaf_node(self):
leaf_nodes = []
self.count_leaf_node_helper_fun(leaf_nodes)
return len(leaf_nodes)
def count_leaf_node_helper_fun(self, leaf_nodes):
if self.children == []:
leaf_nodes.append(self)
else:
for child in self.children:
child.count_leaf_node_helper_fun(leaf_nodes)
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)
sub_op = my_input[2].strip().lower()
if sub_op == 'at':
tree = newNode
elif sub_op == 'below':
my_pos = my_input[3].strip().lower()
key = int(my_pos)
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_leaf_node()
print('The number of leaf nodes are : {}'.format(count))
elif operation == 'quit':
break Đầu ra
MenuMenu (this assumes no duplicate keys) add <data> at root add <data> below <data> count quit What operation would you like to perform ? add 78 at root What operation would you like to perform ? add 90 below 78 What operation would you like to perform ? add 8 below 78 What operation would you like to perform ? count The number of leaf nodes are : 2 What operation would you like to perform ? quit
Giải thích
-
Lớp 'Tree_ Structure' được tạo.
-
Nó đặt 'key' thành True và đặt một danh sách trống thành con của cây.
-
Nó có chức năng ‘set_root’ giúp đặt giá trị gốc cho Cây.
-
Một phương thức có tên là ‘add_vals’ được xác định, giúp thêm một phần tử vào Cây.
-
Một phương thức khác có tên là ‘search_val’ được xác định, giúp tìm kiếm một phần tử trong Cây.
-
Một phương thức khác có tên là ‘count_leaf_nodes’ được định nghĩa, giúp tính số lượng các nút lá của Cây.
-
Một phương thức khác có tên ‘count_leaf_nodes_helper’ được định nghĩa, gọi hàm đã xác định trước đó - đây là một hàm đệ quy.
-
Bốn tùy chọn được đưa ra, chẳng hạn như "thêm tại gốc", "thêm bên dưới", "đếm" và "thoát".
-
Tùy thuộc vào tùy chọn do người dùng cung cấp, hoạt động tương ứng được thực hiện.
-
Đầu ra này được hiển thị trên bảng điều khiển.