Traversarea arborilor generali

Tehnicile de traversare a arborilor generali sunt: în preordine, în postordine și în lățime. Aceste tehnici sunt similare celor cu același nume de la arborii binari. Traversarea în inordine, evident, nu are sens în cazul arborilor generali.

Pentru exemplificare, vom considera arborele din figura 4.


- Figura 4 -

Parcurgerea în adâncime a arborilor generali

Traversarea arborilor în preordine sau în postordine implică parcurgerea în adâncime a arborilor respectivi. Aceasta se realizează, ca și în cazul arborilor binari, prin trasare și revenire (backtracking). După ce s-a ajuns la un anumit nod, se parcurg pe rând toți subarborii lui, după care se revine la nodul tată. Cu fiecare subarbore se procedează la fel. De exemplu, în cazul arborelui din figura 4, nodurile sunt parcurse în 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
În acest șir, deplasările în jos (trasările) sunt marcate cu roșu, iar cele în sus (revenirile) sunt marcate cu albastru.

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.
 
  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 obținerea iteratorului de parcurgere a arborelui în adâncime se folosește metoda 
    Iterator iteratorAdancime()
definită în clasa Arbore. În mod normal, această metodă trebuie să fie privată sau protejată, deoarece iteratorul este folosit numai în alte clase interioare ale clasei Arbore. Aici a fost declarata publică pentru a putea fi testată.

Efectul parcurgerii arborelui din figura 4 cu acest iterator se poate urmări, executând programul de test din fișierul TestArbore.java

Traversarea arborelui general cu parcurgere în adâncime

Parcurgerea în adâncime a arborilor generali permite traversarea acestora în preordine sau în postordine.

Traversarea arborelui în preordine

La traversarea arborelui în preordine, fiecare nod este vizitat inaintea fiilor săi. Astfel, în cazul arborelui din figura 4, la traversarea în preordine nodurile sunt vizitate în ordinea următoare:
A, B, E, F, J, C, D, G, H, K, L, I.
 
În clasa Arbore din fișierul Arbore.java, pentru traversarea arborelui în preordine s-a definit clasa interioară 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 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
    Iterator iteratorAdancime()
definită în clasa Arbore.

Rezultatul traversării arborelui din figura 4, folosind iteratorul în preordine, se poate urmări executând programul din fișierul TestArbore.java.

Traversarea arborelui în postordine

La traversarea în postordine a arborelui general, fiecare nod este vizitat după ce au fost parcurși toți fiii săi. În exemplul din figura 4, traversarea în postordine se face vizitând nodurile în următoarea ordine:
E, J, F, B, C, G, K, L, H, I, D, A.
 
Î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. 
 
  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 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
    boolean testPostordine()
care este invocată de metoda hasNext(). Metoda hasNext() sare peste toate nodurile din stivă care nu satisfac acest test, oprindu-se pe primul care îl satisface.

Iteratorul pentru traversarea în postordine se obține invocând metoda 
    Iterator iteratorPostordine()
definită în clasa Arbore. Efectul traversării arborelui din figura 4 cu acest iterator poate fi urmărit, executând programul de test din fișierul TestArbore.java.

Metode recursive de traversare a arborilor generali în adâncime

Pentru traversarea arborelui general în adâncime, pot fi folosite și metode recursive. Acestea se bazează pe faptul că orice nod al unui arbore este, de asemenea, rădăcina unui subarbore. Însăși frunza poate fi considerată un arbore format dintr-un singur nod. În consecință, traversarea arborelui în preordine se poate face în urmatoarele etape:
    - se vizitează radăcina;
    - se traversează toți subarborii-fii.
La traversarea în postordine, cele două operații se inversează:
    - se traversează toți subarborii-fii;
    - se viziteaza rădăcina.
 
Î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:
 
  /* 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 listă vidă, după care invocă metoda recursivă
  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:
 
  /* 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;
  }

Situația este similară celei de la traversarea în preordine, cu deosebirea că, în acest caz, se parcurg mai întâi toți fiii și abia după aceea se pune în listă informația din nodul nod.

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ă 
 StringBuffer cuParanteze(StringBuffer sb, Nod nod)
care adaugă la StringBuffer-ul sb, primit ca argument, șirul de caractere corespunzător subarborelui cu rădăcina nod. Cele două 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 în lățime (pe niveluri)

La traversarea arborilor în lățime, se parcurg succesiv, de la stânga la dreapta, nodurile de pe fiecare nivel. Astfel, în exemplul din figura 4, nodurile sunt vizitate în următoarea ordine:
A, B, C, D, E, F, G, H, I, J, K, L.

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.
 
  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 obținerea acestui iterator este invocată metoda 
     Iterator iteratorLatime()
definită în clasa Arbore.

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:
 
  public List inLatime() {
    List lista=new ArrayList();
    Iterator iter=iteratorLatime();
    while(iter.hasNext()) 
      lista.add(iter.next());
    return lista;
  }
Această metodă este, de asemenea, testată în aplicația din fișierul TestArbore.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați