Parcurgerea nodurilor este o tehnică de trecere sistematică de la un nod la altul, astfel încât să se treaca prin toate nodurile arborelui într-o ordine prestabilită. Este posibil să se treacă de mai multe ori prin fiecare nod, dar vizitarea nodului se face numai o dată. Există două tehnici de parcurgere a arborilor: în adâncime și în lățime (pe niveluri).
Pentru a aplica tehnici iterative de vizitare a nodurilor unui arbore, în tehnologia Java se folosesc iteratori. Aceștia sunt definiți, la fel ca în cazul colecțiilor sau mapărilor, prin clase care implementează interfața java.util.Iterator. La fiecare invocare a metodei Object next() a unui iterator, acesta intoarce obiectul de informație conținut în urmatorul nod care trebuie vizitat. Această abordare creează o mare flexibilitate în utilizarea iterației, întrucât utilizatorul clasei de arbori este scutit de implementarea tehnicii de parcurgere a nodurilor în vederea vizitării lor, concentrându-și atentia numai asupra prelucrării informației din noduri.
- Figura 2 -
Parcurgerea nodurilor începe întotdeauna de la rădăcina arborelui. Se parcurge apoi întregul subarbore din stânga, urmat de întregul subarbore din dreapta (dacă aceștia există). Parcurgerea fiecarui subarbore se face în același mod. Se observă, deci, că aceasta este o tehnică de parcurgere recursivă, bazată pe recursivitatea structurii de arbore. În figura 2, ordinea de parcurgere a nodurilor este urmatoarea: A, B, D, B -> E -> B -> A -> C -> F -> C -> A. Săgețile roșii reprezintă parcurgerea descendentă (trasarea) iar cele albastre - parcurgerea ascendentă (revenirea). Parcurgerea întregului arbore se încheie în momentul în care s-a trecut prin toate nodurile și s-a revenit în rădăcină.
Pentru parcurgerea în adâncime a arborelui, este necesar să se
memoreze calea pe care s-a ajuns de la rădăcină la nodul
curent, pentru a se asigura revenirea la nodurile deja parcurse. În
acest scop, se folosește o stivă. La începutul parcurgerii, în stivă se
pune rădăcina. De câte ori se trece de la un nod la unul din fiii lui,
fiul respectiv este pus în stivă. După ce au fost vizitați fiii, se
revine la tatăl nodului curent, care este extras din stivă. Nodul
curent se află întotdeauna în vârful stivei. Parcurgerea se încheie
când stiva este vidă. Iată etapele parcurgerii în exemplul din figura
2:
|
|
Continutul stivei (vârful este în dreapta) |
|
|
A |
|
|
A, B |
|
|
A, B, D |
|
|
A, B |
|
|
A, B, E |
|
|
A, B |
|
|
A |
|
|
A, C |
|
|
A, C, F |
|
|
A, C |
|
|
A |
|
|
Se observă că înălțimea maximă a stivei este egală cu înălțimea
arborelui. Datorită folosirii stivei, nu este necesar ca, pentru a
putea parcurge arborele, în fiecare nod să existe și o legatura către
tată.
In fișierul ArboreBinar.java
este definită clasa ArboreBinar. Pentru parcurgerea în adâncime a
arborelui, a fost definit un iterator sub forma clasei interioare
ParcurgAdancime. Această clasă folosește ca structură auxiliară o stivă
realizată printr-o instanță a clasei java.util.Stack. Ca elemente ale
stivei se folosesc instanțe ale clasei interioare ElemStiva, care
conțin două câmpuri: int FiuParcurs; Nod nodCurent; Primul câmp conține un cod care indică ultimul fiu parcurs și care poate fi: 0 - pentru prima intrare în nod (nu s-a parcurs nici un fiu); 1 - a fost parcurs fiul stânga; 2 - a fost parcurs fiul dreapta. În acest mod, la scoaterea nodului din stivă se poate ști și modul în care s-a ajuns la nodul respectiv în timpul parcurgerii stivei. Nodul este instanță a clasei interioare Nod. Dăm aici definirea claselor ElemStiva și ParcurgAdancime:
Pentru a se creea un iterator de parcurgere a arborelui în adancime, în clasa ArboreBinar a fost definită metoda
Menționăm că clasa interioară ParcurgAdancime și metoda iteratorAdancime au fost declarate publice numai pentru a se putea face testarea lor. Dacă clasa ArboreBinar este inclusă într-o bibliotecă, este recomandabil să li se schimbe modul de acces în private sau eventual protected, deoarece au doar un rol auxiliar in realizarea tehnicilor de traversare a arborelui descrise în cele ce urmează. Un exemplu de aplicație în care este testata parcurgerea în adâncime a unui ArboreBinar este dat in fișierul TestArboreBinar.java. |
În cazul traversării în preordine,
vizitarea unui nod se face la prima trecere prin acesta, deci înainte
de a fi parcurși cei doi subarbori. În exemplul din figura 2,
ordinea de vizitare a nodurilor este următoarea: A, B, D,
E, C, F.
Pentru traversarea în preordine a arborelui binar, în clasa
ArboreBinar din fișierul ArboreBinar.java,
prezentată deja mai sus, s-a definit un iterator sub forma clasei
interioare TraversPreordine. Această clasă folosește pentru parcurgerea
în adâncime a arborelui clasa interioară auxiliară ParcurgAdancime.
În metoda hasNext() a acestei clase, se sare peste toate nodurile pentru care numărul de fii parcurși este diferit de 0. În consecință, la fiecare invocare a metodei next() este întors obiectul de informație conținut în următorul nod pentru care fiuParcurs==0. |
În cazul traversării în inordine,
nodul este vizitat după parcurgerea subarborelui stâng (dacă acesta
există), dar înainte de parcurgerea subarborelui drept. În exemplul din figura
2, ordinea de vizitare a nodurilor este următoarea:
D, B, E, A, F, C.
Pentru traversarea arborelui în inordine, în clasa
ArboreBinar din fișierul ArboreBinar.java
s-a definit un iterator sub forma clasei interioare TraversInordine.
Această clasă folosește, pentru parcurgerea în adâncime a arborelui,
clasa interioară auxiliară ParcurgAdancime.
Pentru a se testa dacă elementul curent, întors de iteratorul ParcurgAdancime, îndeplinește condițiile pentru a fi vizitat în inordine, a fost prevăzută metoda boolean vizitInordine(). În metoda hasNext() se sare peste toate elementele parcurse care nu satisfac acest test. În consecință, la fiecare invocare, metoda next() întoarce obiectul de informație al urmatorului nod care poate fi vizitat în inordine. Crearea unui astfel de iterator se face prin metoda Iterator iteratorInordine(). |
În cazul traversării in postordine,
vizitarea se face la ultima trecere prin nodul respectiv, deci după ce
au fost parcurși ambii subarbori (daca ei există). În exempul din figura
2, ordinea de vizitare a nodurilor este următoarea:
D, E, B, F, C, A.
Pentru traversarea arborelui în postordine, în clasa
ArboreBinar din fișierul ArboreBinar.java
a fost definit un iterator sub forma clasei interioare
TraversPostordine. Această clasă folosește, pentru parcurgerea în
adâncime a arborelui, clasa interioară auxiliară ParcurgAdancime.
La fel ca în cazul precedent, pentru a testa dacă un nod parcurs în adâncime îndeplinește condițiile de a fi vizitat în postordine, s-a definit metoda boolean vizitPostordine(). În metoda hasNext() a clasei TraversPostordine se sare peste nodurile care nu îndeplinesc acest test. În consecință, la fiecare invocare a metodei Object next(), este întors obiectul de informație din următorul nod care poate fi vizitat în postordine. |
Metode recursive de traversare a arborilor binari în adâncimePentru realizarea celor trei tehnici de traversare a arborilor descrise mai sus, este foarte comodă implementarea ca metode recursive. în acest caz nu se mai foloseste în mod explicit o stivă ca structură auxiliară, deoarece metodele recursive folosesc implicit stiva sistemului de calcul (în cazul de față cea a mașinii virtuale Java).În cazul implementării
arborelui binar ca structura recursivă, se pot folosi următoarele
metode, în care vizit(Object obj) este metoda de vizitare a
obiectului de informație conținut în rădăcina arborelui sau
subarborelui respectiv:
Implementarea recursivă a traversării este simplă întrucât, în
acest caz, fiecare din cei doi fii este tot un subarbore.
În cazul implementării arborelui binar prin noduri și legaturi traversarea se poate face, de asemenea, prin metode recursive. Un exemplu este dat în clasa ArboreBinar din fișierul ArboreBinar.java, în care s-au introdus metode recursive pentru traversarea arborelui în preordine, inordine și postordine și o metodă recursivă pentru reprezentarea arborelui sub forma de șir, în care fiecare subarbore este cuprins într-o pereche de paranteze. Pentru traversarea în preordine se folosesc urmatoarele două
metode:
Pentru traversarea în inordine, se procedează în mod similar, numai că, în metoda private void inordine(List lista, Nod nod) se traversează mai întâi subarborele din stânga, apoi se pune în listă informația din nodul radăcină și - la sfarsit - se traversează subarborele din dreapta.
În fine, la traversarea în postordine, se traversează mai
întâi cei doi subarbori, după care se pune în listă informația din
nodul rădăcină.
Pentru conversia arborelui într-un șir, s-a adoptat convenția
de reprezentare cu paranteze. În această convenție, de câte ori se
trece către un nivel inferior se deschide o paranteză, iar când se
revine la nivelul superior se închide paranteza respectivă. În
consecință, fiecare subarbore este cuprins într-o pereche de paranteze.
Dacă un nod are un singur fiu, fiul lipsă se reprezinta printr-o
pereche de paranteze vidă (). Pentru reprezentarea arborelui
ca șir, a fost redefinită metoda
Rezultatul aplicării acestor metode se poate urmări la executarea aplicației de testare din fișierul TestArboreBinar.java. |
Pentru a parcurge un arbore în lățime (pe niveluri), se folosește ca
structură auxiliară o coadă. La început se pune în coada rădăcina. Se
consideră că nodul curent este cel din capul cozii. Se pun în coadă
toti fiii nodului curent (dacă ei există), după care acesta se scoate
din coadă. Se continuă astfel până când coada rămâne vidă. Iată cum
evoluează traversarea arborelui în lățime în exemplul din figura 2:
|
|
Conținutul cozii (capul este în stânga) |
|
|
A |
|
|
B, C, D, E |
|
|
C, D, E, F |
|
|
D, E, F |
|
|
E, F |
|
|
F |
|
|
Lungimea cozii este egală cu lățimea arborelui (numărul maxim de
noduri de pe același nivel).
Pentru traversarea arborilor în lățime (pe niveluri), în
clasa Arbore binar din fisierul ArboreBinar.java
s-a definit un iterator sub forma clasei interioare TraversLatime. Ca
structură de date auxiliară, această clasă foloseste o coada,
implementată printr-o instanță a clasei java.util.LinkedList.
Acest iterator poate fi obținut prin metoda Iterator iteratorLatime() a clasei ArboreBinar. În fișierul TestArboreBinar.java este dată aplicația de testare a tuturor tehnicilor de traversare a arborelui binar. |