Zadaci 25/04/2017

initStablo(nil).

insert(E, nil, s(nil, E, nil)):- !.
insert(E, s(L, D, R), s(L1, D, R)):-
    E < D,
    insert(E, L, L1),
    !.
insert(E, s(L, D, R), s(L, D, R1)):-
    E >= D,
    insert(E, R, R1),
    !.

listToTree([], nil).
listToTree([ G | R ], S):-
    listToTree(R, S1),
    insert(G, S1, S).

brCvorova(nil, 0).
brCvorova(s(L, _, R), N):-
    brCvorova(L, N1),
    brCvorova(R, N2),
    N is N1 + N2 + 1.

ispisStabla(nil):- !.
ispisStabla(s(L, E, R)):-
    ispisStabla(L),
    write(E),
    nl,
    ispisStabla(R),
    !.

% trazi listu koja ide najvise u dubinu
najduzi(nil, [], 0):- !.
najduzi(s(L, N, R), Lista, Duzina):-
    najduzi(L, Lista1, Duzina1),
    najduzi(R, _, Duzina2),
    Duzina1 > Duzina2,
    Duzina is Duzina1 + 1,
    Lista = [N | Lista1],
    !.
najduzi(s(L, N, R), Lista, Duzina):-
    najduzi(L, _, _),
    najduzi(R, Lista2, Duzina2),
    Duzina is Duzina2 + 1,
    Lista = [N | Lista2].

concatLists(L1, [], L1):- !.
concatLists(L1, [G | O], [G | R]):-
    concatLists(L1, O, R).

concatMatrix([], M, M):- !.
concatMatrix(M, [], M):- !.
concatMatrix([G1 | O1], [G2 | O2], [G | O]):-
    concatLists(G1, G2, G),
    concatMatrix(O1, O2, O).


% trazi najsiri nivo u stablu
maxWidth(S, List, L):-
    najsiri(S, Matrix),
    longest(Matrix, List, L).

najsiri(nil, []):- !.
najsiri(s(L, N, R), [[N] | M]):-
    najsiri(L, M1),
    najsiri(R, M2),
    concatMatrix(M1, M2, M).

longest([], [], 0):- !.
longest([ G | O ], List, L1):-
    longest(O, List, L1),
    length(G, L2),
    L1 > L2,
    !.
longest([ G | _ ], G, L):-
    length(G, L).