Mở rộng lớp Tree_structure thêm phương thức count_non_leaf_node đệ quy: nút không phải lá là nút có ít nhất một con.
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 count_non_leaf_node(self):
cnt = 0
if self.children:
cnt = 1
for child in self.children:
cnt += child.count_non_leaf_node()
return cnt
tree = None
print("Menu: add at root | add below | count | 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 == 'count':
if not tree:
print("Cây rỗng")
else:
print("Số nút không phải lá:", tree.count_non_leaf_node())
elif op == 'quit':
break
Kết quả
Menu: add at root | add below | count | quit Thao tác: add 34 at root Thao tác: add 78 below 34 Thao tác: add 56 below 78 Thao tác: add 90 below 56 Thao tác: count Số nút không phải lá: 3 Thao tác: quit
Giải thích
- Nút không phải lá:
self.children != []. - Đệ quy cộng 1 cho nút hiện tại nếu có con, sau đó cộng kết quả từ các con.