Tra cứu cây theo trật tự bằng clojure.zip để chỉnh sửa các nút

Question

Tôi có một cây được biểu thị dưới dạng vectơ lồng nhau. Tôi muốn có một sự tổng quát của indexed cho cây, cho thấy chỉ số của mỗi nút như thế này,

(visit 42); => [0 42] 
(visit [6 7]); => [0 
       ;  [[0 6] 
       ;  [1 7]]] 

Việc thực hiện ngây thơ sẽ sử dụng clojure.zip trực tiếp (as already asked here)

(defn visit [tree] 
    (loop [loc (vector-zip tree)] 
    (if (end? loc) 
     (root loc) 
     (recur 
     (next (edit loC#(conj 
          [(count (lefts loc))] 
          %))))))) 

Nhưng định kỳ với clojure.zip/next thực hiện quá trình truyền tải theo thứ tự trước, dẫn đến vòng lặp vô hạn trong trường hợp này (các nút chưa được xác định nhận được conj biến thành một vector [:found] vô hạn). Một cách tiếp cận khác sẽ sử dụng clojure.walk/postwalk, nhưng nó không cung cấp thông tin cấu trúc, chẳng hạn như chỉ mục.

Bạn sẽ triển khai điều này bằng cách nào? Có một số postorder-next cho zip có thể giải quyết ngay lập tức không?

Answer 1

Tôi không chắc liệu tôi có hiểu những gì bạn đang cố gắng làm hay không, nhưng các ví dụ cho tôi biết rằng các chỉ số được gán cho các nút tương ứng với số lượng anh chị em ruột của họ (kể từ ví dụ thứ hai nút và con số 6 được gắn nhãn với số 0). Cập nhật: Rõ ràng tôi chỉ đơn giản là misread ví dụ visit lần đầu tiên vòng - nó làm cho ý định rõ ràng đủ ... May mắn thay bây giờ mà tôi đọc nó đúng có vẻ như với tôi rằng câu trả lời dưới đây là chính xác.

Nếu điều đó là đúng, đây là một giải pháp dựa trên clojure.walk/postwalk:

(defn index-vec-tree [vt] 
    [0 (walk/postwalk 
     (fn [node] 
     (if-not (vector? node) 
      node 
      (vec (map-indexed vector node)))) 
     vt)]) 

Với các ví dụ:

user> (index-vec-tree [6 7]) 
[0 [[0 6] [1 7]]] 
user> (index-vec-tree 42) 
[0 42] 

Cập nhật: Một giải pháp đơn giản sử dụng map-indexed (có sẵn trong 1.2 ; sử dụng map + clojure.contrib.seq-utils/indexed trong 1.1):

(defn index-vec-tree [vt] 
    (letfn [(iter [i vt] [i (if (vector? vt) 
           (vec (map-indexed iter vt)) 
           vt)])] 
    (iter 0 vt)))