Tổng quan
Duyệt theo mức (level-order) là tìm kiếm theo chiều rộng (BFS) trên cây nhị phân: nó thăm tất cả các nút ở độ sâu 0, rồi tất cả ở độ sâu 1, và cứ thế, đi theo từng mức từ trên xuống dưới và từ trái sang phải.
Khác với các cách duyệt theo chiều sâu, nó vốn có tính lặp và được điều khiển bằng hàng đợi thay vì đệ quy, nên là phương pháp ưu tiên khi cần kết quả nhóm theo mức hoặc đường đi ngắn nhất tính theo số cạnh.
Duyệt theo tầng hoạt động thế nào?
- Đưa nút gốc vào một hàng đợi ban đầu rỗng.
- Lấy nút ở đầu hàng đợi ra và thăm (xử lý) nó.
- Đưa nút con trái rồi nút con phải của nó vào hàng đợi, nếu tồn tại.
- Lặp lại đến khi hàng đợi rỗng; các nút đi ra đúng theo thứ tự mức.
Khi nào nên dùng?
- In hoặc nhóm cây theo từng mức, ví dụ để vẽ sơ đồ dễ đọc.
- Tìm đường đi ngắn nhất theo số cạnh từ gốc, hoặc độ sâu nhỏ nhất của một nút.
- Tính kết quả theo từng mức như giá trị lớn nhất mỗi mức hoặc khung nhìn từ bên phải.
Phân tích độ phức tạp
Mỗi nút được đưa vào và lấy ra khỏi hàng đợi đúng một lần, nên level-order chạy trong O(n) thời gian. Bộ nhớ của nó là O(w), với w là chiều rộng lớn nhất của cây — số nút nhiều nhất trên một mức bất kỳ, có thể lên tới khoảng n/2 ở gần đáy của một cây đầy.
Câu hỏi thường gặp
Vì sao dùng hàng đợi thay vì ngăn xếp cho level-order?
Hàng đợi hoạt động vào-trước-ra-trước, nên các nút được xử lý theo đúng thứ tự được phát hiện — từng mức một. Ngăn xếp sẽ đảo ngược thành thứ tự theo chiều sâu.
Làm sao biết một mức kết thúc và mức tiếp theo bắt đầu?
Ghi lại kích thước hàng đợi ở đầu mỗi vòng và lấy ra đúng bấy nhiêu nút; các nút đó tạo thành một mức trọn vẹn trước khi các con của chúng tiếp quản.