3

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

(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 是可能的。
如果我在每个步骤中都有一个递归，我似乎只能使用 recur。
在树的情况下，我对节点的每个子节点都有一个递归。

我正在寻找不会遇到此问题的调整解决方案。
如果您对此问题有完全不同的解决方案，我很乐意看到它。
我读了一些关于 zipper 的文章，也许这是构建树的更好方法。

4

1 回答 1

2

这是我会采用的解决方案。它仍然容易受到 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我们可以留下其他东西来表明还有更多工作要做（比如零 arg 函数），然后再做一个处理步骤来处理每个叶子，不断处理直到没有工作要做. 可以在恒定的堆栈空间中执行此操作，但除非您期待非常高的树，否则它可能是不必要的（即使clojure.walk/prewalk并且postwalk会在足够高的树上溢出堆栈）。

于 2013-06-22T03:16:18.110 回答