% nacteni:
/* ['2.7_15.pl']. */

addleaf(nil,X,t(nil,X,nil)).
addleaf(t(Left,X,   Right),X ,t(Left ,X,   Right)).
addleaf(t(Left,Root,Right),X ,t(Left1,Root,Right))  :- Root>X,addleaf(Left, X, Left1).
addleaf(t(Left ,Root,Right),X,t(Left ,Root,Right1)) :- Root<X,addleaf(Right,X,Right1).

delleaf( t( nil ,X,Right),X,Right).
delleaf( t(Left ,X, nil ),X,Left ).
delleaf( t(Left ,X,Right),X,t(Left ,Y,Right1)) :- delmin(Right,Y,Right1).
delleaf( t(Left ,Root,Right),X,t(Left1,Root,Right)) :- X<Root,delleaf(Left,X,Left1).
delleaf( t(Left ,Root,Right),X,t(Left ,Root,Right1)) :- X>Root,delleaf(Right,X,Right1).
delmin(t( nil ,Y,R),Y,R).
delmin(t(Left ,Root,Right),Y,t(Left1,Root,Right)) :- delmin(Left,Y,Left1).


show(T) :- show2(T,0).
show2(nil,_).
show2(t(L,X,R),Indent) :- Ind2 is Indent+2,show2(R,Ind2),tab(Indent),
                          write(X),nl,show2(L,Ind2).

% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       start/0.
       
start:- 
    write('Binarni stromy'),nl,
    write('--------------'),nl, nl,
    write('Vytvoreni stromu: '),nl,
    write('addleaf(nil ,6,T),addleaf(T,8,T1), addleaf(T1,2,T2),'),nl, 
    write('addleaf(T2,4,T3), addleaf(T3,1,T4), show(T4) :'),nl,
    addleaf(nil ,6,T),addleaf(T,8,T1), addleaf(T1,2,T2), addleaf(T2,4,T3), addleaf(T3,1,T4),
    show(T4),

    write('Smazani uzlu s hodnotou 8:'),nl,
    write('delleaf(T4, 8, T5), show(T5) :'),nl,
    delleaf(T4, 8, T5), show(T5),

    write('Smazani uzlu s hodnotou 2:'),nl,
    write('delleaf(T5, 2, T6), show(T6) :'),nl,
    delleaf(T5, 2, T6), show(T6).

?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).
