Duyệt cây theo chiều rộng (level-order) dùng queue.
Ví dụ
class TreeNode:
def __init__(self, data):
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:
res = child.find_node(key)
if res:
return res
return None
def bfs(self):
queue = [self]
while queue:
node = queue.pop(0)
print(node.key, end=' ')
for child in node.children:
queue.append(child)
root = None
while True:
cmd = input("Cmd (add/bfs/quit): ").split()
if not cmd: continue
if cmd[0] == 'add':
val = int(cmd[1])
node = TreeNode(val)
if cmd[2] == 'at':
root = node
else:
parent = root.find_node(int(cmd[3]))
if parent:
parent.add_child(node)
elif cmd[0] == 'bfs':
if root:
print("BFS:", end=' ')
root.bfs()
print()
else:
print("Cây rỗng")
elif cmd[0] == 'quit':
break
Kết quả
Cmd (add/bfs/quit): add 6 at root Cmd (add/bfs/quit): add 4 below 6 Cmd (add/bfs/quit): add 9 below 4 Cmd (add/bfs/quit): bfs BFS: 6 4 9 Cmd (add/bfs/quit): quit
Giải thích
- Queue khởi tạo với root.
- Lặp: pop đầu, in giá trị, push tất cả con vào cuối.
- Đảm bảo duyệt theo cấp độ (level order).
- Menu tương tác tương tự bài trước.