Ví dụ về truyền tải cây trước/sau đặt hàng thực tế

Question

Tôi hiểu các thuật toán duyệt qua hàng đặt hàng trước, theo trật tự và sau trật tự tốt. (Reference). Tôi hiểu một vài cách sử dụng: theo thứ tự để duyệt qua cây tìm kiếm nhị phân theo thứ tự, đặt hàng trước để nhân bản một cây. Nhưng tôi không thể cho cuộc sống của tôi đi lên với một nhiệm vụ thế giới thực mà tôi cần phải vượt qua trật tự sau để hoàn thành.

Bạn có thể cho tôi ví dụ không? Và: bạn có thể cho tôi bất kỳ cách sử dụng nào tốt hơn cho việc truyền tải đơn đặt hàng trước không?

Chỉnh sửa: Có ai có thể cho tôi một ví dụ khác ngoài cây biểu thức và RPN không? Đó có thực sự là tất cả các đơn đặt hàng sau đều tốt không?

Answer 1

Topological sorting là một traversal hậu thứ tự của cây (hoặc đồ thị không chu trình có hướng).

Ý tưởng là các nút của biểu đồ thể hiện các tác vụ và một cạnh từ A đến B cho biết rằng A phải được thực hiện trước B. Một kiểu topo sẽ sắp xếp các tác vụ này theo thứ tự sao cho tất cả các phụ thuộc của một tác vụ xuất hiện sớm hơn chính tác vụ đó. Bất kỳ hệ thống xây dựng nào như UNIX make đều phải triển khai thuật toán này.

Ví dụ mà Dario đã đề cập - hủy tất cả các nút của cây bằng quản lý bộ nhớ thủ công - là một ví dụ của sự cố này. Sau khi tất cả, nhiệm vụ phá hủy một nút phụ thuộc vào sự phá hủy của con cái của nó.

Answer 2

Thứ tự bài đăng (có thể) được sử dụng bởi trình biên dịch. Xem xét một cây biểu thức cho a + b + c, ngôn ngữ máy sẽ yêu cầu một chuỗi như a b + c +. Điều này cũng được gọi là Reverse polish Notation (RPN). Trên trang Wikipedia nó nói: "RPN aka Postfix"

Yêu cầu sau cũng cần thiết để phá hủy một cây, giống như việc đặt hàng trước là cần thiết để tạo/sao chép nó.

Answer 3

Như Henk Holterman đã chỉ ra, phá hủy một cây bằng cách sử dụng quản lý bộ nhớ thủ công thường là một quá trình truyền tải theo thứ tự.

Mã giả:

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}