Implementarea arborilor binari

Am arătat în capitolul precedent că arborii binari (aproape) compleți pot fi implementați ca tablouri. În cazul general al arborilor binari, o astfel de implementare nu mai este eficientă. Într-adevar, deși s-ar putea implementa un arbore binar incomplet sub formă de tablou la fel ca unul complet, dar lăsând libere locurile nodurilor lipsă, o astfel de implementare ar fi, de cele mai multe ori, nerațională din punct de vedere al consumului de memorie.

În cazul general, un arbore binar este implementat printr-un set de noduri, între care există legături ierarhice de la tată la cei doi fii, ca în figura 1. Acolo unde fiul nu există, legatura respectivă este nulă.


- Figura 1 -

Fiecare nod conține o anumită informație, atașată nodului respectiv, și două legături: către fiul din stânga și fiul din dreapta. Uneori, fiecare nod conține și o legatură către nodul-tată.
 
 

Implementarea arborelui binar ca o structură formată din noduri și legături

În limbajul Java, structura de date de mai sus poate fi programată sub forma unei clase cu urmatoarea structură:

    public class ArboreBinar {
      private Nod radacina;

      class Nod {
        Object info;
        Nod fiuStanga, fiuDreapta;

        // Constructorii și metodele nodului

      }

      // Constructorii și metodele clasei arbore
    }

Clasa conține un singur câmp privat: 
    radacina - referința la nodul rădăcină;

Dacă arborele este vid, radacina are valoarea null. Metodele clasei ArboreBinar trebuie să asigure accesul la orice nod pornind de la rădăcină. Pot exista, de asemenea, metode pentru punerea sau eliminarea de noduri. 

Nodurile arborelui binar sunt instanțe ale clasei interioare ArboreBinar.Nod. Această clasă conține trei câmpuri: 
    info - referința la un Object, care conține informația aferentă nodului respectiv;
    fiuStanga, fiuDreapta - referințe la nodurile fii.
Metodele clasei Nod trebuie să asigure accesul la informația din câmpul info și modificarea acesteia.

Implementarea arborelui binar ca o structură recursivă

O altă implementare a arborelui binar se poate face apelând la faptul că acesta este o structură recursivă: orice nod al acestuia este radacina unui subarbore, care este tot un arbore binar. Chiar și frunzele pot fi considerate ca arbori cu un singur nod. În consecință, arborele binar poate fi programat în Java sub forma următoare:

    public class ArboreBinRec {
      Object info;
      ArboreBinRec subarboreStanga, subarboreDreapta;

      // Constructorii și metodele clasei ArboreBinarRec

    }

În acest caz, nu mai există o clasă pentru noduri. Câmpul info al arborelui conține informația atașata rădăcinii acestuia, iar câmpurile subarboreStanga și subarboreDreapta conțin referințe către cei doi subarbori-fii. Metodele trebuie să asigure accesul la informația din rădăcină (inclusiv modificarea acesteia) și la cei doi subarbori. O asemenea reprezentare a arborelui facilitează utilizarea de metode recursive.



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