Conceptul de arbore

Arborele este o structura de date ierarhizata, in care fiecare nod are un singur nod parinte si poate avea mai multe noduri fii. Exista un singur nod care nu are parinte, numit radacina. Nodurile care nu au fii se numesc frunze. Un exemplu de arbore este reprezentat in figura 1.


- 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).


- Figura 2 -

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati