Metode De Parcurgeri A Arborilor

[+skyler_sdf]

1. Breadth first:

Se citeste matricea de adiacenta a unui graf orientat(nu are bucle, adica de la un nod i la un nod j exista o singura muchie (i,j)). Se cere pacurgerea lui in latime.

Parcurgerea in latime se face incepand de la un anumit nod i, pe care il consideram parcurs. Parcurgem apoi toti descendentii sai. Parcurgem toti descendentii nodurilor parcurse la pasul anterior. Un nod este parcurs o singura data.

Parcurgerea BF se efctueaza prin utilizarea structurii numita coada, avand grija ca un nod sa fie vizitat o singura data. Coada va fi alocata prin utilizarea unui vector.

#include<iostream.h>

#include<conio.h>

int coada[50], s[50], a[50][50], i_c, sf_c, i, n; //i_c indicele cozii care urmeaza a fi prelucrata

//sf_c ultima componenta a cozii

//s vectorul boolean ce retine nodurile introduse in coada

//0 daca nodul i nu a fost introdus in coada, 1 altfel

void bf()

{

int k;

if(i_c<=sf_c)

{

for(k=1; k<=n; k++)

if((a[coada[i_c]][k]==1) && (s[k]==0))

{

sf_c++;

coada[sf_c]=k;

s[k]=1;

}

i_c++;

bf();

}

}

void main()

{

cout<<"n="; cin>>n;

int i, j;

for(i=1; i<=n; i++)

for(j=1; j<=n; j++)

{

cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j];

}

i_c=sf_c=1;

coada[i_c]=s[1]=1;

bf();

for(i=1; i<=sf_c; i++)

cout<<coada[i]<<" ";

getch();

}

Exista mai multe solutii ale unei astfel de parcurgeri, pentru ca ordinea de parcurgere a descendentilor unui nod nu este impusa. Ea depinde si de modul in care a fost memorat graful. 2.Depth first Se citeste matricea de adiacenta a unui graf orientat(nu are bucle, adica de la un nod i la un nod j exista o singura muchie (i,j)). Se cere pacurgerea lui in adancime. Parcurgerea in adncime se face incepand de la un anumit nod i. Dupa parcurgerea unui nod se trece la primul dintre descendentii sai,neparcursi inca.

#include<iostream.h>

#include<conio.h>

int a[20][20], s[20], n;

void df(int nod)

{

int k;

s[nod]=1;

for(k=1; k<=n; k++)

 if((a[nod][k]==1 && (s[k]==0))

df(k);

}

void main()

{

 int i, j;

cout<<"dati nr de noduri: ";

cin>>n;

for(i=1; i<=n; i++)

 for(j=1; j<=n; j++)

{

 cout<<"a["<<i<<"]["<<j<<"]=" cin>>a[i][j];

}

cout<<endl;

df(1);

getch();

}

Principalele modalitati de parcurgere ale unui arbore binar sunt: 1. Parcurgerea in inordine(SVD)- se parcurge mai intai subarborele stang, apoi varful, apoi subarborele drept. 2. Parcurgerea in preordine(VSD)- se parcurge mai intai varful, apoi subarborele stang, apoi cel drept. 3. Parcurgerea in postordine(SDV)- se parcurge mai intai subarborele stang, apoi subarborele drept, apoi varful. 4. DF care a fost prezentata si mai sus.

#include<iostream.h>

#include<conio.h>

struct nod{

int nr;

nod *st, *dr;

};

nod *c;

void sdv(nod *c)

{

if(c)

{

sdv(c->st);

sdv(c->dr);

cout<<c->nr;

}

}

void svd(nod *c)

{

if(c)

{

svd(c->st);

cout<<c->nr;

svd(c->dr);

}

}

void vsd(nod *c)

{

if(c)

{

cout<<c->nr;

vsd(c->st);

vsd(c->dr);

}

}

nod *arbore()

{

int n;

nod *c;

cout<<"n=";  cin>>n;

if(n)

{

c=new nod;

c->nr=n;

c->st=arbore();

c->dr=arbore();

return c;

}

else

return 0;

}

void main()

{

 c=arbore();

vsd(c);

cout<<endl;

svd(c);

cout<<endl;

sdv(c);

getch();

}