5

我有一棵树表示为嵌套向量。我想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))] 
                           %)))))))

但是 recurring withclojure.zip/next会执行前序遍历，在这种情况下会导致无限循环（未访问的节点被无限地conj编入[:found]向量中）。另一种方法是使用clojure.walk/postwalk，但它不提供结构信息，例如索引。

你将如何实现这一点？是否有一个postorder-nextfor zip 可以立即解决它？

4

1 回答 1

4

我不确定我是否理解您要执行的操作，但是这些示例向我表明分配给节点的索引对应于其左兄弟姐妹的数量（因为在第二个示例中，根节点和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)))
于 2010-07-30T19:28:34.293 回答