难以在Clojure中使用功能广度优先树遍历？

Question

说我定义为每个在推荐树这个帖子,虽然它在我的情况下,一个载体,它希望不应该的问题(他们在编程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]]])

但是,我们仍然没有找到广泛的解决方案.

Answer 1

由于显然仍然没有发布广度优先解决方案,这里是一个简单的算法,首先急切地实现,然后转换为懒惰:

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

Answer 2

您的树数据不正确.它应该是[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)