Arbori
Acasă
Tipuri de arbori
Probleme tip
Padure
Cicluri elementare
Algoritmul lui Kruskal
Inaltimea unui Arbore
Memorarea Arborilor prin utilizarea referintelor ascendente
Triunghiuri asemenea
Algoritmul lui Prim
Arbori binari
Parcurgeri
>
Algoritmi
Parcurgerea Arborilor binari: cod sursa
Reprezentarea arborilor binari
Contact
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.
Solutiile de parcurgere ale arborelui din figura urmatoare :
parcurgere svd - in inordine
4 2 5 1 6 3 7 8
parcurgere vsd - in preordine
1 2 4 5 3 6 7 8 parcurgere sdv - in postordine
4 5 2 6 8 7 3 1
Programul alaturat 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();
}