Pentru exemplificare vom considera arborele din figura 4.
- Figura 4 -
La fel ca in cazul arborilor binari, pentru parcurgerea in adancime
se foloseste ca structura auxiliara o stiva.
In fisierul Arbore.java este definita clasa
Arbore. Pentru parcurgerea in adancime a arborelui s-a definit un iterator,
sub forma clasei interioare ParcurgAdancime, care implementeaza interfata
java.util.Iterator.
Ca stiva se foloseste o instanta a clasei java.util.Stack, iar elementele stivei sunt instante ale clasei interioare private ElemStiva. Reproducem aici cele doua clase.
Pentru obtinerea iteratorului de parcurgere a arborelui in adancime
se foloseste metoda
Efectul parcurgerii arborelui din figura 4 cu acest iterator se poate urmari executand programul de test din fisierul TestArbore.java. |
In clasa Arbore din fisierul Arbore.java,
pentru traversarea arborelui in preordine s-a definit clasa interioara
TraversPreordine, pe care o reproducem aici.
Vizitarea nodului se face numai atunci cand numarul de fii parcursi
este zero. Acest test se face in metoda hasNext(), care sare peste
toate nodurile care nu il satisfac. Obtinerea iteratorului de traversare
in preordine se face invocand metoda
Rezultatul traversarii arborelui din figura 4 folosind iteratorul in preordine se poate urmari executand programul din fisierul TestArbore.java. |
In clasa Arbore din fisierul Arbore.java,
pentru traversarea arborelui in postordine s-a definit un iterator sub
forma clasei interioare TraversPostordine, pe care o reproducem aici.
Se considera ca toti fiii au fost parcursi, atunci cand campul nrFiiParcursi
al elementului din varful stivei este egal cu numarul de elemente din lista
fiilor nodului respectiv. Acest test se face in metoda
Iteratorul pentru traversarea in postordine se obtine invocand metoda
|
In clasa Arbore din fisierul Arbore.java se foloseste parcurgerea recursiva
pentru crearea de liste cu informatiile din noduri si pentru convertirea
arborelui intr-un sir de caractere, in notatia cu paranteze.
Pentru a se obtine o lista, in care informatiile din noduri sunt plasate
in preordine, se folosesc urmatoarele metode:
private static void preordine(List lista, Nod nod) care traverseaza arborele cu radacina nod in preordine si pune in lista informatiile din noduri. La fiecare invocare, aceasta metoda pune in lista informatia din nodul nod, dupa care se invoca pe sine insasi pentru fiecare din fiii nodului respectiv. Pentru obtinerea unei liste cu informatiile din nodurile aarborelui
traversat in postordine, se folosesc urmatoarele metode:
Abordarea recursiva a fost adoptata si in cazul conversiei arborelui
intr-un sir de caractere, in formatul cu paranteze (in care fiecare subarbore
este incadrat intr-o pereche de paranteze). In acest scop, metoda toString
invoca metoda recursiva
|
La fel ca in cazul arborilor binari, la parcurgerea arborelui in latime
se foloseste ca structura auxiliara o coada.
Pentru traversarea arborelui in latime (pe nivele), in clasa Arbore
din fisierul
Arbore.java a fost prevazut un iterator
sub forma clasei interioare TraversLatime. ca structura auxiliara se foloseste
o coada, realizata printr-o instanta a clasei java.util.LinkedList.
Pentru obtinerea acestui iterator este invocata metoda
Rezultatul traversarii in latime a arborelui din figura 4 cu aceast iterator se poate urmari executand programul din fisierul TestArbore.java. Iteratorul pentru traversare in latime a fost folosit si in metoda de
creare a unei liste, in care informatiile din noduri sunt plasate pe nivele:
|