algorithm - ¿Perdido con un cruce de árbol funcional en primer plano en Clojure?

functional-programming

Question

Digamos que tengo un árbol definido según la recomendación en esta publicación , aunque es un vector en mi caso, que con suerte no debería importar (son vectores en el libro de programación de Clojure):

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

que debería ser algo así como:

      1
     / /
    2   3
   / /  |
  4   5 6

Ahora, me gustaría hacer un recorrido transversal del árbol sin amplitud, sin ninguno de los medios tradicionales, como la cola, y en su lugar utilizar exclusivamente la pila para pasar información. Sé que esta no es la ruta más fácil, pero lo hago principalmente como ejercicio. Además, en este punto no estoy planeando devolver una colección (lo averiguaré luego como ejercicio), sino que simplemente imprimiré los nodos mientras los recorro.

Mi solución actual (recién comenzando con Clojure, se agradable):

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

La última línea no está funcionando como estaba previsto y estoy perplejo sobre cómo solucionarlo. Sé exactamente lo que quiero: necesito pelar cada capa de vectores y luego concatenar los resultados para pasar a recurrir.

El problema que estoy viendo es principalmente un:

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

Básicamente a conj no le gusta anexar un vector a un largo, y si cambio el conj para concat , entonces fallaré cuando uno de los dos elementos que estoy concatenando no sea un vector. Ambos conj y concat fallan al enfrentar:

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

Siento que me falta una operación realmente básica aquí que funcionaría tanto en vectores como en primitivos en ambas posiciones.

¿Alguna sugerencia?

Editar 1:

El árbol debería ser (¡gracias Joost!):

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

Sin embargo, todavía no hemos encontrado la primera solución de amplitud .

Answer 1

Dado que aparentemente todavía no hay una solución de amplitud publicada, aquí hay un algoritmo simple, implementado primero con entusiasmo, y luego transformado para ser perezoso:

(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

Esto podría ayudar, estaba creando un algoritmo para evaluar si un árbol es simétrico y si se usa un recorrido transversal en amplitud:

(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

Answer 3

Sus datos de árbol son incorrectos. Debería ser [1 [2 [4] [5]] [3 [6]]]

Además, está mezclando el recorrido del árbol con la impresión y creando un resultado. Las cosas se simplifican si te concentras en hacer la parte difícil por separado:

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

NOTA: ESTE ES DEPTH-FIRST. VEA ABAJO

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

VERSIÓN CORRECTA

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

Answer 4

muchas combinaciones de reduce y conj pueden ser reemplazadas por single into call en el caso anterior con reduce puede necesitar pasar un vector vacío inicial para reducir para hacer que la conjunción sea feliz.