1

Buenas,

Quiero hallar la manera de poder devolver una lista con todos los nodos de un árbol en prolog.

Se define un árbol binario en Prolog de la siguiente manera:

A4 = [[[[[],1,[]],5,[]],
    7,
    [[],3,[[],4,[]]]],
    6,
    [[[],10,[]],
    8,
    [[[],9,[]],11,[[],2,[]]]]]

Cuyo aspecto es el siguiente

introducir la descripción de la imagen aquí

Mi duda es, haciendo uso únicamente de los siguientes constructores y selectores

vacio([]).
raiz([_,N,_], N).
hi([HI,_,_],HI).
hd([_,_,HD],HD).
hazarbol(R,HI,HD,[HI,R,HD])

Cómo puedo definir un predicado listadenodos(Abn,L) de manera que por ejemplo:

?- listadenodos(A4,L).
L=[2,9,11,10,8,4,3,1,5,7,6]

La solución que se me ha ocurrido aunque aún no funciona es:

descendencia(X,[L,X,R],[L,X,R]).
descendencia(X,[L,_,_],D) :- descendencia(X,L,D).
descendencia(X,[_,_,R],D) :- descendencia(X,R,D).

listadenodos([],[]).
listadenodos([[],X,[]],[X]).
listadenodos(Abn,P) :- raiz(Abn, N), descendencia(N,Abn,D), listadenodos(D,P).

No busco una respuesta inmediata si no una explicación de cómo proceder para resolver al ejercicio ya que no sé como podría empezarlo, aunque tengo las nociones básicas de Prolog.

2 respuestas 2

1

Hay varias formas de recorrer un árbol (ver Recorrido de árboles):

  • Preorden. Visitar raíz, árbol izquierdo, árbol derecho.
  • Inorden. Visitar árbol izquierdo, raíz, árbol derecho.
  • Postorden. Visitar árbol izquierdo, árbol derecho, raíz.

Por ejemplo, para visitar un árbol en preorden. En el caso base de un árbol vacío se devuelve una lista sin elementos:

listadenodos([],[]).

Para el caso general, se devuelve una lista con la raíz como cabeza y la concatenación de los recorridos en preorden de los arboles izquierdo y derecho como cola:

listadenodos([L,X,R],[X|Xs]) :- 
    listadenodos(L,Ls),
    listadenodos(R,Rs),
    append(Ls,Rs,Xs).

Los recorridos en inorden y postorden se pueden definir de forma similar.

El predicado append/3 forma parte del estándar de Prolog y no suele ser necesario definirlo, en cualquier caso se suele definir como sigue. La concatenación de una lista vacía [] y cualquier lista X es la propia lista X, y la concatenación de una lista (con cabeza H y cola T) con otra lista X es la lista formada por la cabeza H y la concatenación de T y X como cola.

append([],X,X).
append([H|T],X,[H|S]) :- append(T,X,S).
4
  • Gracias de nuevo, esta solución funciona perfecta el 29 may. 2017 a las 18:54
  • Una curiosidad, si quisiera combinar el predicado descendencia con el predicado listadenodos para obtener la lista de nodos de una descendencia como se podría hacer ? Gracias. el 29 may. 2017 a las 19:01
  • Lanza el objetivo ?- descendencia(X,A,D), listadenodos(D,N)., o crea un nuevo predicado p(X,A,N) :- descendencia(X,A,D), listadenodos(D,N).. el 29 may. 2017 a las 19:20
  • Al final lo he resuelto así listadedescendientes(N,Abn,L):- descendencia(N,Abn,Des), listadenodos(Des,L). Gracias :) el 29 may. 2017 a las 19:35
1

Teniendo la siguiente funcion auxiliar concatenar para el armado de la lista:

concatenar([],L,L).
concatenar([X|M],L,[X|Z]):-concatenar(M,L,Z).

Caso base: arbol con unicamente la raiz, retorna lista de unicamente la raiz

listadenodos(tree(A,[],[]),[A]):-!.

Predicado para cuando tiene hijo izquierdo, concatena a la raiz el reusltado de listadenodos del subarbol izquierdo

listadenodos(tree(A,X,[]),S):-listadenodos(X,P), concatenar([A],P,S).

Predicado para cuando tiene hijo derecho, concatena a la raiz el reusltado de listadenodos del subarbol derecho

listadenodos(tree(A,[],X),S):-listadenodos(X,P), concatenar([A],P,S).

Predicado para cuando tiene tanto subarbol derecho como izquierdo no nulos, invoca a los dos predicados anteriores

listadenodos(tree(A,X,Y),W):-listadenodos(X,P),listadenodos(Y,R),concatenar([A],P,U), concatenar(U,R,W).

introducir la descripción de la imagen aquí

4
  • Gracias por contestar, pero no sé si tu respuesta es válida ya que sólo está permitido usar los constructores y selectores definidos arriba. el 28 may. 2017 a las 18:48
  • Acabo de probar tu solución mmartinez7 y no funciona. El output que obtengo es el siguiente listadenodos([[[],3,[]],4,[[],1,[]]],L). false el 28 may. 2017 a las 19:19
  • Disculpas, habian algunos errores en la solucion que te di, edite la respuesta. el 28 may. 2017 a las 20:25
  • Acabo de comprobar ahora la solución tuya y funciona gracias :) el 29 may. 2017 a las 18:54

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.