Znamo šta je binarno stablo. Ako zađemo u definiciju, možemo da kažemo da je binarno stablo struktura koja je ili prazna ili ima glavu i levo i desno podstablo. Podstabla su takođe stabla koja su prazna ili imaju levo i desno podstablo itd. Ovo je rekurzivna definicija. Slobodnim rečima mogli bismo da ovo izrazimo ovako nekako:
stablo : null
| (levo:stablo, desno:stablo)
Ako uzmemo za primer sledeće stablo:
a
b c
d e f
U prologu to zapisujemo ovako:
st(a, st(b, st(d, p, p), st(e, p, p)), st(c, st(f, p, p), p)).
gde je st - stablo, p - prazno stablo
Stablo koje ima dva čvora zapisali bismo kao stablo(koren, levičvor, desničvor). i tako izrazili relaciju između ovih elemenata. Svaki element dalje može da bude predikat za sebe, i tako gradimo izraz iznad.
Sledi nekoliko najvažnijih predikata koji opisuju binarno stablo i operacije nad njim.
a) Predikat kojim se proverava da li je struktura binarno stablo.
b_stablo(p).
b_stablo(st(X, L, D)):-b_stablo(L), b_stablo(D).
b) Predikat kojim se proverava da li se element nalazi u binarnom stablu.
element(X, st(X, L, D)).
element(X, st(S, L, D)):-element(X, L); element(X, D).
Specijalan slučaj binarnog stabla je uređeno binarno stablo u kojem su elementi u levom podstablu manji od glave a elementi u desnom pod stablu su veći od glave.
c) Predikat kojim se proverava da li se element nalazi u uređenom binarnom stablu.
element(X, st(X, L, D)).
element(X, st(G, L, D)):-X<G, element(X, L).
element(X, st(G, L, D)):-X=>G, element(X, D).
d) Predikat kojim se dodaje element u uređeno binarno stablo
dodaj(X, p, st(X, p, p)).
dodaj(X, st(G, L, D), st(G, L1, D)):-X<G, dodaj(X, L, L1).
dodaj(X, st(G, L, D), st(G, L, D1)):-X=>G, dodaj(X, D, D1).
e) Predikat kojim se briše element iz binarnog stabla.
brisi(X, st(X, p, D), D).
brisi(X, st(X, L, D), st(Ym, L1, D)):-najveci(L, Ym, L1).
brisi(X, st(Y, L, D), st(Y, L1, D)):-X<Y, brisi(X, L, L1).
brisi(X, st(Y, L, D), st(Y, L, D1)):-X>Y, brisi(X, D, D1).
najveci(st(Ym, L, p), Ym, L).
najveci(st(Y, L, D), Ym, st(Y, L, D1)):-najveci(D, Ym, D1).
f) Predikat za konverziju liste u uređeno binarno stablo
lista_stablo([], p).
lista_stablo([G|R], S):-lista_stablo(R, S1), dodaj(G, S1, S).
g) Predikat za konverziju binarnog stabla u listu.
stablo_lista(p, []).
stablo_lista(st(G, L, D), Rez)):-stablo_lista(L, L1),
stablo_lista(D, D1),
pripoji(L1, [G|D1], Rez).
h) Sortiranje liste
sortiraj(L, SL):-lista_stablo(L, S), stablo_lista(S, Sl).