data structures - Representando un árbol en Clojure

data-structures

Question

¿Cuál sería una forma idiomática de representar un árbol en Clojure? P.ej:

     A
    / /
   B   C
  //    /
 D  E    F

El rendimiento no es importante y los árboles no crecerán más allá de 1000 elementos.

Answer 1

Hay una manera aterradora de hacerlo usando solo cons :

(defn mktree 
  ([label l r] (cons label (cons l r))) 
  ([leaf] (cons leaf (cons nil nil))))
(defn getlabel [t] (first t))
(defn getchildren [t] (rest t))
(defn getleft [t] (first (getchildren t)))
(defn getright [t] (rest (getchildren t)))

Tenga en cuenta que los niños no son una lista; es un par Si tus árboles no son solo binarios, podrías hacer una lista. use nil cuando no haya un niño izquierdo o derecho, por supuesto.

De lo contrario, mira esta respuesta .

El árbol en tu foto:

(mktree ''A (mktree ''B (mktree ''D) (mktree ''E)) (mktree ''C nil (mktree ''F)))

Answer 2

Los árboles tienen casi todo en Clojure porque se prestan tan bien al intercambio estructural en una estructura de datos persistente. Los mapas y los vectores son en realidad árboles con un alto factor de ramificación para darles una búsqueda limitada e insertar tiempo. Así que la respuesta más breve que puedo dar (aunque en realidad no es tan útil) es que realmente recomiendo estructuras de datos puramente funcionales de Chris Okasaki para una respuesta real a esta pregunta. También el video de Rich Hickey sobre las estructuras de datos de Clojure en blip.tv

(set ''A ''B ''C)

Answer 3

''(A (B (D) (E)) (C (F)))