Clojure中的树遍历

Question

考虑一棵树，它由以下递归定义确定：

一棵树应该是一个包含两个元素的向量：第一个元素是数字，第二个元素是树列表或空值。

下面的Clojure数据结构就是一个例子：

(def tree '[9 ([4 nil]
               [6 nil]
               [2 ([55 nil]
                   [22 nil]
                   [3 ([5 nil])])]
               [67 ([44 nil])])])

这个结构应该转换成一个所有可能的向下连接的列表，可以从任何节点到其子节点进行连接。 连接应表示为包含父节点值后跟子节点值的向量。 顺序不重要：

(def result '([9 4]
              [9 6]
              [9 2]
              [2 55]
              [2 22]
              [2 3]
              [3 5]
              [9 67]
              [67 44])

我想到了这个解决方案：

(defn get-connections [[x xs]]
  (concat (map #(vector x (first %)) xs)
          (mapcat get-connections xs)))

并且，事实上：

(= (sort result)
   (sort (get-connections tree)))
;; true

然而，有没有更好的方法只使用Clojure来实现呢？ 在这个方法中，我遍历了每个节点的两个子节点，这应该被避免。在这种情况下，尾递归并不是必要的，因此一个简单的递归版本就可以了。

此外，我对哪些更高级的抽象方法用于解决这个问题很感兴趣。Zipper或Clojure/Walk怎么样？最后：这些技术中哪些也适用于ClojureScript？

- Anton Harald

Answer 1

您可以尝试使用列表推导式 + tree-seq 的组合：

user> (for [[value children] (tree-seq coll? second tree)
            [child-value] children]
        [value child-value])

;;=> ([9 4] [9 6] [9 2] [9 67] [2 55] [2 22] [2 3] [3 5] [67 44])

这应该在cljs中可用。

据我所知，zippers和clojure.walk都可在clojurescript中使用，但实际上你不需要它们来完成这个微不足道的任务。我猜tree-seq更具惯用性。

至于双遍历，你可以轻松地将其重新排列成单一遍历，如下所示：

(defn get-connections [[x xs]]
  (mapcat #(cons [x (first %)] (get-connections %)) xs))

user> (get-connections tree)
;;=> ([9 4] [9 6] [9 2] [2 55] [2 22] [2 3] [3 5] [9 67] [67 44])

然后，你可以添加"懒惰"来使这个解决方案真正符合惯用法：

(defn get-connections [[x xs]]
  (mapcat #(lazy-seq (cons [x (first %)] (get-connections %))) xs))

- leetwinski

---

之前没有时间查看这个答案。非常感谢您提供的出色解决方案，它们完美地解决了我的问题。 - Anton Harald