Implementarea arborilor binari

Am aratat in capitolul precedent ca arborii binari (aproape) completi pot fi implementati ca tablouri. In cazul general al arborilor binari o astfel de implementare nu mai este eficienta. Intr-adevar, desi s-ar putea implementa un arbore binar incomplet sub forma de tablou la fel ca unul complet, dar lasand libere locurile nodurilor lipsa, o astfel de implementare ar fi, de cele mai multe ori, nerationala din punct de vedere al consumului de memorie.

In cazul general, un arbore binar este implementat printr-un set de noduri, intre care exista legaturi ierarhice de la tata la cei doi fii, ca in figura 1. Acolo unde fiul nu exista, legatura respectiva este nula.


- Figura 1 -

Fiecare nod contine o anumita informatie, atasata nodului respectiv, si doua legaturi: catre fiul din stanga si fiul din dreapta. Uneori, fiecare nod contine si o legatura catre nodul-tata.
 
 

Implementarea arborelui binar ca o structura formata din noduri si legaturi

In limbajul Java, structura de mai sus poate fi programata sub forma unei clase cu urmatoarea structura:

    public class ArboreBinar {
      private Nod radacina;

      class Nod {
        Object info;
        Nod fiuStanga, fiuDreapta;

        // Constructorii si metodele nodului

      }

      // Constructorii si metodele clasei arbore
    }

Clasa contine un singur camp privat: 
    radacina - referinta la nodul radacina;

Daca arborele este vid, radacina are valoarea null. Metodele clasei ArboreBinar trebuie sa asigure accesul la orice nod pornind de la radacina. Pot exista, de asemenea, metode pentru punerea sau eliminarea de noduri. 

Nodurile arborelui binar sunt instante ale clasei interioare ArboreBinar.Nod. Aceasta clasa contine trei campuri: 
    info - referinta la un Object, care contine informatia aferenta nodului respectiv;
    fiuStanga, fiuDreapta - referinte catre nodurile fii.
Metodele clasei Nod trebuie sa asigure accesul la informatia din campul info si modificarea acesteia.

Implementarea arborelui binar ca o structura recursiva

O alta implementare a arborelui binar se poate face apeland la faptul ca acesta este o structura recursiva: orice nod al acestuia este radacina unui subarbore, care este tot un arbore binar. Chiar si frunzele pot fi considerate ca arbori cu un singur nod. In consecinta, arborele binar poate fi programat in Java sub forma urmatoare:

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

      // Constructorii si metodele clasei ArboreBinarRec

    }

In acest caz, nu mai exista o clasa pentru noduri. Campul info al arborelui contine informatia atasata radacinii acestuia, iar campurile subarboreStanga si subarboreDreapta contin referinte catre cei doi subarbori-fii. Metodele trebuie sa asigure accesul la informatia din radacina (inclusiv modificarea acesteia) si la cei doi subarbori. O asemenea reprezentare a arborelui faciliteaza utilizarea de metode recursive.



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