Práctica de Prolog: Árboles (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

% data Arbol = nil | bin(Arbol, Raiz, Arbol)

% Ejercicio 13
% Un ´arbol binario se representar´a en Prolog con:
% nil, si es vac´io.
% bin(sai, v, sad), donde v es el valor del nodo, sai es el sub´arbol izquierdo y sad es el sub´arbol
% derecho.
% i. Definir predicados en Prolog para las operaciones comunes de ´arboles: vacio, raiz, altura y
% cantidadNodos. Asumir siempre que el ´arbol est´a instanciado.
max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.
min(X, Y, X) :- X < Y.
min(X, Y, Y) :- X >= Y.


%vacio(+Arbol).
vacio(nil).

%raiz(+Arbol, -Raiz).
raiz(bin(_, Raiz, _), Raiz).

%altura(+Arbol, -Altura).
altura(nil, 0).
altura(bin(Izq, _, Der), N) :- altura(Izq, AlturaI), altura(Der, AlturaD),
max(AlturaI, AlturaD, N).

%cantidadNodos(+Arbol, -Cantidad).
cantidadNodos(nil, 0).
cantidadNodos(bin(Izq, _, Der), N) :- cantidadNodos(Izq, CantI), cantidadNodos(Der, CantD),
N is CantI + CantD + 1.

% ii. Se define la profundidad de un nodo como la distancia desde la ra´iz hasta el mismo (la ra´iz
% tiene profundidad 0). Definir un predicado hpp que permita, dado un ´arbol binario instanciado,
% obtener la lista de todos los valores de las hojas que tengan profundidad par. Puede ocurrir que
% dos o m´as hojas distintas tengan el mismo valor, pero en la respuesta de hpp los valores no deben
% repetirse.
% Ejemplo:
% hpp( bin(bin(nil, 2, nil), 2, bin(bin(nil, 4, nil), 1, nil) ), L).
% L = [4];
% No.

%hpp(+Arbol, -L)
hpp_con_duplicados(nil, 0, []).
hpp_con_duplicados(nil, 1, []).
hpp_con_duplicados(bin(Izq, Root, Der), 0, [Root | Res]) :- hpp_con_duplicados(Izq, 1, ResI), hpp_con_duplicados(Der, 1, ResD),
append(ResI, ResD, Res).
hpp_con_duplicados(bin(Izq, _, Der), 1, Res) :- hpp_con_duplicados(Izq, 0, ResI), hpp_con_duplicados(Der, 0, ResD),
append(ResI, ResD, Res).

% iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.
pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio).
sacarDuplicados([], []).
sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups).
sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups).

hpp(Arbol, Res) :- hpp_con_duplicados(Arbol, 0, Dups), append([_], L, Dups), sacarDuplicados(L, Res).


% Ejercicio 14
% Definir los siguientes predicados, utilizando la misma representaci´on de ´arbol binario definida en el
% ejercicio 13:
% i. aBB(+T) que ser´a verdadero si T es un ´arbol binario de b´usqueda.
maximo_vs(nil, N, N).
maximo_vs(bin(Izq, Root, Der), N, Max) :- maximo_vs(Izq, Root, MaxI), maximo_vs(Der, N, MaxD),
max(MaxI, MaxD, Max).
minimo_vs(nil, N, N).
minimo_vs(bin(Izq, Root, Der), N, Min) :- minimo_vs(Izq, Root, MinI), minimo_vs(Der, N, MinD),
min(MinI, MinD, Min).

aBB(nil).
aBB(bin(Izq, Root, Der)) :- aBB(Izq), aBB(Der), maximo_vs(Izq, Root, Root),
minimo_vs(Der, Root + 1, Root + 1).

% ii. aBBInsertar(+X, +T1, -T2) donde T2 resulta de insertar X en orden en el ´arbol T1.
aBBInsertar(X, nil, bin(nil, X, nil)).
aBBInsertar(X, bin(Izq, Root, Der), bin(NuevoIzq, Root, Der)) :- X =< Root, aBBInsertar(X, Izq, NuevoIzq).
aBBInsertar(X, bin(Izq, Root, Der), bin(Izq, Root, NuevoDer)) :- X > Root, aBBInsertar(X, Der, NuevoDer).


% Ejercicio 15
% Un ´arbol n-ario de naturales se representar´a en Prolog con:
% hoja(V), donde V es un natural seg´un la representaci´øn de Prolog.
% nodo(V, Hijos), donde V es un natural seg´un la representaci´øn de Prolog, e Hijos es una lista
% no vac´ia de ´arboles n-arios de naturales.
% Definir el predicado mayores(+Arbol, +Max) que dado un ´arbol n-ario de naturales (que podr´ia
% contener variables en los nodos) devuelve verdadero si:
% Los naturales que contiene el ´arbol son menores o iguales a Max (en caso de ser variables, deber´an
% instanciarse con valores en dicho rango).
% El valor de cada nodo del ´arbol es mayor que la suma de los valores de sus hijos.
% ejemplo: mayores(nodo(X, [hoja(0), nodo(1,[hoja(0), hoja(0)]),nodo(4,[hoja(1), hoja(0), nodo(1, [hoja(0)])])]),9)

%in_range(+Min, +Max, -Num).
in_range(Min, Max, Min) :- Min =< Max.
in_range(Min, Max, N) :- Min =< Max, NextMin is Min + 1, in_range(NextMin, Max, N).

valor(hoja(V), V).
valor(nodo(V, _), V).

mayores(hoja(V), Max) :- in_range(0, Max, V).
mayores(nodo(V, [X]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V).
mayores(nodo(V, [X, Y | T]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V),
VMenosX is V - Val, mayores(nodo(VMenosX, [Y | T]), Max).

%mayores no anda bien, no hace la suma de todos los subhijos, sino de los inmediatos... como se hace bien? facilmente?