Clojure 中的树遍历

Question

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

树应该是两个元素的向量：第一个是数字，第二个是树列表或 nil。

下面的 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 来做到这一点？ 在该方法中，我遍历每个节点的子节点两次，应该避免这种情况。在这种特殊情况下，不需要尾递归，所以简单的递归版本就可以了。

此外，我很感兴趣可以使用哪些更高级别的抽象来解决这个问题。 Zippers 或 Clojure/Walk 怎么样？最后：ClojureScript 中也可以使用哪些技术？

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 中可用。

据我所知，拉链和 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))

Clojure 中的树遍历

Tree traversal in Clojure

tree

clojure

clojurescript