Problema parcurgerii unui arbore binar constă în identificarea unei modalităţi prin care, plecând din
rădăcină şi mergând pe muchii, să ajungem în toate vârfurile; în plus, atingerea fiecărui vârf este pusă în evidenţă o singură dată: spunem că vizităm vârful respectiv.
Acţiunea întreprinsă la vizitarea unui vârf depinde de problema concretă şi poate fi de exemplu tipărirea informaţiei ataşate vârfului.
1) Parcurgerea în preordine
Se parcurg recursiv în ordine: rădăcina, subarborele stâng, subarborele drept.
Concret, se execută apelul preordine(rad) pentru procedura:
void preordine(int x)
{
if( x!=0 ){
cout<<x<<” “;
preordine(st(x));
preordine(dr(x));
}
return;
}
Pentru arborele binar de mai sus acest modul de parcurgere, este precizat figurând îngroşat rădăcinile subarborilor ce trebuie dezvoltaţi:
• 1
• 1, 2, 8
• 1, 2, 3, 5, 8, 9
• 1, 2, 3, 4, 5, 6, 7, 8, 9
2) Parcurgerea în inordine
Se parcurg recursiv în ordine: subarborele stâng, rădăcina, subarborele drept.
Concret, se execută apelul inordine(rad) pentru procedura
void inordine(int x)
{
if( x!=0 )
{
inordine(st(x));
cout<<x<<” “;
inordine(dr(x));
}
return;
}
Modul de parcurgere pentru exemplul de mai sus:
• 1
• 2, 1, 8
• 3, 2, 5, 1, 8, 9
• 4, 3, 2, 6, 5, 7, 1, 8, 9
3) Parcurgerea în postordine
• Se parcurg recursiv în ordine: subarborele stâng, subarborele drept, rădăcina.
• Concret, se execută apelul postordine(rad) pentru procedura:
void postordine(int x)
{
if( x!=0 )
{
postordine(st(x));
postordine(dr(x));
cout<<x<<” “;
}
Modul de parcurgere pentru exemplul de mai sus:
• 1
• 2, 8, 1
• 3, 5, 2, 9, 8, 1
• 4, 3, 6, 7, 5, 2, 9, 8, 1
Codul sursa pentru creare a unui arbore binar cu ajutorul vectorilor st si dr si apoi traversarea arborelui:
# include <iostream.h>
int st[15],dr[15],n,i,j,rad;
void inordine(int x)
{
if (st[x]!=0) inordine(st[x]);
cout<<" "<<x;
if (dr[x]!=0) inordine(dr[x]);
}
void preordine(int x)
{
cout<<" "<<x;
if (st[x]!=0) preordine(st[x]);
if (dr[x]!=0) preordine(dr[x]);
}
void postordine(int x)
{
if (st[x]!=0) postordine(st[x]);
if (dr[x]!=0) postordine(dr[x]);
cout<<" "<<x;
}
int main(void)
{
cout<<"Dati numarul de noduri n = ";cin>>n;
cout<<"Dati radacina rad = ";cin>>rad;
for(i=1;i<=n;i++)
{
cout<<"st["<<i<<"]=";cin>>st[i];
cout<<"dr["<<i<<"]=";cin>>dr[i];
}
cout<<"\n parcurgerea in inordine este ";
inordine(rad);
cout<<"\n parcurgerea in preordine este ";
preordine(rad);
cout<<"\n parcurgerea in postordine este ";
postordine(rad);
}