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 Commented 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. Commented 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).. Commented 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 :) Commented 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. Commented 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 Commented el 28 may. 2017 a las 19:19
  • Disculpas, habian algunos errores en la solucion que te di, edite la respuesta. Commented el 28 may. 2017 a las 20:25
  • Acabo de comprobar ahora la solución tuya y funciona gracias :) Commented el 29 may. 2017 a las 18:54

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

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