Xây dựng một cây

Question

Làm thế nào tôi có thể xây dựng một cây được sắp xếp theo thứ tự inorder và preorder? Tôi chỉ đang tìm một thuật toán hiệu quả.

Answer 1

Bản sao trắng trợn và dán từ Sun's (Oracle now, I guess...) forum:

Câu hỏi:
Ai có thể giúp tôi làm thế nào để xây dựng cây nhị phân từ inorder và traversals postorder, tôi chỉ muốn biết các thuật toán để rằng tôi có thể áp dụng nó.

Trả lời:
Hãy p_1, p_2...p_n là traversal postorder và để i_1, i_2...i_n là traversal inorder. Từ quá trình truyền tải thứ tự, chúng ta biết rằng gốc của cây là p_n. Tìm phần tử này trong quá trình truyền tải theo thứ tự, giả sử i_1, i_2...i_k-1p_ni_k+1...i_n. Từ quá trình truyền tải theo thứ tự, chúng tôi tìm thấy tất cả các phần tử trong nhánh trái, tức là i_1, i_2...i_k-1 và ở bên phải, tức là i_k+1...i_n tương ứng.

Xóa phần tử p_n (và phần tử i_k==p_n). Tìm các yếu tố ngoài cùng bên phải p_j trong p_1, p_2...p_j...p_n-1 nơi p_j là một yếu tố trong i_1, i_2 ... i_k-1. Đây là gốc của cây con trái của cây gốc. Chia p_1, p_2...p_j và p_j+1 ... p_n-1 và i_1, i_2...i_k-1 và i_k+1...i_n. Bây giờ bạn có hai chuỗi đại diện cho thứ tự postorder và inorder traversal của hai subtrees của cây ban đầu là .

Tác giả: JosAH.

Tôi đã triển khai thuật toán một lần theo hướng dẫn của Jos 'và nó hoạt động hoàn hảo!

Answer 2

Vì đây là bài tập về nhà, tôi sẽ không cung cấp cho bạn câu trả lời đầy đủ, nhưng hy vọng, đủ để giúp bạn di chuyển.

Hãy tưởng tượng bạn có quá trình truyền tải trước, ví dụ: this cây.

Giao lộ cung cấp cho bạn 2-7-2-6-5-11-5 ... v.v. Lưu ý rằng 5 thực sự là con phải của gốc.Rõ ràng, bạn không thể nói rằng chỉ cần nhìn vào các con số, do đó, hoặc là bạn sẽ được thông báo về cấu trúc của cây, hoặc bạn cần phải lưu trữ một số dữ liệu bổ sung (ví dụ, liệu một nút có phải là trái hay không?). ví dụ như trẻ em hoặc trẻ em phải).

Phân tích cú pháp cây chỉ đơn giản là một hàm đệ quy lấy lượt duyệt trước làm đầu vào (suy nghĩ về phạm vi của bạn khi bạn chuyển đầu vào). Như tôi đã đề cập trước đó, quá trình truyền tải đơn đặt hàng trước của bạn phải có một số dữ liệu bổ sung được đính kèm.

---

Hiệu quả:

cân nhắc bao nhiêu lần mỗi nút được truy cập khi bạn xây dựng cây này, mà còn xem xét các hoạt động của đọc đầu vào. Có cách nào để tổ chức lại đầu vào nhanh hơn bạn có thể xây dựng cây không? Bạn sẽ phải sử dụng cấu trúc nào nếu bạn cần thao tác dữ liệu.

---

Thứ tự: Bạn sẽ cần ý tưởng tương tự để giúp bạn vượt qua nó, vì vậy tôi sẽ không đề cập đến nó. Tôi chắc chắn một người khác sẽ, nếu bạn đang tuyệt vọng cho nó.