Scribd

Parcurgerea arborilor binari

Operatiile de parcurgere a arborilor binari se simplifica mult daca vom considera cafiecare nod al arborelui subordoneaza un subarbore binar stang si un subarbore binar drept.Avand in vedere aceasta observatie se vor defini subprograme recursive care utilizeazatehnica Divide et Impera.Principalele modalitati de parcurgere ale unui arbore binar sunt:A) Arborii binari pot fi parcursi prin metode specifice grafurilor: in adancime, latime.B) Metode specifice arborilor binari :

y

Parcurgerea in inordine (stanga ±varf ± dreapta SVD) ± se parcurge mai intaisubarborele stang, apoi varful, apoi subarborele drept.

y

Parcurgerea in preordine (varf- stanga ± dreapta VSD) ± se parcurge mai intai varful,apoi subarborele stang, apoi subarborele drept.

y

Parcurgerea in postordine (stanga ± dreapta ± varf SDV) ± se parcurge mai intaisubarborele stang, apoi subarborele drept si la sfarsit varful.Solutiile de parcurgere ale arborelui din figura urmatoare : parcurgere svd - in inordine4 2 5 1 6 3 7 8 parcurgere vsd - in preordine1 2 4 5 3 6 7 8 parcurgere sdv - in postordine4 5 2 6 8 7 3 1Programul urmator genereaza un arbore binar memorat in heap si il parcurge prin cele 3metode.#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;}elsereturn 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();}