Parcurgerile sunt cele mai frecvent utilizate operaţii
pe arbori. A parcurge un arbore înseamnă a vizita fiecare nod al arborelui o
singură dată, în scopul prelucrării informaţiei asociate nodului.
Există mai multe posibilităţi de parcurgere a
arborilor- în adâncime (preordine, inordine, postordine) sau pe niveluri, dar
în toate cazurile atât arborele, cât şi subarborii sunt
prelucraţi în acelaşi mod.
Principalele moduri de parcurgere a arborilor binari
sunt:
- parcurgerea în adâncime; și
- parcurgerea pe niveluri.
 |
Figura nr. 11 – Parcurgerea arborilor
binari
|
1. Parcurgerile în adâncime
În toate cele trei tipuri de
parcurgere în adâncime
se vizitează mai întâi subarborele stâng, apoi subarborele drept. Diferenţa
constă în poziţia rădăcinii faţă de cei doi subarbori. Fie scrise recursiv, fie
iterativ, procedurile de parcurgere în adâncime necesită o stivă.
Clasificarea tipurilor de parcurgere în adâncime:
• Preordine (rsd):
Pentru a parcurge un arbore binar
în preordine, se vizitează mai întâi rădăcina, se parcurge în preordine
subarborele stâng, apoi se parcurge în preordine subarborele drept.
Exemplu: Parcurgerea în preordine
a arborelui din Figura nr.11 este: 1 2 4 5 3 6 7 8
• Inordine (srd):
Pentru a parcurge în inordine un
arbore binar, se parcurge în inordine subarborele stâng, se vizitează radăcina,
apoi se parcurge în inordine subarborele drept.
Exemplu: Parcurgerea în inordine a
arborelui din Figura nr.11 este: 4 2 5 1 6 3 7 8
• Postordine (sdr):
Pentru a parcurge în postordine un
arbore binar, se parcurge în postordine subarborele stâng, apoi cel drept, apoi
se vizitează rădăcina.
Exemplu: Parcurgerea în postordine
a arborelui din Figura nr.11 este: 4 5 2 6 8 7 3 1
Programul
urmator genereaza un arbore binar memorat in heap si il parcurge prin cele 3
metode.
#include<iostream.h>
#include<conio.h>
struct
nod{int nro;
nod*st,*dr;};
nod *r;
void
svd(nod *c)
{if(c)
{svd(c->st);
cout<<c->nro<<" ";
svd(c->dr);
}
}
void
vsd(nod *c)
{if(c)
{cout<<c->nro<<"
";
vsd(c->st);
vsd(c->dr);
}
}
void
sdv(nod *c)
{if(c)
{sdv(c->st);
sdv(c->dr);
cout<<c->nro<<" ";
}
}
nod*
citire_h()
{int nr;
nod*c;
cout<<"nr de ordine ";
cin>>nr;
if(nr)
{c=new nod;
c->nro=nr;
c->st=citire_h();
c->dr=citire_h();
return c;
}
else
return 0;
}
void
main()
{clrscr();
r=citire_h();
cout<<endl<<"parcurgere
svd - in inordine "<<endl;
svd(r);
cout<<endl<<"parcurgere
vsd - in preordine "<<endl;
vsd(r);
cout<<endl<<"parcurgere
sdv - in postordine "<<endl;
sdv(r);
getch();
}
2. Parcurgerea pe niveluri
Se vizitează întâi rădăcina, apoi fiul stâng al
rădăcinii, apoi cel drept şi se continuă în acest mod vizitând nodurile de pe
fiecare nivel de la stânga la dreapta.
Exemplu: Parcurgerea în postordine a
arborelui din Figura nr.11 este: 1 2 3 4 5 6 7 8