- Figura 1 -
Nodul A este rădăcina arborelui. Nodurile B, C și D sunt fiii nodului A, iar nodul A este părintele nodurilor B, C și D. Nodurile E și F sunt fiii nodului B, iar B este părintele nodurilor E și F. Nodurile E, F, K, L, H, I și M sunt frunzele arborelui. Nodurile A, C și G sunt ascendenții nodurilor K și L, iar nodurile K si L sunt descendenții nodurilor A, C sau G. Se Spunem că nodul K este descendentul nodului A dacă există o cale descendentă (de la părinte la fiu) de la A catre K.
Arborele poate fi constituit și dintr-un singur nod care, în acest caz, este atât rădăcină, cât și frunză.
După poziția lor în arbore, nodurile sunt situate pe mai multe niveluri. Se consideră că rădăcina arborelui are nivelul 0. Nivelul oricăruia din celelalte noduri arată numărul de legături descendente parcurse de la rădăcina arborelui până la nodul respectiv. De exemplu, nodul K din figura 1 este situat pe nivelul 3.
Fiecare nod al arborelui este rădăcina unui subarbore. În consecință, arborele este o structură de date recursivă. Chiar și frunza este rădăcina unui subarbore care conține un singur nod.
Structura de arbore modelează multe structuri ierarhice existente în
lumea reală. Iată numai câteva exemple:
- organigrama unei instituții sau întreprinderi;
- structura unui produs tehnic (produsul este un ansamblu constituit
din subansamble, care sunt constituite fiecare din alte subansamble,
până se ajunge la piese indivizibile);
- structura unui desen tehnic.
În informatică există, de asemenea, structuri de date care se
reprezintă cel mai comod sub forma de arbore, dintre care unele vor fi
studiate de noi în cele ce urmează.
Un exemplu poate fi arborele sintactic al unei expresii, în
care nodurile intermediare sunt operatori, iar frunzele sunt date
atomice. Astfel, în figura 2 este reprezentat arborele sintactic
al expresiei (5+2*4)*(7-15/3).
Într-un arbore sintactic, operatorii din nodurile fii se aplică întotdeauna înaintea celui din nodul părinte. În consecință, arborele indică nu numai ce operații se fac pentru evaluarea expresiei, ci și în ce ordine se fac. |