Traversarea arborilor generali

Tehnicile de traversare a arborilor generali sunt: in preordine, in postordine si in latime. Aceste tehnici sunt similare celor cu acelasi nume de la arborii binari. Traversarea in inordine, evident, nu are sens in cazul arborilor generali.

Pentru exemplificare vom considera arborele din figura 4.


- Figura 4 -

Parcurgerea in adancime a arborilor generali

Traversarea arborilor in preordine sau in postordine implica parcurgerea in adancime a arborilor respectivi. Aceasta se realizeaza, ca si in cazul arborilor binari, prin trasare si revenire (backtracking). Dupa ce sa ajuns la un anumit nod, se parcurg pe rand toti fiii lui, dupa care se revine la nodul tata. Cu fiecare fiu se procedeaza la fel. De exemplu, in cazul arborelui din figura 4, nodurile sunt parcurse in urmatoarea ordine:
A->B->E->B->F->J->F->B->A->C->A->D->G->D->H->K->H->L->H->D->I->D->A
In acest sir deplasarile in jos (trasarile) sunt marcate cu rosu, iar cele in sus (revenirile) sunt marcate cu albastru.

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.
 
  private class ElemStiva {
    Nod nod;
    Iterator iteratorFii;
    int nrFiiParcursi; 

    ElemStiva(Nod nod) {
      this.nod=nod;
      iteratorFii=nod.fii.iterator();
      nrFiiParcursi=0;
    } 

    ElemStiva(ElemStiva elem) {
      nod=elem.nod;
      iteratorFii=elem.iteratorFii;
      nrFiiParcursi=elem.nrFiiParcursi;
    }

    public String toString() {
      return "<"+nrFiiParcursi+" "+nod+">"; 
    }
  }
 

  public class ParcurgAdancime implements Iterator {
    Stack stiva;

    ParcurgAdancime() {
      stiva=new Stack();
      if(radacina!=null) stiva.push(new ElemStiva(radacina));
    }

    public boolean hasNext() {
      if(stiva.empty()) return false;
      return true;
    }

    public Object next() {
      if(stiva.empty()) return null;
      ElemStiva elemCurent=(ElemStiva)stiva.peek();
      ElemStiva deIntors=new ElemStiva(elemCurent);
      if(elemCurent.iteratorFii.hasNext()) {
        elemCurent.nrFiiParcursi++;
        stiva.push(new ElemStiva((Nod)elemCurent.iteratorFii.next()));
      } else stiva.pop();
      return deIntors;
    }

    public void remove() {}

  }

Pentru obtinerea iteratorului de parcurgere  a arborelui in adancime se foloseste metoda 
    Iterator iteratorAdancime()
definita in clasa Arbore. In mod normal, aceasta metoda trebuie sa fie privata sau protejata, deoarece iteratorul este folosit numai in alte clase interioare ale clasei Arbore. Aici a fost declarata publica pentru a putea fi testata.

Efectul parcurgerii arborelui din figura 4 cu acest iterator se poate urmari executand programul de test din fisierul TestArbore.java

Traversarea arborelui general cu parcurgere in adancime

Parcurgerea in adancime a arborilor generali permite traversarea acestora in preordine sau in postordine.

Traversarea arborelui in preordine

La traversarea arborelui in preordine, fiecare nod este vizitat inaintea fiilor sai. Astfel, in cazul arborelui din figura 4, la traversarea in preordine nodurile sunt vizitate in ordinea urmatoare:
A, B, E, F, J, C, D, G, H, K, L, I.
 
In clasa Arbore din fisierul Arbore.java, pentru traversarea arborelui in preordine s-a definit clasa interioara TraversPreordine, pe care o reproducem aici.
 
  public class TraversPreordine implements Iterator {
    ParcurgAdancime parcurg;
 
    public TraversPreordine() {
      parcurg=(ParcurgAdancime)iteratorAdancime();
    }
           
    public boolean hasNext() {
      while(parcurg.hasNext() && !parcurg.stiva.empty() && 
                ((ElemStiva)parcurg.stiva.peek()).nrFiiParcursi!=0)
        parcurg.next();
      return parcurg.hasNext();
    }

    public Object next() {
      if(parcurg.hasNext()) {
        ElemStiva urmator=(ElemStiva)parcurg.next();
        return urmator.nod.info;
      }
      return null;
    }

    public void remove() {}
  }

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
    Iterator iteratorAdancime()
definita in clasa Arbore.

Rezultatul traversarii arborelui din figura 4 folosind iteratorul in preordine se poate urmari executand programul din fisierul TestArbore.java.

Traversarea arborelui in postordine

La traversarea in postordine a arborelui general fiecare nod este vizitat dupa ce au fost parcursi toti fiii sai. In exemplul din figura 4, traversarea in postordine se face vizitand nodurile in urmatoarea ordine:
E, J, F, B, C, G, K, L, H, I, D, A.
 
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. 
 
  public class TraversPostordine implements Iterator {
    ParcurgAdancime parcurg;
 
    public TraversPostordine() {
      parcurg=(ParcurgAdancime)iteratorAdancime();
    }

    /* Se testeaza daca elementul curent (din varful stivei) poate fi
       vizitat in postordine
    */ 
    private boolean vizitPostordine() {
      if(parcurg.stiva.empty()) return false;
      ElemStiva curent=(ElemStiva)parcurg.stiva.peek();
      if(curent.nrFiiParcursi==curent.nod.fii.size())
        return true;
      return false;
    }
 
    public boolean hasNext() {
      while(parcurg.hasNext() && !vizitPostordine()) parcurg.next();
      return parcurg.hasNext();
    }

    public Object next() {
      if(parcurg.hasNext()) {
        ElemStiva urmator=(ElemStiva)parcurg.next();
        return urmator.nod.info;
      }
      return null;
    }

    public void remove() {}
  }

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
    boolean testPostordine()
care este invocata de metoda hasNext(). Metoda hasNext() sare peste toate nodurile din stiva care nu satisfac acest test, oprindu-se pe primul care il satisface.

Iteratorul pentru traversarea in postordine se obtine invocand metoda 
    Iterator iteratorPostordine()
definita in clasa Arbore. Efectul traversarii arborelui din figura 4 cu acest iterator poate fi urmarit executand programul de test din fisierul TestArbore.java.

Metode recursive de traversare a arborilor generali in adancime

Pentru traversarea arborilor general in adancime pot fi folosite si metode recursive. Acestea se bazeaza pe faptul ca orice nod al unui arbore este, de asemenea, un arbore. Insasi frunza poate fi considerata un arbore format dintr-un singur nod. In consecinta, vizitarea arborelui in preordine se poate face in urmatoarele etape:
    - se viziteaza radacina;
    - se viziteaza toti subarborii-fii.
La parcurgerea in postordine, cele doua operatii se inverseaza:
    - se viziteaza toti subarborii-fii;
    - se viziteaza radacina.
 
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:
 
  /* Traversarea in preordine */
  private static void preordine(List lista, Nod nod) {
    lista.add(nod.info);
    Iterator iter=nod.fii.iterator();
    while(iter.hasNext())
      preordine(lista, (Nod)iter.next());
  }

  public List preordine() {
    List lista=new ArrayList();
    preordine(lista, radacina);
    return lista;
  }

Metoda public List preordine() creeaza o lista vida, dupa care invoca metoda recursiva
  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:
 
  /* Traversarea in postordine */
  private static void postordine(List lista, Nod nod) {
    Iterator iter=nod.fii.iterator();
    while(iter.hasNext())
      postordine(lista, (Nod)iter.next());
    lista.add(nod.info);
  }

  public List postordine() {
    List lista=new ArrayList();
    postordine(lista, radacina);
    return lista;
  }

Situatia este similara celei de la traversarea in preordine, cu deosebirea ca, in acest caz, se parcurg mai intai toti fiii si abia dupa aceea se pune in lista informatia din nodul nod.

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 
 StringBuffer cuParanteze(StringBuffer sb, Nod nod)
care adauga la StringBuffer-ul sb primit ca argument sirul de caractere corespunzator subarborelui cu radacina nod. Cele doua metode sunt reproduse mai jos.
 
  /* Metoda auxiliara recursiva care converteste un subarbore intr-un
     sir, in care arborele este pus in formatul cu paranteze
  */
  private static StringBuffer cuParanteze(StringBuffer sb, Nod nod) {
    sb.append("("+nod);
    Iterator iter=nod.fii.iterator();
    while(iter.hasNext()) cuParanteze(sb, (Nod)iter.next());
    sb.append(")");
    return sb;
  }

  /* Redefinirea metodei toString din clasa Object. Foloseste metoda
     auxiliara cuParanteze() aplicata radacinii arborelui
  */
  public String toString() {
    StringBuffer sb=new StringBuffer();
    if(radacina==null) return "( )";
    return cuParanteze(sb, radacina).toString();
  }

Traversarea arborelui general in latime (pe nivele)

La traversarea arborilor in latime, se parcurg succesiv, de la stanga la dreapta, nodurile de pe fiecare nivel. Astfel, in exemplul din figura 4, nodurile sunt vizitate in urmatoarea ordine:
A, B, C, D, E, F, G, H, I, J, K, L.

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.
 
  public class TraversLatime implements Iterator {
    LinkedList coada;

    public TraversLatime() {
      coada=new LinkedList();
      if(radacina!=null) coada.addLast(radacina);
    }

    public boolean hasNext() {
      if(coada.size()==0) return false;
      return true;
    }

    public Object next() {
      /* Se extrage din coada nodul curent */
      Nod nodCurent=(Nod)coada.removeFirst();
      /* Se pun in coada fiii nodului curent */
      Iterator iter=nodCurent.fii.iterator();
      while(iter.hasNext()) coada.addLast(iter.next());
      /* Se intoarce informatia din nodul curent */
      return nodCurent.info;
    }

    public void remove() {}

    public Nod nodCurent() {
      return (Nod)coada.getFirst();
    }
  }

Pentru obtinerea acestui iterator este invocata metoda 
     Iterator iteratorLatime()
definita in clasa Arbore.

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:
 
  public List inLatime() {
    List lista=new ArrayList();
    Iterator iter=iteratorLatime();
    while(iter.hasNext()) 
      lista.add(iter.next());
    return lista;
  }
Aceasta metoda este, de asemenea, testata in aplicatia din fisierul TestArbore.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati