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)))))))

最后一行没有按预期工作，我对如何修复它感到困惑。我确切地知道我想要什么：我需要剥离每一层向量，然后将结果连接起来传递给 recur。

我看到的问题主要是：

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

基本上conj不喜欢将向量附加到 long 上，如果我将 conj 换成concat，那么当我要连接的两个项目之一不是向量时，我会失败。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在上面的例子中， and的许多组合conj可以用单个into调用替换，你可能需要传递一个初始的空向量来 reduce 以获得快乐的结合。

于 2012-07-10T08:55:54.390 回答