Definitia recursiva a structurii din Prolog ne permite sa reprezentam obiecte recursive cum sunt arborii sau listele.
Exista mai multe posibilitati de reprezentare a unui arbore binar in termeni Prolog. O prima varianta este de a considera radacina ca functorul termenului si subarborii ca argumente. In acest caz insa, accesul la nodurile interioare este dificil si se foloseste numai in situatia in care putem avea un numar mic si cunoscut de atomi care pot fi noduri interioare. Un exemplu in acest sens il reprezinta expresiile aritmetice.
O reprezentare mai avantajoasa este urmatoarea: alegem un simbol special
pentru arborele vid, si un functor cu ajutorul caruia construim arborele
binar din
cele trei componente (radacina si cei doi subarbori).
a
/ \
b c
\
d
In aceasta maniera, arborele din figura este reprezentat prin termenul Prolog
t(a, t(b, empty, empty), t(c, empty, t(d, empty, empty))).
Uzual, predicatele care opereaza asupra acestor obiecte urmaresc structura argumentului. De exemplu, predicatul de apartenenta poate fi definit sub forma:
in( t(X,_,_), X).
in( t(_, Left,_), X) :- in(Left,X).
in( t(_, _, Right), X) :- in(Right,X).
Probleme: