/*
 * ej-03-11.pl
 *
 * Una estrategia de recorrido de arboles es la *horizontal*, la cual consiste
 * en visitar los nodos que estan en un mismo nivel de izqueierda a derecha,
 * luego proceder con los nodos del proximo nivel y asi sucesivamente
 * hasta visitar todos los nodos del arbol.  A continuacion se presenta
 * un ejemplo de recorrido horizontal:
 *
 *      a
 *      /\
 *     /  \
 *    c    j              ( a c j t r h m q z )
 *   /\    /\
 *  t  r  h  m
 *    /\
 *   q  z



La forma de tratar este recorrido usualmente es trabajar con dos listas, 
Ldesarrollado y Lnodos.  Se inicia Lnodos con la raíz del árbol.  Luego 
se retira el primer elemento de Lnodos, se lo agrega en último lugar en 
Ldesarrollados, se hallan los nodos sucesores del mismo y se incorporan 
al final de Lnodos.  Se repite el paso anterior y el algoritmo termina 
cuando Lnodos está vacía;  el recorrido estará en Ldesarrollados.

En el ejemplo, los sucesores del nodo a son los nodos b y c.

Se le solicita que defina el predicado:

                 recorridoHorizontal( Arbol, Lista )

que al ser evaluado permita obtener la Lista con los nodos del árbol 
ordenados de acuerdo al recorrido horizontal arriba descripto.

Indique claramente cómo representará el árbol.  Considere que cada nodo
del árbol posee un nombre o identificador que lo hace único en el árbol.
 */


/*
 * recorridoHorizontal(Arbol, Lista)
 *
 * nodo(Nombre, ArbolIzquierdo, ArbolDerecho)
 *
 */

recorridoHorizontal( nodo(N,I,D), ListaNodos ) :-
	rec_horiz_aux( [N], nodo(N,I,D), ListaInvertida),
	reverse(ListaInvertida, ListaNodos).


/*
 * rec__horiz_aux( ListaNodos, Arbol, ListaNodosDesarrollados)
 */

rec_horiz_aux( [], _, []).

rec_horiz_aux( [N|Ns], Arbol, [N|Desarrollados] ) :-
	nodos_sucesores(N, Sucesores, Arbol),
	append(Ns, Sucesores, NodosARecorrer),
	rec_horiz_aux(NodosARecorrer, Arbol, Desarrollados).


/*
 * nodos_sucesores( nodo, lista_sucesores, arbol )
 */
nodos_sucesores( N, [],      nodo(N,nil,         nil)          ) :- !.
nodos_sucesores( N, [S1],    nodo(N,nodo(S1,_,_),nil)          ) :- !.
nodos_sucesores( N, [S2],    nodo(N,nil,         nodo(S2,_,_)) ) :- !.
nodos_sucesores( N, [S1,S2], nodo(N,nodo(S1,_,_),nodo(S2,_,_)) ) :- !.

nodos_sucesores( N, Sucesores, nodo(_,I,_) ) :-
	nodos_sucesores( N, Sucesores, I ).

nodos_sucesores( N, Sucesores, nodo(_,_,D) ) :-
	nodos_sucesores( N, Sucesores, D ).



/*
 * reverse(?list, ?list)
 * reverse(List1, List2) succeeds if List2 unifies with the list List1 in reverse order.
 * reverse/2 Es un predicado GNU Prolog.
 * Damos una implemetación como cualquiera:
 *

reverse( [], [] ).

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

 * Lo mismo para append/3
 * append(?list, ?list, ?list)
 * append(List1, List2, List12) succeeds if the concatenation of the list List1 
 * and the list List2 is the list List12. This predicate is re-executable 
 * on backtracking (e.g. if List12 is instantiated and both List1
 * and List2 are variable).
 * append/3 es un predicado GNU Prolog

append( [], X, X ).

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

 */

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