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 が発生する可能性があるため、これは悪いことです。
各ステップで再帰が1つある場合にのみ、再帰を使用できるようです。
ツリーの場合、ノードの子ごとに再帰があります。

この問題に遭遇しないように調整されたソリューションを探しています。
この問題に対する完全に異なる解決策がある場合は、ぜひご覧ください。
ジッパーについて少し読んだことがありますが、おそらくこれはツリーを構築するためのより良い方法です。

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 に答える