Arboles con múltiples nodos

Desarrollaremos un árbol múltiple y veremos como recorrerlo y guardarlo. El ejemplo que seguiremos es una estructura en forma de árbol que vi en algún libro, alguna vez y que se utilizaba para ejemplificar un árbol de decisiones que trataba sobre si era conveniente o no ir a jugar al tenis. Le aconsejo que vaya guardando las funciones en un archivo de texto con extensión .lisp, por ejemplo: "arbol.lisp". Cada vez que modifica el archivo fuente, cargue en el interprete la nueva versión con su archivo modificado:

> (load "arbol.lisp")

El árbol de decisión establece que alguien va a jugar tenis, según el clima.

En primer lugar debemos crear una función para guardar los nodos (en un archivo de texto con extension .lisp), sería así:

(defun agregar-nodo (nodo)
  (push nodo *arbol*)) ;vamos metiendo cada nodo en *arbol*

Lo guardamos en la lista global *arbol*. Debemos declararla al principio:

(defvar *arbol* nil) ; y le asignamos a nil

Debemos generar el nodo con una función, es muy fácil:

(defun hacer-nodo(nombre &rest valores)
   (list :nombre nombre :valores valores))

"nombre" es el nombre del nodo, al que se hará referencia. En valores se guarda una lista con los valores del árbol. El primer elemento va a ser la raíz y los demás serán sus ramas. Veamos como cargamos el árbol generando los nodos, a través del interprete:

> (agregar-nodo (hacer-nodo 'clima '("clima" . nil) '("soleado" . humedad) '("nublado" . T) '("lluvioso" . viento)))
(("clima") ("soleado" . HUMEDAD) ("nublado" . T) ("lluvioso" . VIENTO))

CLIMA es el nombre del nodo. Los símbolos HUMEDAD y VIENTO son símbolos a los que daremos los valores correspondientes. En el caso de generar el primer elemento "raíz" del árbol, el primer valor de la lista de valores es la cadena "clima" que es el dato asignado al nodo principal, los valores que siguen son los nodos múltiples.

Ahora creamos el resto de los nodos:

> (agregar-nodo (hacer-nodo 'humedad '("humedad" .  nil) '("normal" . T) '("alta" . nil)))
(("humedad") ("normal" . T) ("alta"))

> (agregar-nodo (hacer-nodo 'viento '("viento" . nil) '("fuerte" . nil) '("debil" . T)))
(("viento") ("fuerte") ("debil" . T))

En este caso va el símbolo y luego los nodos múltiples.
¿Como hacemos para asignar o enlazar a HUMEDAD y VIENTO, los símbolos, con sus respectivos valores...?

Si consultamos estos símbolos veremos que aun no contienen nada y nos dará un error. Incluso debemos tener un símbolo que apunte a la raíz y a sus valores. Para eso les dimos los nombres en :NOMBRE a cada nodo. Debemos crear una función para asignar o enlazar a cada símbolo ":NOMBRE" sus respectivos valores, tanto el de la raíz como sus nodos. De esta manera cada nodo quedará en memoria "en forma de árbol", es decir el símbolo del mismo nombre, por ejemplo HUMEDAD, dentro de la lista de valores, tendrá los nodos asignados como una lista, ya que se le da el mismo nombre ":NOMBRE" cuando se crea el nodo. Parece complicado, pero es fácil, por ejemplo el símbolo VIENTO que se crea en el nodo de nombre CLIMA va a ser el mismo que el símbolo VIENTO cuando se crea el nodo del mismo nombre. Solo que aun estos símbolos no contienen valores. Entonces, creamos la función que realiza dicha asignación:

(defun transforma-nodo-x(nodo) ;Función que transforma un registro de nodo en un nodo en memoria
  (set (getf nodo :nombre) (getf nodo :valores)))

Esta función asigna a cada símbolo en :nombre su lista de valores o nodos múltiples. Ahora bien, tenemos varios nodos, y por lo tanto necesitamos cargar a memoria toda la lista de registros nodos que guardamos en *arbol*, para ello, barrilete cósmico, usamos la siguiente función:

(defun transforma-nodos() ; Función que transforma todos los nodos del árbol y los carga en memoria
  (dolist (nodo *arbol*)
    (transforma-nodo-x nodo)))

Hacemos un (transforma-nodos), y ya podemos constatar que los valores se han cargado:

> clima
(("clima") ("soleado" . HUMEDAD) ("nublado" . T) ("lluvioso" . VIENTO))

> humedad
(("humedad") ("normal" . T) ("alta"))

Debemos modificar la función agregar-registro agregándole la función para cargar un nodo, para que cada vez que creamos un registro nodo, lo cargue en memoria, es decir que le asigne a su nombre los valores correspondientes:

(defun agregar-nodo(nodo) ; Función que agrega un nodo a la lista *arbol*; y a la memoria "nodo-x"
   (push nodo *arbol*)
   (transforma-nodo-x nodo))

Para recorrer el árbol, podemos usar recursividad. Primero accedemos al dato del primer nodo con (first (car ...)), luego aplicando la función recursivamente accedemos al primer elemento de la lista con un first "la raíz", luego con otra llamada recursiva al resto, "los valores", usando un rest. Bueno, menos palabras y mas acción:

(defun mostrar (lista) ;función que muestra todos los nodos
  (when (not (null lista))
    (when (not (equal T lista))
    (format t "~%~5t~s" (car (first lista)))
    (mostrar (eval (cdr (first lista))))
    (mostrar (rest lista)))))

El argumento lista no trata sobre una señorita inteligente, mas bien trata sobre la lista de valores que contiene cada símbolo :NOMBRE, como vimos anteriormente, por ejemplo los símbolos CLIMA, HUMEDAD y VIENTO, los que ya cuentan con valores asignados.

Entonces llamamos a nuestra función para ver los nodos:

> (mostrar clima)

     "clima"
     "soleado"
     "humedad"
     "normal"
     "alta"
     "nublado"
     "lluvioso"
     "viento"
     "fuerte"
     "debil"

Ahí están todos los datos de los nodos. Te preguntarás por que se muestra el árbol sin diferenciar la raíz de sus nodos con alguna especie de dentado o tabulación, es verdad, llevaría mas programación.

¡Ah! ...

¿te habrás dado cuenta que si sales del interprete se borran los nodos cargados en *arbol* y las listas de valores que se cargaron en los símbolos...?

Entonces, antes de salir vamos a crear una función para guardar el árbol en un archivo:

(defun guardar-arbol(archivo) ;Función para guardar los registros nodos de *arbol* en un archivo de salida
  (with-open-file (salida archivo
 :direction :output
 :if-exists :supersede)
    (with-standard-io-syntax
      (print *arbol* salida))))

Pasemos a guardar el archivo con los datos cargados a través del interprete:

> (guardar-arbol "arbol.tree") ;en arbol.tree quedan los datos cargados

Ahora queda cargar esos nodos registro cuando iniciamos:

(defun cargar-arbol (archivo) ;Función para recuperar los nodos de *arbol* desde un archivo de entrada
  (with-open-file (entrada archivo)
    (with-standard-io-syntax
      (setf *arbol* (read entrada)))))

Para cargar hacemos:

> (cargar-arbol "arbol.tree")

Entonces en nuestro archivo "arbol.lisp" agregamos al final:

(cargar-arbol "arbol.tree") ;para cargar los nodos registro al inicio
(transforma-nodos) ;para asignar a los símbolos con los nombres correspondientes sus valores respectivos.
A todo esto le estaría faltando una función que recorra el árbol y haga las preguntas para decidir si voy a jugar al tenis. Así que agregamos estas funciones a nuestro archivo "arbol.lisp", que nos ayudarán a decidir:

(defun leer-mensaje(mensaje) ;función que muestra un msj en pantalla y devuelve un valor ingresado
(format *query-io* "~%~%~a: " mensaje)
(force-output *query-io*)
(read-line *query-io*))

(defun pregunta (lista) ;función que recorre el árbol preguntando al usuario
  (when (not (null lista))
    (if (not (equal T lista))
(progn
 (format t "~%¿Cual es la condición de el/la ~s?" (car (first lista)))
       (set 'opcion 1)
 (set 'valores (rest lista))
 (format t "~%")
 (dolist (valor valores)
   (format t "~%~5t~s. ~s" opcion (car valor))
   (set 'opcion (+ 1 opcion)))
 (set 'elegir (- (parse-integer (leer-mensaje "Elija una opcion: ") :junk-allowed t) 1))

 (pregunta (eval (cdr (nth elegir valores))))) ;vuelve a preguntar con recursividad segun opcion

(format t"~%Entonces voy a jugar al tenis"))))

Para hacer la pregunta obvia:

> (pregunta clima)

En este link está el archivo "arbol.lisp" que contiene las funciones descritas arriba. También otro link donde se guardaron en disco los datos del árbol: "arbol.tree".