1

El predicado que quiero hacer en prolog debe recorrer un árbol n-ario y guardar los valores de cada nodo en una lista. Para representar un árbol uso dos estructuras: hoja/1 y nodo/2.

  • hoja(N) representa una hoja con un valor N (en notación de Peano).
  • nodo(N,Hijos) representa un nodo con un valor N y una lista que contiene hijos.

Por ejemplo:

  • Un árbol con un único nodo que vale 2 se representaría como hoja(s(s(0))).
  • Un árbol con una raíz que vale 1, y dos hijos que valen 2 y 3, se representaría como nodo(s(0),[hoja(s(s(0))),hoja(s(s(s(0))))]

Además, como es normal, un nodo puede contener mas nodos en su lista de hijos.

Este es mi programa:

recorrer(nodo(A,L),Res):-
    miAppend(A,Res,Res2),
    recorrer(L,Res2).

recorrer(hoja(N),N).

%Cuando le paso a recorrer una hoja, funciona

%El problema es que cuando recibe un nodo, a la siguiente iteración de recorrer se le pasa una %lista de Hijos, y no tengo ningún predicado que plantee esa situación. Pero es que no se como %hacerlo. 
He probado con un predicado que recibe una lista, borra la cabeza y vuelve a%recorrer, %pero me sigue sin funcionar:    

%recorrer([Cabeza|Lista],Res):-
%       borrar([Cabeza|Lista],Lista2),
%       recorrer(Lista2,Res).           %Sigue sin funcionar


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

miAppend([], Cs, Cs). 
miAppend([A|As],Bs,[A|Cs]):-
    miAppend(As, Bs, Cs).

Ya no se como hacerlo. Gracias a quien pueda ayudar!

1 respuesta 1

0

El caso base es llegar a una hoja, donde se devuelve una lista con ese único elemento:

elementos(hoja(X), [X]).

En los nodos, se devuelve una lista con el valor del nodo como cabeza, y los elementos de sus hijos como cola, que serán la concatenación de los elementos de todos sus hijos:

elementos(nodo(X,Xs), [X|Ys]) :- elementos(Xs, Ys).

Ahora hay que tratar la lista de árboles, para ir concatenando sus elementos:

elementos([],[]).
elementos([X|Xs],Zs) :- elementos(X,Y), elementos(Xs,Ys), append(Y,Ys,Zs).

Por ejemplo:

?- elementos(nodo(1, [nodo(2, [hoja(5)]), nodo(3, [hoja(6), nodo(7, [hoja(8)])])]), X).
X = [1, 2, 5, 3, 6, 8]

Peano

Nótese que con el predicado anterior, da igual lo que contengan los nodos. Si quieres que sólo recoja como elementos números de Peano, habría que añadir una comprobación:

peano(0).
peano(s(X)) :- peano(X).

elementos(hoja(X),[X]) :- peano(X), !.
elementos(hoja(_),[]).
elementos(nodo(X,Xs),[X|Ys]) :- peano(X), !, elementos(Xs,Ys).
elementos(nodo(_,Xs),Ys) :- elementos(Xs,Ys).
elementos([],[]).
elementos([X|Xs],Zs) :- elementos(X,Y), elementos(Xs,Ys), append(Y,Ys,Zs).

Ahora únicamente añadiría a la lista números de Peano, ignorando el resto:

?- elementos(nodo(s(0), [nodo(s(s(0)), [hoja(5)]), nodo(3, [hoja(6), nodo(7, [hoja(s(s(s(s(0)))))])])]), X).
X = [s(0), s(s(0)), s(s(s(s(0))))].

Estructura de datos

Una consideración respecto a las estructuras que estás utilizando para representar el árbol. No es necesario que distingas explícitamente un nodo y una hoja con dos términos diferentes, ya que una hoja se puede representar como un nodo sin hijos (una lista vacía): hoja(X) :- nodo(X,[])..

elementos(nodo(X,Xs),[X|Ys]) :- elementos(Xs,Ys).
elementos([],[]).
elementos([X|Xs],Zs) :- elementos(X,Y), elementos(Xs,Ys), append(Y,Ys,Zs).

Con esta nueva representación, reducimos el predicado anterior y seguirá funcionando:

?- elementos(nodo(1,[nodo(2,[]),nodo(3,[nodo(4,[]),nodo(5,[])])]),X).
X = [1, 2, 3, 4, 5]

Recorridos

Hay varias formas de recorrer el árbol, según el orden en el que se visitan los nodos:

  • Preorden: Visitar primero la raíz, y luego los hijos.
  • Inorden: Visitar primero el primer hijo, luego la raíz, y después el resto.
  • Postorden: Visitar primero los hijos, y después la raíz.

Puedes tratar de implementar los otros dos recorridos a partir del preorden.

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.