Extras din laborator

Lucrarea nr. 1

Structura de arbore. Arbori generalizati

1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se pot efectua asupra ei.

2. Aspecte teoretice.

2.1. Arbori si traversarea lor

Prin arbore se întelege o multime de n noduri de acelasi tip care, daca nu este vida, are un anumit nod numit radacina, iar restul nodurilor formeaza un numar finit de arbori, doi câte doi disjuncti.

Numarul fiilor unui nod formeaza gradul nodului. Gradul maxim al nodurilor unui arbore se numeste gradul arborelui. Adâncimea unui nod este lungimea drumului unic de la radacina pâna la acel nod.

Prin traversarea unui arbore se întelege executia unei anumite operatii asupra tuturor nodurilor arborelui. În timpul vizitarii nodurile sunt vizitate într-o anumita ordine, astfel încât ele pot fi considerate ca si cum ar fi integrate într-o lista liniara.

Exista trei moduri de ordonare (traversare) a unei structuri de arbore, numite preordine, inordine si postordine.

Cele trei moduri de traversare se definesc recursiv în felul urmator:

- daca arborele A este nul, atunci traversarea lui A în preordine, inordine si postordine se reduce la lista vida.

- daca A se reduce la un singur nod, atunci nodul însusi reprezinta traversarea în oricare din cele trei moduri.

- pentru restul cazurilor, fie arborele A cu radacina R si subarborii acestuia A1, A2,...,Ak (figura 1.2). În acest caz:

1. Traversarea în preordine a arborelui A presupune traversarea radacinii R urmata de traversarea în preordine a lui A1, apoi de traversarea în preordine a lui A2, si asa mai departe pâna la Ak inclusiv.

2. Traversarea în inordine presupune parcurgerea în inordine a subarborelui A1, urmata de nodul radacina R si, în continuare, parcurgerea în inordine ale subarborilor A2, A3,..., Ak.

3. Traversarea în postordine a arborelui A consta în traversarea în postordine a subarborilor A1, A2,..., Ak si, în final, traversarea nodului radacina R.

De exemplu, pentru arborele reprezentat în figura 1.1, traversarea acestuia în cele trei moduri are ca rezultat urmatoarele:

preordine: 1, 2, 5, 6, 10, 11, 12, 3, 4, 7, 8, 9, 13, 14

inordine: 5, 2, 10, 6, 11, 12, 1, 3, 7, 4, 8, 13, 9, 14

postordine: 5, 10, 11, 12, 6, 2, 3, 7, 8, 13, 14, 9, 4, 1

2.2. Implementarea arborilor generalizati prin indicator spre parinte

O maniera simpla de implementare o reprezinta utilizarea unui tablou (A), în care fiecare intrare A[I] contine un indice la parintele nodului I. Deci, daca A[I].indice = J, atunci nodul J este parintele nodului I, exceptie facând cazul în care nodul I este chiar radacina arborelui.

Aceasta modalitate de implementare face uz de proprietatea arborilor ca orice nod are un singur parinte. Reprezentarea prin indicator spre parinte are însa dezavantajul implementarii dificile a operatiilor legate de fii. Pentru a facilita acest lucru, se impune stabilirea unei ordini artificiale a nodurilor în tablou, respectând urmatoarele reguli:

- numerotarea fiilor unui nod se face numai dupa ce nodul a fost numerotat; în consecinta, fiii vor avea întotdeauna un numar de ordine mai mare decît nodul parinte;

- numerele fiilor cresc de la stânga la dreapta.

În continuare, indicele parintelui este indicele nodului parinte în tabloul A, iar nodul radacina va avea ca parinte indicele –1. Pentru arborele din figura 1.1, în aceasta reprezentare, avem: