Arbori-parcurgerea

Operatiile de parcurgere a arborilor binari se simplifica mult daca vom considera ca fiecare nod al arborelui subordoneaza un subarbore binar stang si un subarbore binar drept. Avand in vedere aceasta observatie se vor defini subprograme recursive care utilizeaza tehnica 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 :

• • Parcurgerea in inordine (stanga –varf – dreapta SVD) – se parcurge mai intai subarborele stang, apoi varful, apoi subarborele drept.

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

  • Parcurgerea in postordine (stanga – dreapta – varf SDV) – se parcurge mai intai subarborele stang, apoi subarborele drept si la sfarsit varful.

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();

}