Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice


Acasa » referate » informatica
Parcurgerea arborilor binari

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







Politica de confidentialitate







.com Copyright © 2022 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 Proiect didactic Clasa: a-IX-a, Luarea deciziilor
 PROIECT DIDACTIC 3-5 ani dezvoltarea limbajului si a comunicarii orale - „Cine face, ce face”
 PROIECT MOTOR ASINCRON - Determinarea parametrilor schemei echivalente si a caracteristicilor de functionare in regim stabilizat de la gol la sarcina
 TEMA DE PROIECTARE - arbore de masina rotativa

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Atestat la informatica cu tema “gestionarea unui magazin de confectii”
 Proiect atestat electrician constructor - tehnologia montarii instalatiilor electrice interioare
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM

Proiect Atestat informatica - Limbajul Pascal
Manual Carp
OFERTA COMERCIALA DE EXPORT A FIRMEI 'BitDefender S.R.L.”
SISTEME INFORMATIONALE SI SISTEME INFORMATICE IN GESTIUNEA ORGANIZATIILOR
Operatiile de inmultire si impartire in virgula flotanta
METODOLOGII, METODE SI TEHNICI DE REALIZARE/DEZVOLTARE A SISTEMELOR INFORMATICE
Proiect Fisiere Relative - Algoritmi in Programare
Trasaturile marketingului la inceput de secol XXI





Termeni si conditii
Contact
Creeaza si tu