Truyền tải sau đơn hàng DSA
Truyền tải cây nhị phân theo thứ tự sau
Traversal theo thứ tự sau là một loại Tìm kiếm theo chiều sâu, trong đó mỗi nút được truy cập theo một thứ tự nhất định. Đọc thêm về việc duyệt cây nhị phân nói chung tại đây .
Thực hiện duyệt thứ tự sau trên cây nhị phân có thể được hình dung như thế này:
Kết quả:
Truyền tải theo thứ tự sau hoạt động bằng cách thực hiện đệ quy Truyền tải theo thứ tự sau của cây con bên trái và cây con bên phải, sau đó là truy cập vào nút gốc. Nó được sử dụng để xóa cây, ký hiệu sửa lỗi của cây biểu thức, v.v.
Điều tạo nên "bài đăng" truyền tải này là việc truy cập một nút được thực hiện "sau khi" các nút con trái và phải được gọi đệ quy.
Đây là cách mã cho Traversal đặt hàng sau trông như thế nào:
Ví dụ
Trăn:
def postOrderTraversal(node):
if node is None:
return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print(node.data, end=", ")
Chạy ví dụ » Hàm postOrderTraversal()
tiếp tục duyệt cây con bên trái theo cách đệ quy (dòng 4), cho đến khi trả về None
khi nút con trái của C được gọi làm đối số node
.
Sau khi nút con bên trái của C trả về None
, dòng 5 chạy và nút con bên phải của C trả về None
, sau đó chữ 'C' được in (dòng 6).
Điều này có nghĩa là C được truy cập hoặc in "sau khi" các nút con bên trái và bên phải của nó được duyệt qua, đó là lý do tại sao nó được gọi là duyệt theo thứ tự "đăng".
Hàm postOrderTraversal()
tiếp tục truyền trở lại các lệnh gọi hàm đệ quy trước đó, do đó nút tiếp theo sẽ được in là 'D', sau đó là 'A'.
Hàm tiếp tục truyền ngược lại và in các nút cho đến khi tất cả các nút được in hoặc truy cập.