从节点列表、父元素列表构建树

Question

我有一个节点列表，每个节点都有一个父节点，我想用这些节点构造一棵树。

(def elems '[{:node A :parent nil} {:node B :parent A} {:node C :parent A} {:node D :parent C}])
(build-tree elems)
=> (A (B) (C (D)))

目前我有这样的代码：

(defn root-node [elems]
  (:node (first (remove :parent elems))))

(defn children [elems root]
  (map :node (filter #(= root (:parent %)) elems)))

(defn create-sub-tree [elems root-node]
  (conj (map #(create-sub-tree elems %) (children elems root-node)) root-node))

(defn build-tree [elems]
  (create-sub-tree elems (root-node elems)))

在这个解决方案中，使用了递归，但没有使用循环递归语法。这是不好的，因为代码不能被优化和一个StackOverflowError is possible。

似乎我只能在每个步骤中有一个递归的情况下才能使用recur。

在树的情况下，我对节点的每个子节点都有一个递归。

我正在寻找一个调整后的解决方案，不会遇到这个问题。

如果你对这个问题有一个完全不同的解决方案，我很乐意看到它。

我读过一些关于zipper的文章，也许这是一种更好的建树方式。

Answer 1

这是我想要的解决方案。它仍然对StackOverflowError很敏感，但只适用于非常“高”的树。

(defn build-tree [elems]
  (let [vec-conj (fnil conj [])
        adj-map (reduce (fn [acc {:keys [node parent]}]
                          (update-in acc [parent] vec-conj node))
                        {} elems)
        construct-tree (fn construct-tree [node]
                         (cons node
                               (map construct-tree
                                    (get adj-map node))))
        tree (construct-tree nil)]
    (assert (= (count tree) 2) "Must only have one root node")
    (second tree)))

我们可以删除StackOverflowError问题，但这样做有点痛苦。与使用construct-tree立即处理每个叶不同，我们可以留下一些其他的东西来指示有更多的工作要做(比如零参数函数)，然后执行另一个处理步骤来处理每个叶，不断地处理，直到没有剩余的工作要做。在恒定的堆栈空间中实现这一点是可能的，但除非您期望的是非常高的树，否则这可能是不必要的(即使是clojure.walk/prewalk和postwalk也会在足够高的树上溢出堆栈)。