:-dynamic stablo/3.

napravi([A|Rep]):-asserta(stablo(nil,A,nil)),ubaci(Rep).
ubaci([X|Y]):-nadjiMesto(X,_),ubaci(Y).
ubaci([]).
nadjiMesto(Elem,Koren):- stablo(Levo,Koren,_),Elem<Koren,not(Levo=nil),nadjiMesto(Elem,Levo).
nadjiMesto(Elem,Koren):-stablo(nil,Koren,Z),Elem<Koren,retract(stablo(nil,Koren,Z)),assertz(stablo(Elem,Koren,Z)),assertz(stablo(nil,Elem,nil)).

nadjiMesto(Elem,Koren):- stablo(_,Koren,Desno),Elem>=Koren,not(Desno=nil),nadjiMesto(Elem,Desno).
nadjiMesto(Elem,Koren):-stablo(Z,Koren,nil),Elem>=Koren,retract(stablo(Z,Koren,nil)),assertz(stablo(Z,Koren,Elem)),assertz(stablo(nil,Elem,nil)).

nadjiMesto(Elem,_):- assertz(stablo(nil,Elem,nil)).


brisi(X):-stablo(Levo,X,Desno),srediDecu(Levo,X,Desno),srediRoditelja(Levo,X,Desno), retract(stablo(Levo,X,Desno)),prviKoren.

srediDecu(nil,_,_).
srediDecu(Levo,_,Desno):-nadjiDesniList(Levo,Desno).

nadjiDesniList(Cvor,Desno):-stablo(nil,Cvor,nil),retract(stablo(nil,Cvor,nil)),assertz(stablo(nil,Cvor,Desno)).
nadjiDesniList(Cvor,Desno):-stablo(_,Cvor,D),nadjiDesniList(D,Desno).


srediRoditelja(nil,X,Desno):-stablo(X,Roditelj,D1),retract(stablo(X,Roditelj,D1)),assertz(stablo(Desno,Roditelj,D1)).
srediRoditelja(nil,X,Desno):-stablo(L1,Roditelj,X),retract(stablo(L1,Roditelj,X)),assertz(stablo(L1,Roditelj,Desno)).

srediRoditelja(Levo,X,_):-stablo(X,Roditelj,D1),retract(stablo(X,Roditelj,D1)),assertz(stablo(Levo,Roditelj,D1)).
srediRoditelja(Levo,X,_):-stablo(L1,Roditelj,X),retract(stablo(L1,Roditelj,X)),assertz(stablo(L1,Roditelj,Levo)).

srediRoditelja(_,_,_).

prviKoren :- stablo(L,K,D),not(stablo(K,_,_)),not(stablo(_,_,K)),retract(stablo(L,K,D)),asserta(stablo(L,K,D)).

brisi :- retractall(stablo(_,_,_)).
ispis :- listing(stablo).

dubina(X):- prviKoren,stablo(Levo,Koren,Desno),dubina(Koren,X),!.
dubina(nil,0):-!.
dubina(Koren,X):-stablo(Levo,Koren,Desno),dubina(Levo,X1),dubina(Desno,X2),maks(X1,X2,Y),X is Y+1.

maks(X,Y,X):-X>=Y.
maks(X,Y,Y).

for(I,I,K):-I=<K.
for(I,P,K):-P1 is P+1,P1=<K,for(I,P1,K).

poNivoima(X):- for(I,1,X),write('Nivo '),write(I),write(': '),ispisNivo(I),nl,fail.
poNivoima.

ispisNivo(I):-stablo(_,K,_),ispisN(I,1,K),!.
ispisNivo(_):-!.

ispisN(I,I,K):-not(K=nil), write(K),write(' ').
ispisN(I,J,K):-stablo(L,K,D),J1 is J+1,ispisN(I,J1,L),ispisN(I,J1,D).
ispisN(_,_,_).


nivoLista(D,X):-formNivoList(1,D,X,[]).

formNivoList(D,D1,X,X):-D > D1.
formNivoList(DP,D,X,P):- poNivoimaL(DP,L),DP1 is DP+1,append(P,[L],P1),formNivoList(DP1,D,X,P1).

poNivoimaL(X,L):-stablo(_,K,_),popuni(1,X,[],L,K).

popuni(_,_,LP,LP,nil).
popuni(X,X,LP,L,K):-append(LP,[K],L).
popuni(X,Y,LP,L,K):-stablo(Levo,K,Desno),X1 is X+1,popuni(X1,Y,LP,LL,Levo),popuni(X1,Y,LP,LD,Desno),append(LL,LD,L).