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. |