Обход дерева с corecursion
Я пытаюсь выяснить corecursion в Clojure с нетривиальным (т.е. не Fibonacci), но управляемый, примеры. По-видимому, возможно реализовать обход двоичного дерева с corecursion. Википедия имеет пример в Python, который я не могу понять.
Как я могу реализовать его в Clojure? Скажем, я ищу BFS, но это мог быть любой порядок.
Вот то, что я имею до сих пор:
(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 ответа
Предполагая, что код Михала делает то, что вы хотите, это тоже работает:
(defn bftrav [& trees]
(when trees
(concat trees
(->> trees
(mapcat #(vector (:left %) (:right%)))
(filter identity)
(apply bftrav)))))
Это прямой перевод функции 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 подразумевает nil на ветви : 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))
Пример из REPL:
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