LISP - Árbol

Puede construir estructuras de datos de árbol a partir de celdas de cons, como listas de listas.

Para implementar estructuras de árbol, tendrá que diseñar funcionalidades que atraviesen las celdas de contras, en un orden específico, por ejemplo, preorden, en orden y posorden para árboles binarios.

Árbol como lista de listas

Consideremos una estructura de árbol formada por celdas de contras que forman la siguiente lista de listas:

((1 2) (3 4) (5 6)).

En forma de diagrama, podría expresarse como:

Funciones de árbol en LISP

Aunque principalmente necesitará escribir sus propias funcionalidades de árbol de acuerdo con sus necesidades específicas, LISP proporciona algunas funciones de árbol que puede utilizar.

Aparte de todas las funciones de lista, las siguientes funciones funcionan especialmente en estructuras de árbol:

No Señor.	Función descriptiva
1	copy-tree x y vecp opcional Devuelve una copia del árbol de contras celdas x. Copia recursivamente las direcciones del coche y del CDR. Si x no es una celda de cons, la función simplemente devuelve x sin cambios. Si el argumento vecp opcional es verdadero, esta función copia vectores (recursivamente) así como celdas de cons.
2	tree-equal xy & key: test: test-not: key Compara dos árboles de células contras. Si xey son ambas celdas de cons, sus coches y cdrs se comparan de forma recursiva. Si ni x ni y son celdas de cons, se comparan mediante eql o de acuerdo con la prueba especificada. La función: clave, si se especifica, se aplica a los elementos de ambos árboles.
3	subst nuevo árbol antiguo y clave: prueba: prueba-no: clave Sustituye las apariciones de un elemento antiguo dado por un elemento nuevo , en el árbol , que es un árbol de celdas de contras.
4	nsubst nuevo árbol antiguo y clave: prueba: prueba-no: clave Funciona igual que subst, pero destruye el árbol original.
5	sublis árbol de lista y clave: prueba: prueba-no: clave Funciona como subst, excepto que toma una lista de asociación, una lista de pares nuevos y antiguos. Cada elemento del árbol (después de aplicar la función de tecla:, si corresponde), se compara con los carros de una lista; si coincide, se reemplaza por el cdr correspondiente.
6	nsublis árbol de lista y clave: prueba: prueba-no: clave Funciona igual que sublis, pero en una versión destructiva.

Ejemplo 1

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq lst (list '(1 2) '(3 4) '(5 6)))
(setq mylst (copy-list lst))
(setq tr (copy-tree lst))

(write lst)
(terpri)
(write mylst)
(terpri)
(write tr)

Cuando ejecuta el código, devuelve el siguiente resultado:

((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))

Ejemplo 2

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(write tr)
(setq trs (subst 7 1 tr))
(terpri)
(write trs)

Cuando ejecuta el código, devuelve el siguiente resultado:

((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))

Construyendo su propio árbol

Intentemos construir nuestro propio árbol, usando las funciones de lista disponibles en LISP.

Primero, creemos un nuevo nodo que contenga algunos datos.

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)

A continuación, agreguemos un nodo hijo al árbol: tomará dos nodos de árbol y agregará el segundo árbol como hijo del primero.

(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree)

Esta función devolverá al primer hijo de un árbol determinado; tomará un nodo de árbol y devolverá el primer hijo de ese nodo, o nulo, si este nodo no tiene ningún nodo hijo.

(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

Esta función devolverá el siguiente hermano de un nodo determinado: toma un nodo de árbol como argumento y devuelve una referencia al siguiente nodo hermano, o nil, si el nodo no tiene ninguno.

(defun next-sibling (tree)
   (cdr tree)
)

Por último, necesitamos una función para devolver la información en un nodo:

(defun data (tree)
   (car (car tree))
)

Ejemplo

Este ejemplo utiliza las funcionalidades anteriores:

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)
(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

(defun next-sibling (tree)
   (cdr tree)
)
(defun data (tree)
   (car (car tree))
)
(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree
)

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(setq mytree (make-tree 10))

(write (data mytree))
(terpri)
(write (first-child tr))
(terpri)
(setq newtree (add-child tr mytree))
(terpri)
(write newtree)

Cuando ejecuta el código, devuelve el siguiente resultado:

10
(2 (3 4 5) ((7 8) (7 8 9)))

((1 2 (3 4 5) ((7 8) (7 8 9)) (10)))