代码之家 › 专栏 › 技术社区 › Konrad Garus

用共光标遍历树

clojure algorithm

Konrad Garus · 技术社区 · 14 年前

我试图用非平凡(即不是Fibonacci)但可管理的例子来理解Clojure中的corecursion。显然,用corecursion实现二叉树遍历是可能的。Wikipedia有一个Python的例子,我无法理解。

(defstruct tree :val :left :right)

(def my-tree (struct tree 1 (struct tree 2) (struct tree 3 4 5)))

(def bfs (lazy-cat [my-tree] (map #(:left %) bfs) (map #(:right %) bfs) ))

(println (take 4 bfs))

不幸的是,它似乎一直向左走,忽略了右分支。

2 回复 | 直到 14 年前

Alex Taggart 14 年前

假设Michal的代码符合您的要求,这也可以:

(defn bftrav [& trees]
  (when trees
    (concat trees 
      (->> trees
        (mapcat #(vector (:left %) (:right%)))
        (filter identity)
        (apply bftrav)))))

MichaÅ Marczyk 14 年前

bftrav 维基百科文章中的Haskell函数。请注意,它使用 letrec this Gist 最新版本。

我改变了你对 my-tree 如此解读:

(def my-tree (struct tree 1 (struct tree 2) (struct tree 3 (struct tree 4) (struct tree 5))))

还有,我的 leaf? nil 上 :left 分支意味着上 :right

(defn leaf? [t] (nil? (:left t)))

的代码 bftrav公司 具体如下:

(defn bftrav [t]
  (letrec [queue (lazy-seq (cons t (trav 1 queue)))
           trav (fn [l q]
                  (lazy-seq
                    (cond (zero? l) nil
                          (leaf? (first q)) (trav (dec l) (rest q))
                          :else (let [{:keys [left right]} (first q)]
                                  (cons left (cons right (trav (inc l) (rest q))))))))]
    queue))

user> (bftrav my-tree)
({:val 1, :left {:val 2, :left nil, :right nil}, :right {:val 3, :left {:val 4, :left nil, :right nil}, :right {:val 5, :left nil, :right nil}}} {:val 2, :left nil, :right nil} {:val 3, :left {:val 4, :left nil, :right nil}, :right {:val 5, :left nil, :right nil}} {:val 4, :left nil, :right nil} {:val 5, :left nil, :right nil})
user> (count (bftrav my-tree))
5

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前