PARCURGEREA ARBORILOR BINARI

PARCURGEREA ARBORILOR BINARI

Prin parcurgerea arborilor binari se intelege examinarea in mod sistematic a nodurilor sale astfel incat fiecare nod sa fie atins o singura data. Exista trei modalitati, specifice arborilor binari, de parcurgere:

parcurgerea in preordine (RSD : radacina-stanga-dreapta)

parcurgerea in inordine (SRD : stanga-radacina-dreapta)

parcurgerea in postordine(SDR : stanga-dreapta-radacina)

Parcurgerea in preordine a arborelui cu radacina I, presupune parcurgerea etapelor:

>       se viziteaza radacina (nodul i);

>        daca exista, se parcurge in preordine subarborele stang (are radacina st[I];

>        daca exista, se parcurge in preordine subarborele drept (are radacina dr[I];

procedure preordine(I:integer); begin

write(info[I]:4);

if (st[I]<>0) then preordine(st[I]);

if (dr[I]<>0) then preordine(dr[I]); end;

Parcurgerea in inordine, a arborelui cu radacina I, presupune parcurgerea etapelor:

>       daca exista, se parcurge in inordine subarborele stang (are radacina st[I]);

>       se viziteaza radacina (nodul i);

>       daca exista, se parcurge in inordine subarborele drept (are radacina dr[I]);

procedure inordine(I:integer); begin

if (st[I]<>0) then inordine(st[I]);

write(info[I]:4);

if (dr[I]<>0) then inordine(dr[I]); end;

Parcurgerea in postordine, a arborelui cu radacina I, presupune parcurgerea etapelor:

Ø    daca exista, se parcurge in postordine subarborele stang (are radacina

st[I];

Ø    daca exista, se parcurge in postordine subarborele drept (are radacina
dr[I]);

Ø    se viziteaza radacina (nodul i);

procedure postordine(I:integer); begin

if (st[I]<>0) then postordine(st[I]);

if (dr[I]<>0) then postordine(dr[I]);

write(info[I]:4); end;

Exemplu. Fie arborele binar: