用clojure.zip编辑节点的后序遍历树

Question

我有一棵树表示为嵌套矢量。我希望有indexed树木，呈现出这样每个节点的指数的推广，

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

天真的实施将使用clojure.zip直接（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/next复发执行前序遍历，导致在这种情况下的无限循环（未访问节点无限地获取[:found]矢量）。另一种方法是使用clojure.walk/postwalk，但它不提供结构信息，如索引。

你将如何实现这一点？有没有一个postorder-next的拉链，可以马上解决它？

Answer 1

我不知道我是否明白你想要做什么，但这些例子告诉我，分配给节点的索引对应于它们的左边兄弟的数目（因为在第二个例子中，根节点和6孩子被标记为0）。 更新：显然，我只是第一次误读visit示例 - 它意图明确足够清楚......幸运的是，现在我正确阅读它，在我看来，下面的答案是正确的。

如果这是正确的，这是一个基于clojure.walk/postwalk溶液：

(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] 

更新：使用map-indexed的简单溶液（在1.2可用;在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)))