BusquedaProfunda.lsp

; TopologIa del Arbol 
(setq Lista '( (a (b c) ) (b (d e) ) (c (f g) ) (d (h i) ) (e (j k) ) (f (l m) ) (g (n o) ) ) )

; Camino recorrido. Inicialmente vacIo
(setq Ruta nil)

(defun Recorre (Lista)
	(cond
		((eql nil Lista) t)
		(t	(setq x (car Lista))
			(print x)
			(Recorre (cdr Lista))
		)
	)
)

; Se revisa si existe X en el subarbol Rama
; Rama = 0 	es izquierdo	-regresa TRUE-
; Rama = 1	es derecho	-regresa NIL-
; Nodo = (a (b c))	-es sOlo un ejemplo-
; X = 'b		-regresa TRUE
(defun ExisteHoja? (Nodo X Rama)
	(if (equal (position X (second Nodo)) Rama) t nil)
)

; Se extraE el nodo donde se encuentra al componente X
; como primer elemento
; Ejemplo:
;	Lista = ( (a (b c) ) (b (d e) ) (c (f g) ) )
;	    X = 'b
;     Regresa:  (b (d e))	-si lo encontrO
;		NIL		-no lo encontrO
; ----------------------------------------------------------------
(defun BuscaNodo (Lista X)
	(setq Nodo_OK NIL)
	(dolist (Nodo Lista)
		(if (equal X (first Nodo)) (setq Nodo_OK Nodo))
	)
	Nodo_OK
)

(defun Busqueda_Profunda (Arbol Nodo X Ruta)
	(if (equal Nodo nil) Ruta
		(cond
			( (ExisteHoja? nodo X 0)		; existe en la posiciOn 0? -first-
				(setq Ruta (append Ruta (list (first (second Nodo)))))
			)
			( T
				(setq Ruta (append Ruta (list (first (second Nodo)))))
				(setq Nodo (BuscaNodo Arbol (first (second Nodo))))
				(cond
					((equal Nodo nil)
						(setq Ruta (append Ruta (list (first Nodo))))
						(setq Nodo (BuscaNodo Arbol (second (second Nodo))))
					)
					(T (Busqueda_Profunda Arbol Nodo X Ruta))
				)
			)
		)
	)
)


; ______________________________________________________________
; FunciOn de inicio para el algoritmo de bUsqueda en lo profundo
; --------------------------------------------------------------
(defun EncuentraRuta (X)
	(MuestraArbol)
	(setq Ruta nil)									; Se inicializa la ruta con NIL
	(if (equal X (first (first Lista)))						; es el nodo raIz el que se busca?
		(list (first (first Lista)))						; se regresa el nodo raIz
		(Busqueda_Profunda Lista (car Lista) X (list (car (car Lista))))	; se envIa (Arbol, Raiz, X, Ruta) para la bUsqueda
	)
)
		
; ____________________________________
; SOlo se muestra el grAfico del Arbol
; ------------------------------------
(defun MuestraArbol ()
	(print "                            A")
	(print "                          /    \")
	(print "                        /        \")
	(print "                      /            \")
	(print "                    /                \")
	(print "                  /                    \")
	(print "                /                        \")
	(print "              B                           C")
	(print "           /     \                     /     \")
	(print "         /         \                 /         \")
	(print "       D             E             F             G")
	(print "     /  \          /  \         /    \         /   \")
	(print "   H      I      J      K      L      M      N      O")
	T
)