Parcurgerea nodurilor este o tehnica de trecere sistematica de la un nod la altul,astfel incat sa se treaca prin toate nodurile arborelui intr-o ordine prestabilita. Este posibil sa se treaca de mai multe ori prin fiecare nod, dar vizitarea se face numai o data. Exista doua tehnici de parcurgere a arborilor: in adancime si in latime (pe niveluri).
Pentru a aplica tehnici iterative de vizitare a nodurilor unui arbore, in tehnologia Java se folosesc iteratori. Acestia sunt definiti, la fel ca in cazul colectiilor sau maparilor, prin clase care implementeaza interfata java.util.Iterator. La fiecare invocare a metodei Object next() a unui iterator, acesta intoarce obiectul de informatie continut in urmatorul nod care trebuie vizitat. Aceasta abordare creeaza o mare flexibilitate in utilizarea iteratiei, intrucat utilizatorul clasei de arbori este scutit de implementarea tehnicii de parcurgere a nodurilor in vederea vizitarii lor, concentrandu-si atentia numai asupra prelucrarii informatiei din noduri.
- Figura 2 -
Parcurgerea nodurilor incepe intotdeauna de la radacuina arborelui. Se parcurge apoi intregul subarbore din stanga, urmat de intregul subarbore din dreapta (daca acestia exista). Parcurgerea fiecarui subarbore se face in acelasi mod. Se observa, deci ca aceasta este o tehnica de parcurgere recursiva, bazata pe recursivitatea structurii de arbore. In figura 2 ordinea de parcurgere a nodurilor este urmatoarea: A, B, D, B -> E -> B -> A -> C -> F -> C -> A. Sagetile rosii reprezinta parcurgerea descendenta (trasarea) iar cele albastre parcurgerea ascendenta (revenirea). Parcurgerea intregului arbore se incheie in momentul in care s-a trecut prin toate nodurile si s-a revenit in radacina.
Pentru parcurgerea in adancime a arborelui, este necesar sa se memoreze
calea
pe care s-a ajuns de la radacina la nodul curent, pentru a se asigura revenirea
la nodurile deja parcurse. La inceputul parcurgerii, in stiva se pune radacina.
De cate ori se trece de la un nod la unul din fiii lui, fiul respectiv
este pus in stiva. Dupa ce au fost vizitati fiii, se revine la tatal nodului
curent, care este extras din stiva. Nodul curent se afla intotdeauna in
varful stivei. Parcurgerea se incheie cand stiva este goala. Iata etapele
parcurgerii in exemplul din figura 2:
|
|
Continutul stivei (varful este in dreapta) |
|
|
A |
|
|
A, B |
|
|
A, B, D |
|
|
A, B |
|
|
A, B, E |
|
|
A, B |
|
|
A |
|
|
A, C |
|
|
A, C, F |
|
|
A, C |
|
|
A |
|
|
Se observa ca inaltimea maxima a stivei este egala cu inaltimea arborelui.
Datorita folosirii stivei, nu este necesar ca, pentru a putea parcurge
arborele, in fiecare nod sa existe si o legatura catre tata.
In fisierul ArboreBinar.java este definita
clasa ArboreBinar. Pentru parcurgerea in adancime a arborelui a fost definit
un iterator sub forma clasei interioare ParcurgAdancime. Aceasta clasa
foloseste ca structura auxiliara o stiva realizata printr-o instanta a
clasei java.util.Stack. Ca elemente ale stivei se folosesc instante ale
clasei interioare ElemStiva, care contin doua campuri:
int FiuParcurs; Nod nodCurent; Primul camp contine un cod care indica ultimul fiu parcurs si care poate fi: 0 - pentru prima intrare in nod (nu s-a parcurs nici un fiu); 1 - a fost parcurs fiul stanga; 2 - a fost parcurs fiul dreapta. In acest mod, la scoaterea nodului din stiva se poate sti si modul in care s-a ajuns la nodul respectiv in timpul parcurgerii stivei. Nodul este instanta a clasei interioare Nod. Dam aici definirea claselor ElemStiva si ParcurgAdancime:
Pentru a se creea un iterator de parcurgere a arborelui in adancime, in clasa ArboreBinar a fost definita metoda
Mentionam ca clasa interioara ParcurgAdancime si metoda iteratorAdancime au fost declarate publice numai pentru a se putea face testarea lor. Daca clasa ArboreBinar este inclusa intr-o biblioteca, este recomandabil sa li se schimbe modul de acces in publuic sau eventual protected, deoarece au doar un rol auxiliar in realizarea tehnicilor de traversare a arborelui descrise in cele ce urmeaza. Un exemplu de aplicatie in care este testata parcurgerea in adancime a unui ArboreBinar este dat in fisierul TestArboreBinar.java. |
In cazul traversarii in preordine,
vizitarea unui nod se face la prima trecere prin acesta, deci inainte de
a fi parcursi cei doi subarbori. In exemplul din figura 2, ordinea
de vizitare a nodurilor este urmatoarea: A, B, D, E, C, F.
Pentru traversarea in preordine a arborelui binar, in clasa ArboreBinar
din fisierul ArboreBinar.java, prezentata
deja mai sus, s-a definit un iterator sub forma clasei interioare TraversPreordine.
Aceasta clasa foloseste pentru parcurgerea in adancime clasa interioara
auxiliara ParcurgAdancime.
In metoda hasNext() a acestei clase se sare peste toate nodurile pentru care numarul de fii parcursi este diferit de 0. In consecinta, la fiecare invocare a metodei next() este intors obiectul de informatie continut in urmatorul nod pentru care fiuParcurs==0. |
In cazul traversarii in inordine,
nodul este vizitat dupa parcurgerea subarborelui stang (daca exista), dar
inainte de parcurgerea subarborelui drept. In exemplul din figura 2,
ordinea de vizitare a nodurilor este urmatoarea: D, B, E,
A, F, C.
Pentru traversarea arborelui in inordine, in clasa ArboreBinar din
fisierul ArboreBinar.java s-a definit un
iterator sub forma clasei interioare TraversInordine. Aceasta clasa foloseste,
pentru parcurgerea in adancime a arborelui, clasa interioara auxiliara
ParcurgAdancime.
Pentru a se testa daca elementul curent, intors de iteratorul ParcurgAdancime, indeplineste conditiile pentru a fi vizitat in inordine, a fost prevazuta metoda boolean vizitInordine(). In metoda hasNext() se sare peste toate elementele parcurse care nu satisfac acest test. In consecinta, la fiecare invocare, metoda next() intoarce obiectul de informatie al urmatorului nod care poate fi vizitat in inordine. Crearea unui astfel de iterator se face prin metoda Iterator iteratorInordine(). |
In cazul traversarii in postordine,
vizitarea se face la ultima trecere prin nodul respectiv, deci dupa ce
au fost parcursi ambii subarbori (daca ei exista). In exempul din figura
2, ordinea de
vizitare a nodurilor este urmatoarea: D,
E, B, F, C, A.
Pentru traversarea arborelui in postordine, in clasa ArboreBinar din
fisierul ArboreBinar.java a fost definit
un iterator sub forma clasei interioare TraversPostordine. Aceasta clasa
foloseste, pentru parcurgerea in adancime a arborelui, clasa interioara
auxiliara ParcurgAdancime.
La fel ca in cazul precedent, pentru a testa daca un nod parcurs in adancime indeplineste conditiile de a fi vizitat in postordine, s-a definit metoda boolean vizitPostordine(). In metoda hasNext() a clasei TraversPostordine se sare peste nodurile care nu indeplinesc acest test. In consecinta, la fiecare invocare a metodei Object next(), este intors obiectul de informatie din urmatorul nod care poate fi vizitat in postordine. |
Metode recursive de traversare a arborilor binari in adancimePentru realizarea celor trei tehnici de traversare a arborilor descrise mai sus, este foarte comoda implementarea ca metode recursive. In acest caz nu se mai foloseste in mod explicit o stiva ca structura auxiliara, deoarece metodele recursive folosesc implicit stiva sistemului de calcul (in cazul de fata cea a masinii virtuale Java).In cazul implementarii arborelui
binar ca structura recursiva, se pot folosi urmatoarele metode, in
care vizit(Object obj) este metoda de vizitare a obiectului de
informatie continut in radacina arborelui sau subarborelui respectiv:
Implementarea recursiva a traversarii este simpla intrucat, in acest
caz, fiecare din cei doi fii este tot un subarbore.
In cazul implementarii arborelui binar prin noduri si legaturi traversarea se poate face, de asemenea prin metode recursive. Un exemplu este dat in clasa ArboreBinar din fisierul ArboreBinar.java, in care s-au introdus metode recursive pentru traversarea arborelui in preordine, inordine si postordine si o metoda recursiva pentru reprezentarea arborelui sub forma de sir, in care fiecare subarbore este cuprins intr-o pereche de paranteze. Pentru traversarea in preordine se folosesc urmatoarele doua metode:
Pentru traversarea in inordine se procedeaza in mod similar, numai ca, in metoda private void inordine(List lista, Nod nod) se traverseaza mai intai subarborele din stanga, apoi se pune in lista informatia din nodul radacina si la sfarsit se traverseaza subarborele din dreapta.
In fine, la traversarea in postordine, se traverseaza mai intai cei
doi subarbori, dupa care se pune in lista informatia din nodul radacina.
Pentru conversia arborelui intr-un sir, s-a adoptat conventia de reprezentare
cu paranteze. In aceasta conventie, de cate ori se trece catre un nivel
superior se deschide o paranteza, iar cand se revine la nivelul superior
se inchide paranteza respectiva. In consecinta, fiecare subarbore este
cuprins intr-o pereche de paranteze. Daca un nod are un singur fiu, fiul
lipsa se reprezinta printr-o pereche de paranteze vida (). Pentru
reprezentarea arborelui ca sir a fost redefinita metoda
Rezultatul aplicarii acestor metode se poate urmari la executarea aplicatiei de testare din fisierul TestArboreBinar.java. |
Pentru a parcurge un arbore in latime (pe niveluri), se foloseste ca
structura auxiliara o coada. La inceput se pune in coada radacina. Se considera
ca nodul curent este cel din capul cozii. Se pun in coada toti fiii nodului
curent, dupa care acesta se scoate din coada. Se continua astfel pana cand
coada ramane vida. Iata cum evolueaza traversarea arborelui in latime in
exemplul din
figura 2:
|
|
Continutul cozii (capul este in stanga) |
|
|
A |
|
|
B, C, D, E |
|
|
C, D, E, F |
|
|
D, E, F |
|
|
E, F |
|
|
F |
|
|
Lungimea cozii este egala cu latimea arborelui (numarul maxim de noduri
de pe acelasi nivel).
Pentru traversarea arborilor in latime (pe niveluri), in clasa Aebore
binar din fisierul
ArboreBinar.java s-a
definit un iterator sub forma clasei interioare TraversLatime. Ca structura
de date auxiliara, aceasta clasa foloseste o coada, implementata printr-o
instanta a clasei java.util.LinkedList.
Acest iterator poate fi obtinut prin metoda Iterator iteratorLatime() a clasei ArboreBinar. In fisierul TestArboreBinar.java este data aplicatia de testare a tuturor tehnicilor de traversare a arborelui binar. |