ภาพรวม
นับจำนวนโหนดที่ไม่ใช่ leaf node (มีลูกอย่างน้อย 1 ตัว) ใน general tree โดยใช้ 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_non_leaf_nodes(self):
count = 1 if self.children else 0 # นับตัวเองถ้ามีลูก
for child in self.children:
count += child.count_non_leaf_nodes()
return count
# โปรแกรมโต้ตอบ (เหมือนบทความก่อนหน้า)
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"Non-leaf nodes: {tree.count_non_leaf_nodes()}")
else:
print("Tree is empty")
elif op == 'quit':
breakตัวอย่างการทำงาน
Operation? add 34 at root Operation? add 78 below 34 Operation? add 56 below 78 Operation? add 90 below 56 Operation? count Non-leaf nodes: 3 Operation? quit
คำอธิบาย
- โหนดที่มี children (len > 0) คือ non-leaf node
- ฟังก์ชัน recursion: นับตัวเอง (ถ้าเป็น non-leaf) + ผลรวมจากทุก child
- ในตัวอย่าง: 34, 78, 56 เป็น non-leaf (มีลูก), 90 เป็น leaf
