Parcurgerea arborilor binari

Parcurgerea arborilor binari

Prin parcurgerea arborilor binari se intelege, ca si la glafurile obisnuite, examinarea in mod sistematic a nodurilor a.i. fiecare nod sa fie atins o singura data. Aceasta procedura se mai numeste si VIZITARE a nodurilor arborelui in scopul prelucrarii informatiei continute de fiecare dintre acestea.

Deoarece arborii sunt structuri neliniare de organizare a datelor, rolul traversarii este tocmai obtinerea unei aranjari liniare a nodurilor, pentru ca trecerea de la unul la altul sa se realizeze cat mai simplu posibil.

Analizand situatia la nivelul unui arbore binar, se observa ca pentru a avea parcurgere riguroasa dar mai ales eficienta, tebuie precizata in fiecare moment pozitia a trei componente, si anume: radacina si cei doi subarbori ai sai (stang si drept). Sunt deci 3!=6 variante. Pentru a facilita reprezentarea unui arbore binar se tine seama de urmatoarea regula: totdeauna este reprezentat subarborele stang si apoi subarborele drept. In raport de acestia, se pozitioneaza radacina. S-au obtinut astfel 3 posibilitati de reprezentare. Acestea sunt definite recursiv: daca arborele este vid, atunci el este traversat fara a executa nimic; daca nu este vid, atunci se executa pasii dintre cele trei modalitati de traversare:

(RDS)   1. Traversarea in preordine presupune:

Pasul 1 Se viziteaza radacina;

Pasul 2 Se treverseaza subarborele stang;

Pasul 3 Se treverseaza subarborele drept.

(SRD)   2. Traversarea in ordine presupune:

Pasul 1 Se treverseaza subarborele stang;

Pasul 2 Se viziteaza radacina;

Pasul 3 Se traverseaza subarborele drept;

(SDR)   3. Traversarea in postordine presupune:

Pasul 1 Se treverseaza subarborele stang;

Pasul 2 Se traverseaza subarborele drept;

Pasul 3 Se viziteaza radacina.

Observatie:      Denumirea metodelor semnifica momentul cand se viziteaza radacina in raport cu vizitarea subarborilor (subarborele stang inainte celui drept in totdeauna).

Procedurile PASCAL de parcurgere a uni arbore binar prezentate in continuare aplica prima modalitate de prezentare a arborilor binari, adica folosesc cei doi vectori S si D pentru retinerea descendentilor stanga si respectiv dreapta ai fiecarui nod. Aceste programe, realizate folosind metoda de rezolvare DIVIDE ET IMPERA, sunt:

program parcurg_arbore;

uses crt;

var s,d: array[1..10] of byte;

rad, n, i, k: byte;

procedure RSD (k:byte);

begin

write (k, ' ');

if s[k]<> 0 then RSD (s[k]);

if d[k]<> 0 then RSD (d[k]);

end;

procedure SRD (k: byte);

begin

if s[k]<>0 then SRD(s[k]);

write (k, ' ');

if d[k]<>0 then SRD (d[k]);

end;

procedure SDR (k: byte);

begin

if s[k]<>0 then SDR (s[k]);

if d[k]<>0 then SDR (d[k]);

write(k, ' ');

end;

begin

clrscr;

write('Introduceti numarul de varfuri n: '); readln(n);

write ('Introduceti nodul radacina: '); readln(rad);

for i:=1 to n do

begin

writeln(' Pentru nodul ',I,' introduceti ');

write('descendent stang: '); read (s[i]);

write('descendent drept:'); read (d[i]);

end;

writeln;

writeln('*Parcurgere in preordine(RSD): ');

RSD(rad); writeln;

Writeln('*parcurgere in ordine(SRD): ');

SRD(rad); writeln;

Writeln('*Parcurgere in postordine (SDR) ');

SDR(rad); writeln;

Readln:

end