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

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 问题，但这样做有点麻烦。我们可以在那里留下其他东西来指示还有更多工作要做(例如零参数函数)，而不是立即使用构造树处理每个叶子，然后再执行另一个处理步骤来处理每个叶子，不断处理，直到没有任何工作要做。可以在恒定的堆栈空间中执行此操作，但除非您期望非常高的树，否则可能没有必要(即使 clojure.walk/prewalk 和 postwalk 也会溢出堆放在足够高的树上)。