/*
 * ej-03-10.pl
 *


Sea p1, p2, ..., pn un conjunto de números positivos, los cuales reciben 
el nombre de pesos, y A un árbol binario con n hojas (n>1).

Si asignamos a cada hoja del árbol un peso, obtenemos lo que se denomina 
"árbol binario para los pesos p1,p2,...,pn".

La siguiente sumatoria da el peso total del árbol:

       n
      ---
      \    pi * h(pi)
      /
      ---
      i=1

donde h(pi) es el número de nivel (cantidad de aristas para llegar a una 
hoja) asignado al peso pi.

A continuación se dan dos ejemplos de peso de árbol:

        /\
       /  \                        /\
      /    \                      /\ 9
     /\    /\                    /\ 6
    /  \  /  \                  /  \
    3  9  5  6                  3  5

    arbol_1                     arbol_2
    P(arbol_1) = 46             P(arbol_2) = 45

Definir en Prolog un predicado denominado mapeoArboles/2.  El primer 
argumento corresponde a una lista de árboles binarios con las 
características antes mencionadas (proponga usted una representación 
para los mismos) y el segundo corresponde al árbol de menor peso en la 
lista.

Obviamente deberá definir un predicado para evaluar el peso de cada 
árbol.  Indique claramente la estructura de datos que emplea para 
representar un árbol binario.
 */

/*
 * mapeoArboles(ListaArboles, Menor)
 */

mapeoArboles(Arboles, Menor) :-
	pesar_arboles(Arboles, ArbolesPesados),
	arbol_menos_pesado(ArbolesPesados, Menor).


pesar_arboles( [], [] ).

pesar_arboles( [A|As], [arbol(A,P)|RestoArboles] ) :-
	peso(A, P),
	pesar_arboles(As, RestoArboles).


arbol_menos_pesado( [A], A ).

arbol_menos_pesado( [arbol(A1,P1)|As], arbol(A1,P1) ) :-
	arbol_menos_pesado(As, arbol(A2,P2) ), !,
	P1 < P2.

arbol_menos_pesado( [_|As], Amin ) :-
	arbol_menos_pesado(As, Amin).

/*
 * Ahora el peso de un arbol binario
 * n \in N, n > 1    cantidad de nodos hoja
 * p_i, i=1..n, p_1 \in R, p_i > 0 \forall i
 * p_i es peso de la hoja i
 *
 * \Sum_{i=1}^n p_i \cdot h(p_i)
 *
 * donde h(p_i) es el numero de nivel del nodo hoja i
 * (cantidad de aristas desde la raiz)
 *
 * y un arbol se representa mediante un nodo:
 *    nodo(Peso, ArbolIzquierdo, ArbolDerecho)
 */

peso(Arbol, Peso) :- peso_aux( 0, Arbol, Peso ).


peso_aux( _, nil, 0 ).

peso_aux( H, nodo(P,nil,nil), Peso ) :-
	Peso is H * P, !.

peso_aux( H, nodo(_,I,D), Peso ) :-
	K is H + 1,
	peso_aux(K,I,P1),
	peso_aux(K,D,P2),
	Peso is P1 + P2.

/* EOF ej-03-10.pl */