ภาพรวม
สร้างโครงสร้างต้นไม้ (Tree) แบบ general tree และคำนวณผลรวมของทุกโหนด โดยใช้ recursion
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root(self, data):
self.key = data
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 sum_all_nodes(self):
total = self.key
for child in self.children:
total += child.sum_all_nodes()
return total
# โปรแกรมโต้ตอบ
tree = None
print("Menu (no duplicate keys allowed)")
print("add at root")
print("add below ")
print("summation")
print("quit")
while True:
user_input = input("What would you like to do? ").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 == 'summation':
if tree:
print(f"Sum of all nodes: {tree.sum_all_nodes()}")
else:
print("Tree is empty")
elif op == 'quit':
breakตัวอย่างการทำงาน
What would you like to do? add 56 at root What would you like to do? add 45 below 56 What would you like to do? add 23 below 56 What would you like to do? summation Sum of all nodes: 124
คำอธิบาย
- Class
TreeNodeแทนโหนด มี key และ list ของ children sum_all_nodes()ใช้ recursion: ผลรวม = key ของตัวเอง + ผลรวมของทุก child- โปรแกรมให้สร้างต้นไม้แบบโต้ตอบ แล้วคำนวณผลรวม
