20

私の場合はベクトルですが、この投稿の推奨事項に従って定義されたツリーがあるとします。これは問題にならないことを願っています（Programming Clojureの本のベクトルです）。

(def tree [1 [[2 [4] [5]] [3 [6]]]])

これは次のようになります。

      1
     / \
    2   3
   / \  |
  4   5 6

ここで、キューなどの従来の手段を使用せずに、ツリーを幅優先でトラバースし、代わりにスタックのみを使用して情報を渡したいと思います。これが最も簡単なルートではないことは知っていますが、私は主に運動としてそれを行っています。また、この時点では、コレクションを返す予定はありません（後で演習として理解します）。代わりに、ノードを移動しながらノードを印刷します。

私の現在の解決策（Clojureから始めたばかりですが、いいですね）：

(defn breadth-recur
  [queue]
  (if (empty? queue)
    (println "Done!")
    (let [collections (first (filter coll? queue))]
      (do
        ; print out nodes on the current level, they will not be wrapped'
        ; in a [] vector and thus coll? will return false
        (doseq [node queue] (if (not (coll? node)) (println node)))
        (recur (reduce conj (first collections) (rest collections)))))))

最後の行は意図したとおりに機能しておらず、修正方法に困惑しています。私は自分が何を望んでいるのかを正確に知っています。ベクトルの各レイヤーをはがし、結果を連結して繰り返しに渡す必要があります。

私が見ている問題は主に：

IllegalArgumentException Don't know how to create ISeq from: java.lang.Long

基本的に、 conjはlongにベクトルを追加するのが好きではありません。conjをconcatと交換すると、連結している2つの項目のいずれかがベクトルでない場合に失敗します。conjとconcatの両方が直面すると失敗します：

[2 [4] [5] [3 [6]]]

ここでは、両方の位置のベクトルとプリミティブの両方で機能する、本当に基本的な操作が欠けているように感じます。

助言がありますか？

編集1：

ツリーは実際には次のようになります（Joostに感謝します！）：

(def tree [1 [2 [4] [5]] [3 [6]]])

ただし、幅優先の解決策はまだ見つかりません。

4

4 に答える 4

23

明らかに幅優先の解決策はまだ投稿されていないので、ここに単純なアルゴリズムがあり、最初に熱心に実装され、次に怠惰になるように変換されます。

(defn bfs-eager [tree]
  (loop [ret [], queue (conj clojure.lang.PersistentQueue/EMPTY tree)]
    (if (seq queue)
      (let [[node & children] (peek queue)]
        (recur (conj ret node) (into (pop queue) children)))
      ret)))

(defn bfs-lazy [tree]
  ((fn step [queue]
     (lazy-seq
      (when (seq queue)
        (let [[node & children] (peek queue)]
          (cons node
                (step (into (pop queue) children)))))))
   (conj clojure.lang.PersistentQueue/EMPTY tree)))
于 2012-07-11T05:51:39.450 に答える
13

ツリーデータが正しくありません。そのはず[1 [2 [4] [5]] [3 [6]]]

また、ツリートラバーサルと印刷を組み合わせて、結果を作成します。難しい部分を個別に行うことに集中すると、物事はより簡単になります。

(def tree [1 [2 [4] [5]] [3 [6]]])

これは深さ優先であることに注意してください。下記参照

(defn bf "return elements in tree, breath-first"
   [[el left right]] ;; a tree is a seq of one element,
                     ;; followed by left and right child trees
   (if el
     (concat [el] (bf left) (bf right))))

(bf tree)
=> (1 2 4 5 3 6)

正しいバージョン

(defn bf [& roots] 
   (if (seq roots) 
       (concat (map first roots) ;; values in roots
               (apply bf (mapcat rest roots))))) ;; recursively for children

(bf tree)
=> (1 2 3 4 5 6)
于 2012-07-10T09:04:54.627 に答える
1

これは役立つかもしれません。私は、ツリーが対称であり、幅優先探索を使用したかどうかを評価するアルゴリズムを作成していました。

(defn node-values [nodes]
    (map first nodes))

(defn node-children [nodes]
  (mapcat next nodes))

(defn depth-traversal [nodes]
    (if (not (empty? nodes))
        (cons (node-values nodes) (depth-traversal (node-children nodes)))))

(defn tree-symmetric? [tree]
    (every?
        (fn [depth] (= depth (reverse depth)))
        (depth-traversal (list tree))))

(def tree '(1 (2 (3) (4)) (2 (4) (3))))
(node-values (list tree)) ; (1)
(node-children (list tree)) ; ((2 (3) (4)) (2 (4) (3)))
(depth-traversal (list tree)) ; ((1) (2 2) (3 4 4 3))
(tree-symmetric? tree) ; true
于 2013-10-25T20:09:16.970 に答える
0

reduce上記の場合、との多くの組み合わせconjを単一の呼び出しに置き換えることができますinto。reduceを使用すると、接続詞を幸せにするために、reduceに最初の空のベクトルを渡す必要があります。

于 2012-07-10T08:55:54.390 に答える