Traversarea arborilor binari

Traversarea arborelui este parcurgerea nodurilor intr-o anumita ordine, insotita de vizitarea acestora.
Vizitarea nodului inseamna utilizarea si, eventual, actualizarea informatiei aferente nodului respectiv.

Parcurgerea nodurilor este o tehnica de trecere sistematica de la un nod la altul,astfel incat sa se treaca prin toate nodurile arborelui intr-o ordine prestabilita. Este posibil sa se treaca de mai multe ori prin fiecare nod, dar vizitarea se face numai o data. Exista doua tehnici de parcurgere a arborilor: in adancime si in latime (pe niveluri).

Pentru a aplica tehnici iterative de vizitare a nodurilor unui arbore, in tehnologia Java se folosesc iteratori. Acestia sunt definiti, la fel ca in cazul colectiilor sau maparilor, prin clase care implementeaza interfata java.util.Iterator. La fiecare invocare a metodei Object next() a unui iterator, acesta intoarce obiectul de informatie continut in urmatorul nod care trebuie vizitat. Aceasta abordare creeaza o mare flexibilitate in utilizarea iteratiei, intrucat utilizatorul clasei de arbori este scutit de implementarea tehnicii de parcurgere a nodurilor in vederea vizitarii lor, concentrandu-si atentia numai asupra prelucrarii informatiei din noduri.

Parcurgerea in adancime

La parcurgerea arborelui in adancime (engleza: depth-first) se aplica o tehnica cunoscuta si sub numele de trasare cu revenire (engleza: backtracking), care este ilustrata in figura 2.


- Figura 2 -

Parcurgerea nodurilor incepe intotdeauna de la radacuina arborelui. Se parcurge apoi intregul subarbore din stanga, urmat de intregul subarbore din dreapta (daca acestia exista). Parcurgerea fiecarui subarbore se face in acelasi mod. Se observa, deci ca aceasta este o tehnica de parcurgere recursiva, bazata pe recursivitatea structurii de arbore.  In figura 2 ordinea de parcurgere a nodurilor este urmatoarea: A, B, D, B -> E -> B -> A -> C -> F -> C -> A. Sagetile rosii reprezinta parcurgerea descendenta (trasarea) iar cele albastre parcurgerea ascendenta (revenirea). Parcurgerea intregului arbore se incheie in momentul in care s-a trecut prin toate nodurile si s-a revenit in radacina.

Pentru parcurgerea in adancime a arborelui, este necesar sa se memoreze calea pe care s-a ajuns de la radacina la nodul curent, pentru a se asigura revenirea la nodurile deja parcurse. La inceputul parcurgerii, in stiva se pune radacina. De cate ori se trece de la un nod la unul din fiii lui, fiul respectiv este pus in stiva. Dupa ce au fost vizitati fiii, se revine la tatal nodului curent, care este extras din stiva. Nodul curent se afla intotdeauna in varful stivei. Parcurgerea se incheie cand stiva este goala. Iata etapele parcurgerii in exemplul din figura 2:
 
Pasul
Nodul curent
Continutul stivei (varful este in 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 (sfarsitul parcurgerii)
 

Se observa ca inaltimea maxima a stivei este egala cu inaltimea arborelui. Datorita folosirii stivei, nu este necesar ca, pentru a putea parcurge arborele, in fiecare nod sa existe si o legatura catre tata.
 
In fisierul ArboreBinar.java este definita clasa ArboreBinar. Pentru parcurgerea in adancime a arborelui a fost definit un iterator sub forma clasei interioare ParcurgAdancime. Aceasta clasa foloseste ca structura auxiliara o stiva realizata printr-o instanta a clasei java.util.Stack. Ca elemente ale stivei se folosesc instante ale clasei interioare ElemStiva, care contin doua campuri: 
    int FiuParcurs; 
    Nod nodCurent;
Primul camp contine un cod care indica ultimul fiu parcurs si care poate fi:
    0 - pentru prima intrare in nod (nu s-a parcurs nici un fiu);
    1 - a fost parcurs fiul stanga;
    2 - a fost parcurs fiul dreapta.
In acest mod, la scoaterea nodului din stiva se poate sti si modul in care s-a ajuns la nodul respectiv in timpul parcurgerii stivei. Nodul este instanta a clasei interioare Nod.

Dam aici definirea claselor ElemStiva si 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 in adancime, in clasa ArboreBinar a fost definita metoda
  public Iterator iteratorAdancime() {
    return new ParcurgAdancime();
  }
care intoarce un iterator al arborelui binar. La fiecare invocare a metodei Object next() a acestui iterator, este intoarsa o instanta a clasei ElemStiva, care contine o referinta la nodul curent si codul ultimului fiu parcurs. Este posibila astfel folosirea acestui iterator pentru a creea metode de traversare a arborelui.

Mentionam ca clasa interioara ParcurgAdancime si metoda iteratorAdancime au fost declarate publice numai pentru a se putea face testarea lor. Daca clasa ArboreBinar este inclusa intr-o biblioteca, este recomandabil sa li se schimbe modul de acces in publuic sau eventual protected, deoarece au doar un rol auxiliar in realizarea tehnicilor de traversare a arborelui descrise in cele ce urmeaza.

Un exemplu de aplicatie in care este testata parcurgerea in adancime a unui ArboreBinar este dat in fisierul TestArboreBinar.java

Traversarea arborelui binar cu parcurgere in adancime

Traversarea combina parcurgerea cu vizitarea nodurilor. S-a aratat ca la parcurgerea in adancime se trece de mai multe ori prin acelasi nod. Vizitarea nodului trebuie sa se faca, insa, o singura data. Se pune problema la care din trecerile printr-un nod se face vizitarea lui. In cazul arborilor binari exista trei posibilitati, numite, respectiv, traversarea in preordine, inordine si postordine.

In cazul traversarii in preordine, vizitarea unui nod se face la prima trecere prin acesta, deci inainte de a fi parcursi cei doi subarbori. In exemplul din figura 2, ordinea de vizitare a nodurilor este urmatoarea: A, B, D, E, C, F.
 
Pentru traversarea in preordine a arborelui binar, in clasa ArboreBinar din fisierul ArboreBinar.java, prezentata deja mai sus, s-a definit un iterator sub forma clasei interioare TraversPreordine. Aceasta clasa foloseste pentru parcurgerea in adancime clasa interioara auxiliara 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() {}
  }

In metoda hasNext() a acestei clase se sare peste toate nodurile pentru care numarul de fii parcursi este diferit de 0. In consecinta, la fiecare invocare a metodei next() este intors obiectul de informatie continut in urmatorul nod pentru care fiuParcurs==0.

In cazul traversarii in inordine, nodul este vizitat dupa parcurgerea subarborelui stang (daca exista), dar inainte de parcurgerea subarborelui drept. In exemplul din figura 2, ordinea de vizitare a nodurilor este urmatoarea: D, B, E, A, F, C.
 
 
Pentru traversarea arborelui in inordine, in clasa ArboreBinar din fisierul ArboreBinar.java s-a definit un iterator sub forma clasei interioare TraversInordine. Aceasta clasa foloseste, pentru parcurgerea in adancime a arborelui, clasa interioara auxiliara 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 daca elementul curent, intors de iteratorul ParcurgAdancime, indeplineste conditiile pentru a fi vizitat in inordine, a fost prevazuta metoda boolean vizitInordine(). In metoda hasNext() se sare peste toate elementele parcurse care nu satisfac acest test. In consecinta, la fiecare invocare, metoda next() intoarce obiectul de informatie al urmatorului nod care poate fi vizitat in inordine. Crearea unui astfel de iterator se face prin metoda Iterator iteratorInordine().

In cazul traversarii in postordine, vizitarea se face la ultima trecere prin nodul respectiv, deci dupa ce au fost parcursi ambii subarbori (daca ei exista). In exempul din figura 2, ordinea de vizitare a nodurilor este urmatoarea: D, E, B, F, C, A.
 
Pentru traversarea arborelui in postordine, in clasa ArboreBinar din fisierul ArboreBinar.java a fost definit un iterator sub forma clasei interioare TraversPostordine. Aceasta clasa foloseste, pentru parcurgerea in adancime a arborelui,  clasa interioara auxiliara 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 in cazul precedent, pentru a testa daca un nod parcurs in adancime indeplineste conditiile de a fi vizitat in postordine, s-a definit metoda boolean vizitPostordine(). In metoda hasNext() a clasei TraversPostordine se sare peste nodurile care nu indeplinesc acest test. In consecinta, la fiecare invocare a metodei Object next(), este intors obiectul de informatie din urmatorul nod care poate fi vizitat in postordine.


 

Metode recursive de traversare a arborilor binari in adancime

Pentru realizarea celor trei tehnici de traversare a arborilor descrise mai sus, este foarte comoda implementarea ca metode recursive. In acest caz nu se mai foloseste in mod explicit o stiva ca structura auxiliara, deoarece metodele recursive folosesc implicit stiva sistemului de calcul (in cazul de fata cea a masinii virtuale Java).

In cazul implementarii arborelui binar ca structura recursiva, se pot folosi urmatoarele metode, in care vizit(Object obj) este metoda de vizitare a obiectului de informatie continut in radacina 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 recursiva a traversarii este simpla intrucat, in acest caz, fiecare din cei doi fii este tot un subarbore.
 
Exemplu: In fisierul ArboreBinRec.java este dat un exemplu de clasa de arbori binari recursivi in care sunt implementate cele trei tehnici de traversare sub forma de metode recursive. In fisierul TestArboreBinRec.java este dat un exemplu de testare a clasei ArboreBinRec pentru arborele din figura 3.


- Figura 3 -

Construirea arborelui s-a facut de la frunze catre radacina, folosind constructorii pentru fiecare subarbore. Metodele preordine, inordine si postordine au fost putin modificate, astfel incat fiecare din ele intoarce o lista, in care nodurile sunt puse in ordinea vizitarii. "Vizitarea" nodului consta, in acest caz, din simpla punere a lui in lista.

In cazul implementarii arborelui binar prin noduri si legaturi traversarea se poate face, de asemenea prin metode recursive. Un exemplu este dat in clasa ArboreBinar din fisierul ArboreBinar.java, in care s-au introdus metode recursive pentru traversarea arborelui in preordine, inordine si postordine si o metoda recursiva pentru reprezentarea arborelui sub forma de sir, in care fiecare subarbore este cuprins intr-o pereche de paranteze.

Pentru traversarea in preordine se folosesc urmatoarele doua 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() intoarce o lista, care contine obiectele din informatie din nodurile arborelui, traversate in preordine. In aceasta metoda se creeaza lista vida, iar punerea elementelor in lista se face de catre metoda recursiva private void preordine(List lista, Nod nod). Se remarca cu usurinta cat de simpla si clara este aceasta metoda: se viziteaza nodul nod si se pune in lista informatia din acesta, dupa care se traverseaza pe rand, prin aceeasi metoda, subarborele din stanga si cel din dreapta.

Pentru traversarea in inordine se procedeaza in mod similar, numai ca, in metoda private void inordine(List lista, Nod nod) se traverseaza mai intai subarborele din stanga, apoi se pune in lista informatia din nodul radacina si la sfarsit se traverseaza 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;
  }

In fine, la traversarea in postordine, se traverseaza mai intai cei doi subarbori, dupa care se pune in lista informatia din nodul radacina.
 
  /* 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 intr-un sir, s-a adoptat conventia de reprezentare cu paranteze. In aceasta conventie, de cate ori se trece catre un nivel superior se deschide o paranteza, iar cand se revine la nivelul superior se inchide paranteza respectiva. In consecinta, fiecare subarbore este cuprins intr-o pereche de paranteze. Daca un nod are un singur fiu, fiul lipsa se reprezinta printr-o pereche de paranteze vida (). Pentru reprezentarea arborelui ca sir a fost redefinita metoda 
    public String toString()
din clasa Object. Aceasta creeaza un StringBuffer vid sb, dupa care invoca metoda privata recursiva
    private static StringBuffer cu paranteze(StringBuffer sb, Nod nod)
care pune in sb subarborele cu radacina nod, convertit in sir.
  /* 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 aplicarii acestor metode se poate urmari la executarea aplicatiei de testare din fisierul TestArboreBinar.java.

Traversarea arborilor in latime (pe niveluri)

La traversarea in latime (engleza: breadth-first), numita si traversare pe niveluri, nodurile arborelui se parcurg si se viziteaza astfel: se incepe cu radacina, apoi se viziteaza de la stanga la dreapta toate nodurile de nivel 1, apoi toate nodurile de nivel 2 si asa mai departe. Prin fiecare nod se trece o singura data. In cazul arborelui din figura 2, ordinea de vizitare a nodurilor este urmatoarea: A, B, C, D, E, F.

Pentru a parcurge un arbore in latime (pe niveluri), se foloseste ca structura auxiliara o coada. La inceput se pune in coada radacina. Se considera ca nodul curent este cel din capul cozii. Se pun in coada toti fiii nodului curent, dupa care acesta se scoate din coada. Se continua astfel pana cand coada ramane vida. Iata cum evolueaza traversarea arborelui in latime in exemplul din figura 2:
 
Pasul
Nodul curent
  Continutul cozii (capul este in stanga)
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 (sfarsitul parcurgerii)
 

Lungimea cozii este egala cu latimea arborelui (numarul maxim de noduri de pe acelasi nivel).
 
 
Pentru traversarea arborilor in latime (pe niveluri), in clasa Aebore binar din fisierul ArboreBinar.java s-a definit un iterator sub forma clasei interioare TraversLatime. Ca structura de date auxiliara, aceasta clasa foloseste o coada, implementata 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 */
      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 obtinut prin metoda Iterator iteratorLatime() a clasei ArboreBinar. In fisierul TestArboreBinar.java este data aplicatia de testare a tuturor tehnicilor de traversare a arborelui binar.



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