- Figura 1 -
Nodul A este radacina arborelui. Nodurile B, C si D sunt fiii nodului A, iar nodul A este parintele nodurilor B, C si D. Nodurile E si F sunt fiii nodului B, iar B este parintele nodurilor E si F. Nodurile E, F, K, L, H, I si M sunt frunzele arborelui. Nodurile A, C si G sunt ascendentii nodurilor K si L, iar nodurile K si L sunt descendentii nodurilor A, C sau G. Se Spunem ca nodul K este descendentul nodului A saca exista o cale descendenta (de la parinte la fiu) de la A catre K.
Arborele poate fi constituit si dintr-un singur nod care, in acest caz, este atat radacina, cat si frunza.
Dupa pozitia lor in arbore, nodurile sunt situate pe mai multe niveluri. Se considera ca radacina arborelui are nivelul 0. Nivelul oricaruia din celelalte noduri arata numarul de legaturi descendente parcurse de la radacina arborelui pana la nodul respectiv. De exemplu, nodul K din figura 1 este situat pe nivelul 3.
Fiecare nod al arborelui este radacina unui subarbore. In consecinta, arborele este o structura de date recursiva. Chiar si frunza este raracina unui subarbore care contine un singur nod.
Structura de arbore modeleaza multe structuri ierarhice existente in
lumea reala. Iata numai cateva exemple:
- organigrama unei institutii sau intreprinderi;
- structura unui produs tehnic (produsul este un ansamblu constituit
din subansamble, care sunt constituite fiecare din alte subansamble, pina
se ajunge la piese indivizibile);
- structura unui desen tehnic.
In informatica exista, de asemenea, structuri de date care se reprezinta
cel mai comod sub forma de arbore, dintre care unele vor fi studiate de
noi in cele ce urmeaza.
Un exemplu poate fi arborele sintactic al unei expresii, in care nodurile
intermediare sunt operatori, iar frunzele sunt date atomice. Astfel, in
figura
2 este reprezentat arborele sintactic al expresiei (5+2*4)*(7-15/3).
Intr-un arbore sintactic operatorii din nodurile fii se aplica intotdeauna inaintea celui din nodul parinte. In consecinta, arborele indica nu numai ce operatii se fac pentru evaluarea expresiei, ci si in ce ordine. |