Lucrarea nr.1

TDA ARBORE GENERALIZAT

1.Definitii

Prin arbore se intelege o multime de n>=0 noduri de acelasi tip, care poate fi vida (arbore vid) sau formata dintr-un nod numit radacina, restul nodurilor formand un numar finit de arbori (numiti subarbori), doi cate doi disjuncti.

Din definitie rezulta ca structura de date arbore este recursiva, permitand prelucrarea simpla a acestei structuri cu ajutorul unor algoritmi recursivi. Orice nod al unui arbore e radacina unui arbore partial.

Succesorii directi ai unui nod se numesc fiii sai, el fiind nodul tata, iar succesorii sai directi sunt frati intre ei.

Intr-o structura de arbore, se definesc niveluri astfel: radacina formeaza nivelul 1, fiii sai nivelul 2, si asa mai departe, fiii nodurilor de pe nivelul n, formeaza nivelul n+1.

Nivelul maxim se numeste inaltimea arborelui.

Numarul fiilor unui nod se numeste gradul acelui nod, iar gradul maxim al nodurilor unui arbore se numeste gradul arborelui. Un nod de grad 0 (fara fii) se numeste terminal (frunza), restul fiind noduri interne (avand cel putin un fiu).

Daca n1,n2,...,nk este o secventa de noduri apartinand unui arbore, astfel incat ni este parintele lui ni+1 (i=1,k-1), ea se numeste drum sau cale de la nodul n1 la nodul nk.

Daca exista un drum de la nodul a la b, a se numeste stramos al lui b, iar b descendent al lui a.

Inaltimea unui nod este lungimea celui mai lung drum de la nodul respectiv la unul terminal.

Adancimea unui nod e lungimea drumului de la radacina la nodul respectiv.

Lungimea drumului unui arbore sau lungimea drumului intern (P) este suma adancimilor tuturor nodurilor, care este egala cu suma produselor dintre numarul de noduri de pe fiecare nivel si numarul nivelului: unde

n-numarul de noduri
ai-adancimea nodului i
m-adancimea arborelui
ni-numarul de noduri de pe nivelul i.

Lungimea medie a drumului, Pm, este raportul dintre lungimea drumului intern si numarul de noduri : Pm=P/n.

2.Traversarea arborilor

Prin traversarea unui arbore se intelege efectuarea unei anumite operatii asupra tuturor nodurilor arborelui.

In timpul traversarii, nodurile vor fi vizitate intr-o anumita ordine, deci pot fi considerate ca si cum ar fi integrate intr-o lista liniara.

Exista trei moduri de traversare (liniarizare) a unui arbore numite preordine, inordine si postordine, definite recursiv astfel:

daca arborele A este vid, ordonarea lui A in pre-,in- sau postordine se reduce la lista vida;
daca A este format dintr-un singur nod, nodul insusi este traversarea lui A in oricare din cele trei variante;
pentru restul cazurilor, fie A arborele cu radacina R, avand subarborii A1, A2, ... Ak; traversarea lui A in :
- preordine- inseamna traversarea lui R urmata de traversarea in preordine a lui A1, apoi A2, si asa mai departe pana la Ak;
- inordine- inseamna traversarea in inordine a lui A1, apoi a lui R, si apoi a lui A2, pana la Ak;
- postordine- inseamna traversarea in postordine a lui A1 pana la Ak si apoi traversarea radacinii R.

Traversarile pot fi realizate in maniera recursiva sau nerecursiva (folosind o stiva ).

O metoda practica de traversare : se imagineaza parcurgerea arborelui in sens trigonometric:

pentru preordine - nodurile se prelucreaza prima data cand sunt intalnite;
pentru postordine - ultima data;
pentru inordine - se prelucreaza un nod terminal la prima intalnire, unul interior, la a doua.

Exemplu: Se considera arborele generalizat din figura 1. Fig. 1. Arbore generalizat

Parcurgerea in preordine genereaza secventa: a,b,e,f,c,d,g,h,i

Parcurgerea in postordine genereaza secventa: e,f,b,c,g,h,i,d,a

Parcurgerea in inordine genereaza secventa: e,b,f,a,c,g,d,h,i

3.Operatorii TDA arbore generalizat

INITIALIZEAZa(A) - face vid arborele A;
TATA(N,A) - returneaza tatal nodului N in arborele A; daca N e chiar radacina, se returneaza nodul vid;
PRIMUL_FIU(N,A) - returneaza cel mai din stanga fiu al nodului N; daca N e terminal, returneaza nodul vid;
FRATE_DREPT(N,A) - returneaza nodul care are acelasi parinte ca N si apare imediat in dreapta lui N;
CHEIE(N,A) - returneaza cheia nodului N;
CREAZAi(v,A1,A2,...,Ai) - e una din functiile unei familii, i=0,1,2,...; genereaza un nod nou R cu cheia v, asociindu-i i fii, radacinile arborilor A1,A2,...; in final se genereaza arborele cu radacina R;
RADACINA(A) - returneza nodul ce e radacina arborelui A sau nodul vid daca arborele e vid;
TRAVERSEAZA(A) - parcurge toate nodurile arborelui.

4.Tehnici de implementare a TDA arbore

4.1.Implementarea arborilor cu ajutorul tipului tablou

Fie A un arbore cu n noduri numerotate 1,2,...,n. Cea mai simpla maniera de implementare e printr-un tablou in care fiecare element are doua campuri: unul reprezentand valoarea cheii nodului respectiv, celalalt un cursor la parinte (numarul nodului parinte - campul parinte pentru nodul radacina va fi 0).

type nod = record
             cheie : tip_cheie;
             parinte : integer
           end;
     arbore=array [1..n] of nod;

Pentru a da acuratete reprezentarii, se impune o ordine artificiala a nodurilor in tablou, respectand conventiile:

- numerotarea fiilor se face numai dupa cea a parintelui;

- numerele fiilor cresc de la stanga la dreapta.

Implementarea este avantajoasa pentru operatorul TATA, dar foarte laborioasa pentru operatorul CREAZa. Fig.2 Exemplu: memorarea arborelui intr-un tablou "indicator la parinte"

Exemplu: pentru arborele din figura 1, continutul tabloului de indicatori spre parinte este dat in figura 2.

4.2.Implementarea arborilor cu ajutorul listelor

Se creaza pentru fiecare nod o lista a fiilor sai. Pentru ca gradele nodurilor unui arbore sunt diferite (numarul fiilor este diferit), se impune ca fiind mai potrivita utilizarea listelor inlantuite.

Se va implementa deci arborele printr-un tablou de inceputuri ale listelor fiilor, cu cate o intrare in tablou pentru fiecare nod al arborelui.

Exista doua modalitati de implementare:

a) in lista fiecarui nod se pastreaza cheile nodurilor fii :

type tip_cheie = {integer};
        lista=^nodlista;
        nodlista = record
                      cheie:tip_cheie;
                      urm:lista
                   end;

       arbore = record
                    tablou_inceputuri:array [1..maxnod] of
	                             record
	                              cheie:tip_cheie;
                                      inceput:lista
                                     end;
                     radacina:tip_cheie
                 end;

b) in lista fiecarui nod se pastreaza cursorii spre nodurile fii ( in declaratiile de mai sus se modifica tipul nodlista ) :

  type nodlista = record
                      pozitie:1..maxnod;
                      urm:lista
       end;

Exemplu: Pentru arborele din figura 1, continutul structurii de date este prezentat in figura 3. Fig. 3. Arbore generalizat implementat cu lista

4.3.Implementarea arborelui bazata pe relatiile "primul-fiu" si "frate- drept"

E o implementare avantajoasa in care intr-o tabela Zona se pastreaza in intrarea rezervata fiecarui nod i, valoarea cheii, numarul nodului ce reprezinta primul fiu (valoarea 0 in intrarea unui nod terminal) si numarul nodului ce reprezinta fratele drept al nodului din intrare (0 daca nodul din intrare este ultimul fiu). Deci ultimele doua campuri sunt cursori in aceeasi tabela Zona. Arborele se va reprezenta printr-un cursor la Zona, indicand nodul radacina al arborelui.

type arbore=0..maxnod; {0 daca arborele este vid}
     cursor=0..maxnod;

var  Zona:array [1..maxnod] of  record
                                  cheie:tip_cheie;
                                  primul_fiu,frate_drept:cursor
                                 end;
     radacina : arbore;

Varianta este improprie implementarii operatorului TATA, necesitand baleierea intregii tabele Zona. Pentru o implementare eficienta, se poate adauga un al patrulea camp - tata, reprezentand cursorul spre nodul parinte.

Exemplu: pentru arborele considerat si in exemplele anterioare, continutul tabloului Zona este prezentat in figura 4. Fig. 4. Implementarea bazata pe relatiile

4.4.Implementarea arborelui ca multilista

Fiecare nod din arbore va contine, pe langa cheie, pointeri spre nodurile tata, primul fiu si frate drept. In Anexa 3 se prezinta o varianta de implementare a arborilor generalizati in C++, folosind structuri dinamice.

Exemplu: pentru arborele considerat in exemplele anterioare, continutul unei structuri multilista este prezentat in figura 5: Fig. 5. Arbore generalizat reprezentat printr-o multilista