Árboles binarios en Lisp

En lisp, todos los datos en memoria se estructuran de a pares, conocidos como nodos:

En la notación antigua de lisp, se escribía con puntos así:

> '(23 . 99)
> (23 . 99)

23 es el elemento de la izquierda y 99 el de la derecha

Para acceder al elemento de la izquierda usamos CAR, y para acceder al elemento de la derecha usamos CDR.

> (car '(23 . 99))
23

> (cdr '(23 . 99))
99

De esta manera todos los tipos de datos se estructuran a partir de nodos, solo que actualmente se omite el punto. Así las listas son nodos encadenados:

Del mismo modo las funciones, tienen estructura de lista, solo que estas se evalúan.

Revista Mundo Linux n° 85 - Articulo sobre lisp

Arboles binarios

Para crear árboles usamos los nodos. La figura siguiente es un árbol binario:

Para hacerlo mediante nodos:

Es fácil construirlo en Lisp, (voy a usar la notacion con puntos, pues me resulta mas cómodo)

Las ramas van separadas por puntos y entre paréntesis

> (set 'arbol '(1 . ((2 . nil) . (3 . nil))))
(1 (2) 3)

;;; a la variable arbol le asignamos el arbol binario

Por convención el elemento de la izquierda del nodo tendrá el valor y el elemento de la derecha apuntará hacia otro nodo, o bien apunta a NIL.

Para acceder a la raíz usamos CAR:

> (car arbol)
1

Para acceder al nodo 2, por ejemplo, primero usamos un (CDR arbol), que nos situa en el nodo que contiene las direcciones de los nodos (2 . nil) y (3 . nil). Luego un CAR (que lo envuelve) nos lleva al nodo (2 . nil). Por último un CAR devolverá el elemento 2, si usáramos CDR aca, nos devolvería NIL.

> (car (car (cdr arbol)))
2

Dejo al lector como ejercicio, que intente acceder al elemento 3.

Debido a que los valores están a la izquierda, siempre que queramos acceder un dato, habrá un CAR que envuelva a toda la expresión.

Veamos un árbol con mas hojas:

En Lisp, se ve así:

Se guarda así:

> (set 'arbol '(1  .  ((2 . ((4 . nil) . (5 . nil)))  .  (3 . ((6 . nil) . (7 . nil))))))
(1 (2 (4) 5) 3 (6) 7)

Para recorrer este árbol usamos CAR y CDR, como vimos anteriormente.
Para acceder a 5 sería asi:

> (car (cdr (cdr (car (cdr arbol)))))
5

Dejo al lector que intente acceder a los demás elementos.

Bien de esta manera, podemos crear cualquier tipo de estructura que se nos ocurra. Las funciones para recorrerlas y agregar elementos no serían muy complicadas. Nos evitamos el hecho de tener que manejar punteros y/o variables de tipo puntero.

"Dona lo que quieras, y ayuda a mantener este blogg en funcionamiento, eso eso eso!!!"