Tổng quan
Duyệt tiền thứ tự (preorder) là cách duyệt theo chiều sâu, thăm các nút theo thứ tự Gốc, Trái, Phải. Nó xử lý một nút trước khi đi xuống bất kỳ cây con nào của nó.
Vì gốc được phát ra đầu tiên, preorder ghi lại hình dạng cây từ trên xuống, nên đây là lựa chọn tiêu chuẩn để sao chép cây hoặc chuỗi hóa nó thành dạng có thể dựng lại đúng cấu trúc ban đầu.
Duyệt Preorder hoạt động thế nào?
- Thăm (xử lý) nút hiện tại trước tiên.
- Duyệt đệ quy toàn bộ cây con trái.
- Duyệt đệ quy toàn bộ cây con phải.
- Trả về khi gặp cây con rỗng (null); gốc luôn xuất hiện trước các nút con cháu của nó.
Khi nào nên dùng?
- Tạo bản sao sâu của cây, vì nút cha được tạo trước các nút con.
- Chuỗi hóa cây ra đĩa hoặc mạng để có thể dựng lại y hệt.
- Xuất ký pháp tiền tố (Ba Lan) từ cây biểu thức.
Phân tích độ phức tạp
Duyệt preorder chạm tới mỗi trong n nút một lần, nên chạy trong O(n) thời gian. Ngăn xếp đệ quy bị chặn bởi chiều cao cây h, cho O(h) bộ nhớ — O(log n) khi cân bằng và O(n) với cây suy biến.
Câu hỏi thường gặp
Vì sao preorder được ưa dùng để chuỗi hóa cây?
Nó ghi mỗi nút cha trước các nút con, nên bên đọc có thể tạo lại nút từ trên xuống và gắn con dần dần — việc ghi dấu null giúp dựng lại đúng cấu trúc một cách rõ ràng.
Preorder khác inorder và postorder thế nào?
Cả ba đều là duyệt theo chiều sâu và O(n); chúng chỉ khác ở thời điểm thăm gốc — đầu tiên với preorder, giữa hai cây con với inorder, và cuối cùng với postorder.