แสดงโหนดของ Tree ด้วย BFS Traversal ใน Python

Breadth-First Search (BFS) เรียงโหนดตามระดับ (Level Order) ใช้ Queue เก็บโหนดรอประมวลผล

ตัวอย่างโค้ด

from collections import deque

class TreeNode:
    def __init__(self, data):
        self.key = data
        self.left = None
        self.right = None
    
    def bfs(self):
        q = deque([self])
        while q:
            node = q.popleft()
            print(node.key, end=' ')
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

# Build tree
root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(1)
root.left.right = TreeNode(5)

print("BFS Traversal:")
root.bfs()

ผลลัพธ์

BFS Traversal: 6 4 9 1 5

คำอธิบาย

• เริ่มจาก root ใส่ queue

• Dequeue โหนด พิมพ์ค่า Enqueue ลูกซ้ายและลูกขวา (ถ้ามี)

• ทำซ้ำจน queue ว่าง

• ลำดับ: ระดับ 0 (6) → ระดับ 1 (4,9) → ระดับ 2 (1,5)

• ใช้ deque เพื่อ O(1) popleft