%DCC-FCUP - Logica e Programacao 2011-2012

bintree([]).
bintree(n(A,L,R)):- integer(A), !, bintree(L), bintree(R).

intree(X,n(X,_,_)):-!.
intree(X,n(_,L,_)):- intree(X,L), !.
intree(X,n(_,_,R)):- intree(X,R).

preorder([],[]).
preorder(n(X,L,R),Xs):-
       preorder(L,Ls),
       preorder(R,Rs),
       append([X|Ls],Rs,Xs).

inorder([],[]).
inorder(n(X,L,R),Xs):-
       inorder(L,Ls),
       inorder(R,Rs),
       append(Ls,[X|Rs],Xs).

postorder([],[]).
postorder(n(X,L,R),Xs):-
       postorder(L,Ls),
       postorder(R,Rs),
       append(Rs,[X],Rs1),
       append(Ls,Rs1,Xs).

t(n(1,n(2,[],n(3,[],[])),n(5,n(2,[],[]),n(7,[],[])))).

t1(n(4,n(2,[],n(5,[],[])),n(5,n(6,[],[]),n(7,[],[])))).

% Ordenadas: permitem representar conjuntos ordenados

insOrdTree(I,[],n(I,[],[])).
insOrdTree(I,n(N,L,R),n(N,Ls,R)):- I<N, !, insOrdTree(I,L,Ls).
insOrdTree(I,n(N,L,R),n(N,L,Rs)):- I>N, !, insOrdTree(I,R,Rs).
insOrdTree(N,n(N,L,R),n(N,L,R)).

% substituir todos nós pelo maximo
maxTree(A,B):-mt(A,B,M,0,M).

mt([],[],_,M,M).
mt(n(N,L,R),n(H,Ls,Rs),H,MX,T):- N<MX, !,
       mt(L,Ls,H,MX,MXX), mt(R,Rs,H,MXX,T).
mt(n(N,L,R),n(H,Ls,Rs),H,MX,T):- 
       N>=MX, mt(L,Ls,H,N,MXX), mt(R,Rs,H,MXX,T).


