Pentru exemplificare, vom considera arborele din figura 4.
- Figura 4 -
La fel ca în cazul arborilor binari, pentru parcurgerea în adâncime
a arborelui general se folosește ca structură auxiliară o stivă.
In fișierul Arbore.java este
definită clasa Arbore. Pentru parcurgerea în adâncime a arborelui s-a
definit un iterator, sub forma clasei interioare ParcurgAdancime, care
implementează interfața java.util.Iterator. Ca stivă se folosește o instanță a clasei java.util.Stack, iar elementele stivei sunt instanțe ale clasei interioare private ElemStiva. Reproducem aici cele două clase.
Pentru obținerea iteratorului de parcurgere a arborelui în
adâncime se folosește metoda Efectul parcurgerii arborelui din figura 4 cu acest iterator se poate urmări, executând programul de test din fișierul TestArbore.java. |
În clasa Arbore din fișierul Arbore.java,
pentru traversarea arborelui în preordine s-a definit clasa interioară
TraversPreordine, pe care o reproducem aici.
Vizitarea nodului se face numai atunci când numărul de fii
parcurși este zero. Acest test se face în metoda hasNext(),
care sare peste toate nodurile care nu il satisfac. Obținerea
iteratorului de traversare în preordine se face invocând metoda Rezultatul traversării arborelui din figura 4, folosind iteratorul în preordine, se poate urmări executând programul din fișierul TestArbore.java. |
În clasa Arbore din fișierul Arbore.java,
pentru traversarea arborelui în postordine s-a definit un iterator sub
forma clasei interioare TraversPostordine, pe care o reproducem aici.
Se consideră că toți fiii au fost parcurși, atunci când câmpul
nrFiiParcursi al elementului din varful stivei este egal cu numărul de
elemente din lista fiilor nodului respectiv. Acest test se face în
metoda Iteratorul pentru traversarea în postordine se obține invocând
metoda |
În clasa Arbore din fișierul Arbore.java, se folosește
parcurgerea recursivă pentru crearea de liste cu informațiile din
noduri și pentru convertirea arborelui într-un șir de caractere, în
notația cu paranteze.
Pentru a se obține o listă, în care informațiile din noduri
sunt plasate în preordine, se folosesc următoarele metode:
private static void preordine(List lista, Nod nod) care traversează arborele cu radăcina nod în preordine și pune în listă informațiile din noduri. La fiecare invocare, această metodă pune în listă informația din nodul nod, după care se invocă pe sine însăși pentru fiecare din fiii nodului respectiv. Pentru obținerea unei liste cu informațiile din nodurile
arborelui traversat în postordine, se folosesc următoarele metode:
Abordarea recursivă a fost adoptată și în cazul conversiei
arborelui într-un șir de caractere, în formatul cu paranteze (în care
fiecare subarbore este încadrat într-o pereche de paranteze). În acest
scop, metoda toString invocă metoda recursivă
|
La fel ca în cazul arborilor binari, la parcurgerea arborelui
general în lățime se folosește ca structură auxiliară o coadă.
Pentru traversarea arborelui în lățime (pe niveluri), în
clasa Arbore din fisierul Arbore.java a fost
prevăzut un iterator sub forma clasei interioare TraversLatime. Ca
structură auxiliară se folosește o coadă, realizată printr-o instanța a
clasei java.util.LinkedList.
Pentru obținerea acestui iterator este invocată metoda Rezultatul traversării în lățime a arborelui din figura 4 cu aceast iterator se poate urmări executând programul din fișierul TestArbore.java. Iteratorul pentru traversare în lățime a fost folosit și în
metoda de creare a unei liste, în care informațiile din noduri sunt
plasate pe niveluri:
|