Dường như với tôi giống như bạn khá nhiều, nhưng chỉ cần một chút trợ giúp với các chi tiết. Vì vậy, giả sử bạn có một số cấu trúc nút và chức năng sau để hoạt động trên nó:
(left-subtree [node]) - trả về cây con trái của node, hoặc nil nếu node không có cây con trái(right-subtree [node]) - trả về cây con phải của node hoặc nil nếu node không có cây con phù hợp.(value [node]) - trả về giá trị gắn liền với node(leaf? [node]) - trả true nếu node là một chiếc lá, nếu không false.
Bây giờ chúng ta hãy viết một hàm without-root mà phải mất một (sub) cây và trả về một cây mới có chứa tất cả mọi thứ trong cây gốc trừ nút gốc của nó:
(defn without-root [node]
(cond (leaf? node) nil ; resulting tree is the empty tree, return nil
(and (left-subtree node) ; two children, "difficult" case
(right-subtree node)) (handle-difficult-case node)
;; cases for single child
(left-subtree node) (left-subtree node)
(right-subtree node) (right-subtree node)))
Như bạn nêu trong câu hỏi, trường hợp "khó" là khi node có hai con. Vì vậy, tôi đã quyết định chia nó ra thành một chức năng riêng biệt để tạo điều kiện thảo luận.
Vì vậy, hãy nói về handle-difficult-case. Vì có hai đứa con, chúng ta bằng cách nào đó cần phải kết hợp chúng thành một cây duy nhất. Nếu bạn đọc Wikipedia nói gì về BST Deletion, về cơ bản bạn muốn chọn người tiền nhiệm hoặc người thừa kế theo thứ tự (nghĩa là nút ngoài cùng bên phải của cây con trái hoặc nút ngoài cùng bên trái của cây con bên phải) và biến nó thành thư mục gốc mới . Nó không quan trọng bạn chọn cái nào - dù là ai cũng sẽ làm. Vì mục đích của cuộc thảo luận này, chúng ta sẽ chọn nút cao nhất của cây con trái.
Bây giờ chúng ta có thể viết một hàm mới, without-rightmost-node, có thể chấp nhận một cây và trả về một cây mới mà không có nút ngoài cùng bên phải của nó. Tuy nhiên, chúng tôi cũng cần giá trị được lưu trữ trong nút đó. Vì vậy, chúng ta sẽ cần phải gọi một cách độc lập một số chức năng find-rightmost-node để nhận giá trị của nó (sẽ không hiệu quả) hoặc trả về giá trị cùng với cây mới (sẽ làm lệch mục đích của hàm). Thay vào đó, hãy viết một hàm chấp nhận một cây và trả về một cây mới tương đương với cây gốc, ngoại trừ gốc của nó là nút ngoài cùng bên phải của cây gốc. Để giải trí, hãy gọi hàm này percolate-rightmost-node vì, như chúng ta sẽ thấy, nút ngoài cùng bên phải sẽ đệ quy "bong bóng lên" lên trên cùng của cây (phụ).
(defn percolate-rightmost-node [node]
(if-let [right-side (right-subtree node)]
;; then (recurse down the right side)
(let [percolated (percolate-rightmost-node right-side)]
;; Construct a new tree from the result.
(with-left-subtree percolated
(with-right-subtree node (left-subtree percolated))))
;; else (we are at the rightmost node -- return it!)
node))
Tôi cảm thấy mặt "sau đó" của biểu thức if-let không rõ ràng, vì vậy hãy để tôi giải thích một chút. Về cơ bản, chúng tôi lấy các phụ tùng percolated, có được subtree trái (đó là con duy nhất của percolated) và thay thế nó cho subtree quyền của node. Sau đó chúng tôi lấy kết quả đó và thay thế nó cho cây con trái của percolated (hiệu quả tái rễ cây), tạo ra kết quả cuối cùng.
Đầu ra của percolate-rightmost-node sẽ chỉ có một cây con trái - nó sẽ không bao giờ có một cây con phù hợp. Vì vậy, sau khi kết quả đã hoàn thành "sủi bọt", chúng tôi chỉ cần cung cấp cho nó một cây con ngay. Do đó, chúng tôi có thể triển khai handle-difficult-case là:
(defn handle-difficult-case [node]
(let [percolated (-> node ; Find the rightmost node of the left
(left-subtree) ; subtree and "percolate" it to the top
(percolate-rightmost-node))]
;; Now take the percolated tree. Its right subtree is empty,
;; so substitute in the right subtree of node.
(with-right-subtree percolated
(right-subtree node))))
Và điều đó phải là vậy. Tất nhiên, bạn sẽ cần phải điều chỉnh điều này để mã của bạn (tối thiểu, hoặc là nội tuyến handle-difficult-case hoặc cung cấp cho nó một tên thích hợp). Nhưng hy vọng rằng sẽ giúp bạn bắt đầu.
Làm trống caveat: Tôi đã không cố gắng kiểm tra mã được đưa ra trong câu trả lời này. Sửa chữa được hoan nghênh!
Bạn đã xem xét dây kéo chưa? –
@ lgrapenthin, bạn có nghĩa là sử dụng dây kéo để lưu trữ thông tin? – Landey
tôi thành thật không có đầu mối nào cả về cách tạo lại cây trong khi chia sẻ dữ liệu. @ lgrapenthin – Landey