Thêm phương thức count_leaf_node dùng hàm helper đệ quy thu thập các nút không có con vào list, trả về độ dài list.
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_val(key)
if temp:
return temp
return None
def count_leaf_node(self):
leaves = []
self._collect_leaves(leaves)
return len(leaves)
def _collect_leaves(self, leaves):
if not self.children:
leaves.append(self)
else:
for child in self.children:
child._collect_leaves(leaves)
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 lá:", tree.count_leaf_node())
elif op == 'quit':
break
Kết quả
Menu: add at root | add below | count | quit Thao tác: add 78 at root Thao tác: add 90 below 78 Thao tác: add 8 below 78 Thao tác: count Số nút lá: 2 Thao tác: quit
Giải thích
- Nút lá:
self.children == []. - Hàm helper đệ quy đi sâu, thêm nút lá vào list chung.
- Trả về số lượng phần tử trong list.