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

发布于 2024-09-12 04:28:48 字数 810 浏览 4 评论 0原文

我有一棵表示为嵌套向量的树。我想要对树进行 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，但它不提供结构信息，例如索引。

你会如何实施这个？是否有一个 zip 的 postorder-next 可以立即解决这个问题？

原文

I have a tree represented as a nested vector. I want to have a generalization of indexed for trees, showing the index of each node like this,

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

The naive implementation would use clojure.zip directly (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))] 
                           %)))))))

But recurring with clojure.zip/next performs a preorder traversal, resulting in an infinite loop in this case (unvisited nodes get conjed into a [:found] vector infinitely). Another approach would be using clojure.walk/postwalk, but it doesn't provide structural information, such as index.

How would you implement this? Is there a postorder-next for zip that would solve it right away?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十二 2024-09-19 04:28:48

我不确定我是否理解您要做什么，但这些示例向我表明分配给节点的索引对应于它们左兄弟的数量（因为在第二个示例中根节点和 < code>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)))

I'm not sure if I understand what you're trying to do, but the examples suggest to me that the indices assigned to the nodes correspond to the number of their left siblings (since in the second example both the root node and the 6 child are labelled with 0). Update: Apparently I simply misread the visit example the first time round -- it makes the intention clear enough... Fortunately now that I read it properly it seems to me that the answer below is correct.

If that is correct, this is a clojure.walk/postwalk-based solution:

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

With the given examples:

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

Update: A simple solution using map-indexed (available in 1.2; use map + clojure.contrib.seq-utils/indexed in 1.1):

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

回复收藏 0 原文

~没有更多了~