Arbori binari

Arborele binar este un arbore, în care fiecare nod are cel mult doi fii. Un exemplu de arbore binar este reprezentat în figura 3.


- Figura 3 -

Arborele binar complet este un arbore binar, în care toate nivelurile sunt complete. Într-un astfel de arbore, toate nodurile intermediare au exact doi fii și toate frunzele sunt situate pe același nivel, ca în figura 4.


- Figura 4 -

Arborele binar aproape complet este un arbore binar, în care toate nivelurile sunt complete, cu excepția ultimului nivel, care este aproape complet. Toate nodurile lipsă de pe ultimul nivel sunt situate la sfârșitul acestuia. Un exemplu de arbore binar aproape complet este dat in figura 5.


- Figura 5 -



 
 
 
 

Reprezentarea ca tablou a arborelui binar (aproape) complet

Un arbore binar complet sau aproape complet poate fi reprezentat ca tablou, procedând în modul următor: se consideră că rădăcina arborelui este primul element din tablou, t[0]. În continuare, se plasează în tablou nodurile de pe nivelul 1, parcurse de la stânga la dreapta, apoi cele de nivel doi etc. Procedând astfel cu arborele binar din figura 5, se obține tabloul următor
 
A
B
C
D
E
F
G
H
I
J

Se poate usor arăta că indicii celor doi fii ai unui nod oarecare, de indice i,  se determină cu formulele:

is = 2*i+1
id = 2*i+2
unde is este indicele fiului stânga, iar id este indicele fiului dreapta

Indicele i al părintelui unui nod oarecare de indice k se determină cu formula

i = (k-1)/2
unde, evident, se consideră numai partea întreaga a câtului. 

Aplicând relațiile de mai sus, există posibilitatea de a se parcurge arborele în ambele sensuri: atât în sens descendent, cât și ascendent.

Exemplu: Aplicând aceste relații arborelui din tabloul de mai sus constatăm că:
    - fiii nodului C de indice 2 sunt nodurile de indici 5 și 6, respectiv F și G;
    - părintele nodurilor H și I (de indici 7 și 8) este nodul D (de indice 3).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați