- 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) completUn 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
Se poate usor arata ca indicii celor doi fii ai unui nod oarecare, de indice i, se determina cu formulele: id = 2*i+2 Indicele i al parintelui unui nod oarecare de indice k se determina cu formula 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:
|