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