Traversarea arborilor binari

Traversarea arborelui este parcurgerea tuturor nodurilor într-o anumită ordine, însoțită de vizitarea acestora.
Vizitarea nodului înseamnă utilizarea și, eventual, actualizarea informației aferente nodului respectiv.

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.

Parcurgerea în adâncime

La parcurgerea arborelui în adâncime (engleză: depth-first) se aplică o tehnică cunoscută și sub numele de trasare cu revenire (engleză: backtracking), care este ilustrată în figura 2.


- 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:
 
Pasul
Nodul curent
Continutul stivei (vârful este în dreapta)
0
A
  A
1
B
  A, B
2
D
  A, B, D
3
B
  A, B
4
E
  A, B, E
5
B
  A, B
6
A
  A
7
C
  A, C
8
F
  A, C, F
9
C
  A, C
10
A
  A
11
null (sfârșitul parcurgerii)
 

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:
 
  private class ElemStiva {
    int fiuVizitat;
    Nod nod;

    ElemStiva(Nod nodCurent, int fiuVizitat) {
      this.fiuVizitat=fiuVizitat;
      nod=nodCurent;
    }

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

  public class ParcurgAdancime implements Iterator {
    Stack stiva;
    ParcurgAdancime() {
      stiva=new Stack();
      if(radacina!=null) stiva.push(new ElemStiva(radacina, 0));
    }

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

    public Object next() {
      if(stiva.empty()) return null;
      ElemStiva varfStiva=(ElemStiva)stiva.peek();
      Nod nodCurent=varfStiva.nod;
      int fiuVizitat=varfStiva.fiuVizitat;
      if(fiuVizitat==0) {
        if(nodCurent.fiuStanga!=null) {
          stiva.push(new ElemStiva(nodCurent.fiuStanga, 0));
          varfStiva.fiuVizitat=1;
        }
        else if(nodCurent.fiuDreapta!=null) {
          stiva.push(new ElemStiva(nodCurent.fiuDreapta, 0));
          varfStiva.fiuVizitat=2;
        }
        else stiva.pop();
      }
      else if(fiuVizitat==1) {
        if(nodCurent.fiuDreapta!=null) {
          stiva.push(new ElemStiva(nodCurent.fiuDreapta, 0));
          varfStiva.fiuVizitat=2;
        }
        else stiva.pop();
      } else stiva.pop();
      return new ElemStiva(nodCurent, fiuVizitat);
    }

    public void remove() {}
 

  }
 

Pentru a se creea un iterator de parcurgere a arborelui în adancime, în clasa ArboreBinar a fost definită metoda
  public Iterator iteratorAdancime() {
    return new ParcurgAdancime();
  }
care întoarce un iterator al arborelui binar. La fiecare invocare a metodei Object next() a acestui iterator, este intoarsă o instanță a clasei ElemStiva, care conține o referință la nodul curent și codul ultimului fiu parcurs. Este posibilă astfel folosirea acestui iterator pentru a creea metode de traversare a arborelui.

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

Traversarea arborelui binar cu parcurgere în adâncime

Traversarea combină parcurgerea cu vizitarea nodurilor. S-a arătat că, la parcurgerea în adâncime, se trece de mai multe ori prin același nod. Vizitarea nodului trebuie sa se facă, însa, o singură dată. Se pune problema la care din trecerile printr-un nod se face vizitarea lui. În cazul arborilor binari exista, trei posibilități numite, respectiv, traversarea în preordine, inordine și postordine.

Î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.
 
  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()).fiuVizitat>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() {}
  }

Î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.
 
  public class TraversInordine implements Iterator {
    ParcurgAdancime parcurg;

    public TraversInordine() {
      parcurg=(ParcurgAdancime)iteratorAdancime();
    }

    /* Se testeaza daca elementul curent (din varful stivei) poate fi vizitat in inordine
    */ 
    private boolean vizitInordine() {
      if(parcurg.stiva.empty()) return false;
      ElemStiva curent=(ElemStiva)parcurg.stiva.peek();
      //if(curent==null) return false;
      if(curent.fiuVizitat==1) return true;
      if(curent.fiuVizitat==0 && curent.nod.fiuStanga==null)
                                              return true;
      return false;
    }

    public boolean hasNext() {
      if(!parcurg.hasNext()) return false;
      while(parcurg.hasNext() && !vizitInordine()) 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() {}
  }

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.
 
  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==null) return false;
      if(curent.fiuVizitat==2) return true;
      if(curent.nod.fiuDreapta==null && (curent.fiuVizitat==1 ||
        curent.fiuVizitat==0 && curent.nod.fiuStanga==null))
                                              return true;
      return false;
    }

    public boolean hasNext() {
      if(!parcurg.hasNext()) return false;
      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() {}
  }

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âncime

Pentru 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:
 
  public void preordine() {
    vizit(info);
    if(subarboreStanga!=null)
        subarboreStanga.preordine();
    if(subarboreDreapta!=null)
        subarboreDreapta.preordine();
  }

  public void inordine() {
    if(subarboreStanga!=null)
        subarboreStanga.inordine();
    vizit(info);
    if(subarboreDreapta!=null)
        subarboreDreapta.inordine();
  }

  public void postordine() {
    if(subarboreStanga!=null)
        subarboreStanga.postOrdine();
    if(subarboreDreapta!=null)
        subarboreDreapta.postOrdine();
    vizit(info);
  }

Implementarea recursivă a traversării este simplă întrucât, în acest caz, fiecare din cei doi fii este tot un subarbore.
 
Exemplu: În fișierul ArboreBinRec.java este dat un exemplu de clasă de arbori binari recursivi, în care cele trei tehnici de traversare sunt implementate sub forma de metode recursive. În fișierul TestArboreBinRec.java este dat un exemplu de testare a clasei ArboreBinRec pentru arborele din figura 3.


- Figura 3 -

Construirea arborelui s-a făcut de la frunze către rădăcină, folosind constructorii pentru fiecare subarbore. Metodele preordine, inordine si postordine au fost puțin modificate, astfel încât fiecare din ele întoarce o listă, în care nodurile sunt puse în ordinea vizitării. "Vizitarea" nodului constă, în acest caz, din simpla punere a lui în listă.

Î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: 
 
  /* Traversare in preordine */
  private void preordine(List lista, Nod nod) {
    lista.add(nod.info);
    if(nod.fiuStanga!=null) preordine(lista, nod.fiuStanga);
    if(nod.fiuDreapta!=null) preordine(lista, nod.fiuDreapta);
  }

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

Metoda List preordine() întoarce o listă, care conține obiectele de informație din nodurile arborelui, traversate în preordine. În această metodă se creează lista vidă, iar punerea elementelor în listă se face de către metoda recursivă private void preordine(List lista, Nod nod). Se remarcă cu ușurință cât de simplă și clară este această metodă: se vizitează nodul nod și se pune în listă informația din acesta, după care se traversează pe rând, prin aceeași metodă, subarborele din stânga și cel din dreapta.

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.
  /* Traversare in inordine */
  private void inordine(List lista, Nod nod) {
    if(nod.fiuStanga!=null) inordine(lista, nod.fiuStanga);
    lista.add(nod.info);
    if(nod.fiuDreapta!=null) inordine(lista, nod.fiuDreapta);
  }

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

Î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ă.
 
  /* Traversare in postordine */
  private void postordine(List lista, Nod nod) {
    if(nod.fiuStanga!=null) postordine(lista, nod.fiuStanga);
    if(nod.fiuDreapta!=null) postordine(lista, nod.fiuDreapta);
    lista.add(nod.info);
  }

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

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 
    public String toString()
din clasa Object. Aceasta creeaza un StringBuffer vid sb, după care invocă metoda privată recursivă
    private static StringBuffer cu paranteze(StringBuffer sb, Nod nod)
care pune în sb subarborele cu rădăcină nod, convertit în șir.
  /* 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.info);
    if(nod.fiuStanga!=null) cuParanteze(sb, nod.fiuStanga);
    else if(nod.fiuDreapta!=null) sb.append("(()");
    if(nod.fiuDreapta!=null) cuParanteze(sb, nod.fiuDreapta);
    else if(nod.fiuStanga!=null) sb.append("()");
    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();
  }

Rezultatul aplicării acestor metode se poate urmări la executarea aplicației de testare din fișierul TestArboreBinar.java.

Traversarea arborilor in lățime (pe niveluri)

La traversarea în lățime (engleză: breadth-first), numită și traversare pe niveluri, nodurile arborelui se parcurg și se vizitează astfel: se începe cu rădăcina, apoi se vizitează de la stânga la dreapta toate nodurile de nivel 1, apoi toate nodurile de nivel 2 și așa mai departe. Prin fiecare nod se trece o singură dată. În cazul arborelui din figura 2, ordinea de vizitare a nodurilor este următoarea: A, B, C, D, E, F.

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:
 
Pasul
Nodul curent
  Conținutul cozii (capul este în stânga)
0
A
  A
1
B
  B, C, D, E
2
C
  C, D, E, F
3
D
  D, E, F
4
E
  E, F
5
F
  F
6
null (sfârșitul parcurgerii)
 

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.
 
  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 */
      if(nodCurent.fiuStanga!=null) 
            coada.addLast(nodCurent.fiuStanga);
      if(nodCurent.fiuDreapta!=null) 
            coada.addLast(nodCurent.fiuDreapta);
      /* Se intoarce informatia din nodul curent */
      return nodCurent.info;
    }

    public void remove() {}

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

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.



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