Arbori binari

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


- Figura 3 -

Arborele binar complet este un arbore binar in care toate nivelurile sunt complete. Intr-un astfel de arbore, toatenodurile intermediare au exact doi fii si toate frunzele sunt situate pe acelasi nivel, ca in figura 4.


- Figura 4 -

Arborele binar aproape complet este un arbore binar in care toate nivelurile sunt complete, cu exceptia ultimului nivel, care este aproape complet. Toate nodurile lipsa de pe ultimul nivel sunt situate la sfarsitul 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, procedand in modul urmator: se considera ca radacina arborelui este primul element din tablou, t[0]. In continuare se plaseaza in tablou nodurile de pe nivelul 1, parcurse de la stanga la dreapta, apoi cele de nivel doi etc. Procedand astfel cu arborele binar din figura 5 se obtine tabloul urmator
 
A
B
C
D
E
F
G
H
I
J

Se poate usor arata ca indicii celor doi fii ai unui nod oarecare, de indice i,  se determina cu formulele:

is = 2*i+1
id = 2*i+2
unde is este indicele fiului stanga, iar id este indicele fiului dreapta

Indicele i al parintelui unui nod oarecare de indice k se determina cu formula

i = (k-1)/2
unde, evident, se considera numai partea intreaga a catului. 

Aplicand relatiile de mai sus, exista posibilitatea de a se parcurge arborele in ambele sensuri: atat in sens descendent, cat si ascendent.

Exemplu: Aplicand aceste relatii arborelui din tabloul de mai sus constatam ca:
    - fiii nodului C de indice 2 sunt nodurile de indici 5 si 6, respectiv F si G;
    - parintele nodurilor H si I (de indici 7 si 8) este nodul D (de indice 3).



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