Lucrarea nr. 4
Obiecte recursive. Arbori







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:

  1. Sa se defineasca predicatele care realizeaza operatiile de baza asupra unui arbore binar ordonat (adauga, sterge). In ce conditii poate lucra predicatul de adaugare ca predicat de stergere?
  2. Sa se defineasca un predicat care realizeaza conversia bidirectionala intre o expresie aritmetica si arborele corespunzator, care are ca si noduri interne operatorii, iar in frunze numerele din expresie. Operatorii acceptati sint: +, - (binar si unar), *, /.
  3. Sa se implementeze tipul de date multime prin arbore binar ordonat (impreuna cu operatiile standard pe multimi).