Xây dựng lớp Tree_structure với các phương thức thêm nút gốc, thêm nút con, tìm kiếm, và đệ quy tính tổng giá trị tất cả nút. Chương trình tương tác menu dòng lệnh.
Ví dụ
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:
return temp
return None
def summation_nodes(self):
total = self.key
for child in self.children:
total += child.summation_nodes()
return total
tree = None
print("Menu: add at root | add below | summation | quit")
while True:
inp = input("Thao tác: ").split()
op = inp[0].lower()
if op == 'add':
data = int(inp[1])
new_node = Tree_structure(data)
sub = inp[2].lower()
if sub == 'at':
tree = new_node
elif sub == 'below':
key = int(inp[3])
ref = tree.search_val(key) if tree else None
if not ref:
print("Không tìm thấy key")
continue
ref.add_vals(new_node)
elif op == 'summation':
if not tree:
print("Cây rỗng")
else:
print("Tổng các nút:", tree.summation_nodes())
elif op == 'quit':
break
Kết quả
Menu: add at root | add below | summation | quit Thao tác: add 56 at root Thao tác: add 45 below 56 Thao tác: add 23 below 56 Thao tác: summation Tổng các nút: 124 Thao tác: quit
Giải thích
- Lớp Tree_structure quản lý nút và danh sách con.
- Phương thức
summation_nodesđệ quy cộng giá trị nút hiện tại và tất cả con. - Menu cho phép xây dựng cây và truy vấn tổng.