노드를 편집하기 위해 clojure.zip을 사용한 Postorder tree traversal

Question

중첩 된 벡터로 표현 된 트리가 있습니다. 나는

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

순진 구현은 직접 (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))] 
          %))))))) 

을 clojure.zip 사용하지만 clojure.zip/next로 반복되는 것 같은 각 노드의 인덱스를 보여주는 나무에 대한 indexed의 일반화를 갖고 싶어 이 경우 무한 루프를 초래하는 선행 순회를 수행합니다 (방문하지 않은 노드는 conj이 무한히 [:found] 벡터가됩니다). 또 다른 방법은 clojure.walk/postwalk을 사용하는 것이지만 인덱스와 같은 구조 정보는 제공하지 않습니다.

어떻게 구현하나요? 지금 당장 해결할 수있는 zip 용 postorder-next이 있습니까?

Answer 1

당신이하려는 일을 이해할 수 있을지 모르겠지만 노드에 할당 된 색인은 왼쪽 형제의 수와 일치한다는 것을 나에게 제안합니다 (두 번째 예에서는 루트 노드 및 6 자식은 0)로 레이블됩니다. 업데이트 : 분명히 처음으로 visit 예제를 잘못 읽은 것 같습니다. 의도가 충분히 명확 해졌습니다 ... 다행히 이제는 올바르게 읽었으므로 아래 답변이 정확하다고 생각합니다. 주어진 예에

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

:

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

업데이트 : 1.2map-indexed를 사용하여 간단한 용액 (가능한 그 올바른 경우

, 이것은 clojure.walk/postwalk 기반 솔루션 ; 1.1에서 map + clojure.contrib.seq-utils/indexed을 사용하십시오.

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