ภาพรวม
นับจำนวน leaf node (โหนดที่ไม่มีลูก) ใน general tree โดยใช้ helper function แบบ recursion
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data=None):
self.key = data
self.children = []
def add_child(self, node):
self.children.append(node)
def find_node(self, key):
if self.key == key:
return self
for child in self.children:
result = child.find_node(key)
if result:
return result
return None
def count_leaf_nodes(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")
print("add at root")
print("add below ")
print("count")
print("quit")
while True:
user_input = input("Operation? ").split()
if not user_input:
continue
op = user_input[0].lower()
if op == 'add':
data = int(user_input[1])
new_node = TreeNode(data)
sub_op = user_input[2].lower()
if sub_op == 'at':
tree = new_node
elif sub_op == 'below':
parent_key = int(user_input[3])
parent = tree.find_node(parent_key) if tree else None
if parent:
parent.add_child(new_node)
else:
print("Key not found")
elif op == 'count':
if tree:
print(f"Leaf nodes: {tree.count_leaf_nodes()}")
else:
print("Tree is empty")
elif op == 'quit':
breakตัวอย่างการทำงาน
Operation? add 78 at root Operation? add 90 below 78 Operation? add 8 below 78 Operation? count Leaf nodes: 2 Operation? quit
คำอธิบาย
- Leaf node = โหนดที่ children ว่าง
- ใช้ helper method
_collect_leavesสะสม leaf nodes ใน list - ในตัวอย่าง: 78 มีลูก 2 ตัว (non-leaf), 90 และ 8 ไม่มีลูก (leaf) = 2 leaf nodes
เวอร์ชันสั้นกว่า (ไม่ต้อง helper)
def count_leaf_nodes(self):
if not self.children:
return 1
return sum(child.count_leaf_nodes() for child in self.children)