Tổng quan
Duyệt hậu thứ tự (postorder) là cách duyệt theo chiều sâu, thăm các nút theo thứ tự Trái, Phải, Gốc. Nó xử lý xong cả hai cây con trước khi chạm tới nút phía trên chúng.
Thăm các nút con trước nút cha chính là điều cần thiết khi giải phóng hoặc xóa cây, hoặc khi tính giá trị cây biểu thức, nơi các toán hạng phải được tính trước toán tử kết hợp chúng.
Duyệt Postorder hoạt động thế nào?
- Duyệt đệ quy toàn bộ cây con trái.
- Duyệt đệ quy toàn bộ cây con phải.
- Thăm (xử lý) nút hiện tại chỉ sau khi cả hai cây con đã hoàn tất.
- Trả về khi gặp cây con rỗng (null); mỗi nút được thăm sau tất cả con cháu của nó.
Khi nào nên dùng?
- Xóa hoặc giải phóng cây an toàn, giải phóng các nút con trước nút cha trỏ tới chúng.
- Tính giá trị cây biểu thức, tính các kết quả con trước khi áp dụng mỗi toán tử.
- Tính các tổng hợp từ dưới lên như kích thước cây con, chiều cao, hay dung lượng thư mục.
Phân tích độ phức tạp
Duyệt postorder xử lý mỗi trong n nút một lần, nên chạy trong O(n) thời gian. Đệ quy đi xuống tới chiều cao cây h trước khi quay lui, dùng O(h) bộ nhớ — O(log n) khi cân bằng và O(n) ở trường hợp suy biến.
Câu hỏi thường gặp
Vì sao dùng postorder để xóa cây?
Các nút con phải được giải phóng trước chính nút đó, nếu không sẽ mất các con trỏ tới chúng. Thứ tự Trái, Phải, Gốc đảm bảo mỗi nút cha chỉ bị xóa sau các cây con của nó.
Postorder tính cây biểu thức như thế nào?
Lá chứa toán hạng và nút trong chứa toán tử. Tính hai nút con trước sẽ cho giá trị của chúng, nên khi thăm một nút thì toán tử của nó có thể áp dụng ngay — đây là cách tính hậu tố (Ba Lan ngược).