% Autor:
% Datum: 02.12.2018

 mmax(Z1,Z2,Z1) :- Z1 >= Z2,!.
 mmax(Z1,Z2,Z2) :- Z2 >= Z1,!.

%
%  is_sbin_tree(nil).
%  is_sbin_tree(t(W,H,L,R)) :- number(W),
%                              is_sbin_tree(L, 0, W, H1), %links
%                              is_sbin_tree(R, W, inf, H2), %rechts
%                              mmax(H1,H2,HMax),
%                              H is HMax.

 is_sbin_tree(T) :- is_sbin_tree(T, 0, inf, _).
 is_sbin_tree(nil,_,_,1).
 %HMax +1 damit die Höhe nach oben hin größer wird, weil die Wurzel die höchste Höhe hat
 is_sbin_tree(t(W,H,L,R),LowerBound,UpperBound,HMax + 1) :- number(W),
                                          W >= LowerBound,
                                          W < UpperBound,
                                          is_sbin_tree(L, LowerBound, W, H1),  %links
                                          is_sbin_tree(R, W, UpperBound, H2),  %rechts
                                          mmax(H1,H2,HMax),
                                          H is HMax.



insert_sbin_tree(Element, Tree, NewTree) :- insert_sbin_tree(Element, Tree, NewTree, _),!.
insert_sbin_tree(Element, nil, t(Element, 1, nil, nil), 2).
insert_sbin_tree(Element, t(W, H, L, R), t(W, HNew, LNew, R), HParent) :-
                          Element < W,
                          insert_sbin_tree(Element, L, LNew, HL),
                          mmax(H,HL,HNew),
                          HParent is HNew + 1.
insert_sbin_tree(Element, t(W, H, L, R), t(W, HNew, L, RNew), HParent) :-
                          Element >= W,
                          insert_sbin_tree(Element, R, RNew, HR),
                          mmax(H,HR,HNew),
                          HParent is HNew + 1.

inorder_sbin2tree(nil, []).
inorder_sbin2tree(t(W, _, L, R), List):- inorder_sbin2tree(L, LeftList),
                                         inorder_sbin2tree(R, RightList),
                                         append(LeftList,[W|RightList],List).


halfList(List,FirstPart,SecondPart) :- length(List,Length),halfList(List,FirstPart,SecondPart,Length,0),!.
halfList([],[],[],_,_).
halfList([Head|Tail], [Head | FirstPart], SecondPart, Length, Count) :- Count < (Length-1)/2,
                        halfList(Tail, FirstPart, SecondPart, Length,Count+1).
halfList([Head|Tail], FirstPart, [Head| SecondPart], Length, Count) :- Count >= (Length-1)/2,
                        halfList(Tail, FirstPart, SecondPart, Length,Count+1).

list2sbin_tree(List,Tree) :- halfList(List,Left,Right), list2sbin_tree(Left, Right, Tree, _),!.
list2sbin_tree([],[],nil,1).
list2sbin_tree([],[Head|[]],t(Head,1,nil,nil),2).

list2sbin_tree(Left,[HeadR| TailR], t(HeadR,H,L,R), HParent) :-
    halfList(Left, Left1, Left2),
    halfList(TailR, Right1, Right2),
    list2sbin_tree(Left1, Left2, L, HL),
    list2sbin_tree(Right1, Right2, R, HR),
    mmax(HL,HR,H),
    HParent is H + 1.





gennumslist(Anzahl,List) :- randset(Anzahl,1000,List).