% strom(?T) :- T je strom.
strom(nil).
strom(t(L, _, R)) :- strom(T), strom(R).

% preorder_list(+T, -L) :- L je seznam vrcholů T v preorder pořadí.
preorder_list(nil, []).
preorder_list(t(L, X, R), [X|S]) :-
	preorder_list(L, SL),
	preorder_list(R, SR),
	append(SL, SR, S).

postorder(t(L, _, _), X) :- postorder(L, X).
postorder(t(_, _, R), X) :- postorder(R, X).
postorder(t(_, X, _), X).

vyhodnot(H, H) :- number(H).
vyhodnot(t(L, +, R), H) :- vyhodnot(L, HL), vyhodnot(R, HR), H is HL + HR.
vyhodnot(t(L, *, R), H) :- vyhodnot(L, HL), vyhodnot(R, HR), H is HL * HR.

% cmp_v(?U, ?V) :- U má klíč nejvýše V nebo jeden z vrhcolů je externí.
cmp_v(nil, _).
cmp_v(_, nil).
cmp_v(t(_,K1,_), t(_,K2,_)) :- K1 @< K2.

% bst(+T) :- T je binární vyhledávací strom.
bst(nil).
bst(T) :- T = t(L, K, R), cmp_v(L, T), cmp_v(T, R), bst(L), bst(R).

% find(+K, +T, ?V) :- T je BVS, K je hledaný klíč a V je vrchol stromu T, jehož klíč je K.
find(_, nil, nil).
find(K, T, T) :- T = t(_, K, _). % Nalezení vrcholu
find(K, t(L, X, _), V) :- X @< K, find(L, K, V).
find(K, t(_, X, R), V) :- X @> K, find(R, K, V).

% insert(+K, +T, -NT) :- NT je BVS T, který navíc obsahuje klíč K,
% pokud jej předtím neobsahoval.
insert(K, nil, t(nil, K, nil)).
insert(K, T, T) :- T = t(_, K, _).
insert(K, t(L, X, R), t(NL, X, R)) :- K @< X, insert(L, K, NL).
insert(K, t(L, X, R), t(L, X, NR)) :- K @> X, insert(R, K, NR).

bst_from_list(L, T) :- bst_from_list(L, nil, T).

bst_from_list([], T, T).
bst_from_list([K|L], T, NT) :- insert(K, T, KT), bst_from_list(L, KT, NT).