代码之家 › 专栏 › 技术社区 › Adam Schmideg

使用clojure.zip进行后序树遍历以编辑节点

zipper traversal tree clojure

5

Adam Schmideg · 技术社区 · 14 年前

我有一个用嵌套向量表示的树。我想概括一下 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 执行预排序遍历,在这种情况下会产生无限循环(未访问的节点获取 conj 变成一个 [:found] 矢量无限)。另一种方法是 clojure.walk/postwalk 但它不提供结构信息,如索引。

您将如何实现这一点?有没有 postorder-next 对于能马上解决问题的Zip?

1 回复 | 直到 14 年前

1

4

MichaÅ Marczyk 14 年前

我不确定我是否理解您要做什么,但是示例向我建议,分配给节点的索引对应于它们的左兄弟(因为在第二个示例中,根节点和 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中可用;使用 map + clojure.contrib.seq-utils/indexed 1.1):

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