使用clojure.zip对Postorder树进行遍历以编辑节点

Question

我有一个表示为嵌套向量的树.我想indexed对树进行泛化,显示每个节点的索引,如下所示,

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

天真的实现将直接使用clojure.zip(如此处已经提到的那样)

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

但是反复出现clojure.zip/next执行前序遍历,在这种情况下导致无限循环(未访问的节点无限地conj进入[: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)))