- 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) completUn 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
Se poate usor arăta că indicii celor doi fii ai unui nod oarecare, de indice i, se determină cu formulele: id = 2*i+2 Indicele i al părintelui unui nod oarecare de indice k se determină cu formula 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ă: |