Arbori binari.
Definitie.Reprezentare.Parcurgere
Structurile arborescente reprezinta structuri neliniare de date cu multe aplicatii in programarea si utilizarea calculatoarelor.Intr-un limbaj simplist, 19319l1120t structurile arborescente exprima relatii de"ramificare" intre noduri,asemanatoare configuratiei arborilor din natura,cu deosebirea ca,in informatica,in mod traditional,arborii "cresc" in jos.
Definitie
Se numeste arborescenta un arbore care are un varf special numit radacina iar celelalte noduri pot fi repartizate in m multimi disjuncte X1,X2,.,Xm,m>0,astfel incat in fiecare din aceste multimi exista un nod adiacent cu radacina iar subgrafurile generate de acestea sunt la randul lor arborescente.
In particular,o arborescenta cu un singur nod este formata doar din nodul radacina.
Daca ordinea relativa a arborescentelor generate de multimile X1,X2,.,Xm din definitie are importanta,arborescenta se numeste arbore ordonat.
In reprezentarea grafica a unei arborescente,nodurile se deseneaza pe nivele,astfel:radacina se afla pe primul nivel,varfurile adiacente cu radacina - pe urmatorul nivel,si asa mai departe.
Nodurile adiacente cu radacina-care se deseneaza pe nivelul urmator-se numesc descendentii radacinii.In mod analog,in fiecare arbore ordonat a carui radacina este un nod aflat pe un nivel,nodurile adiacente cu acesta se numesc descendentii sai.Descendentii aceluiasi nod se mai numesc si frati.
Daca un nod x este descendentul altui nod y,il numim pe acesta din urma parintele nodului x.
Folosim deci termenii "descendent" si "parinte" pentru a exprima relatii intre noduri aflate pe nivele consecutive in reprezentarea vizuala a arborilor.
Terminologia utilizata in structurile arborescente include chiar cuvinte ca fiu,tata,frati,unchi,veri,strabunic,cu inteles similar celui din vorbirea curenta pentru noduri aflate pe diverse nivele.
Prezentam ca exemplu de utilizare a acestei structuri de date modalitatea de organizare arborescenta a software-ului unui calculator utilizata de sisteme de operare ca MS-DOS,Unix,Linux,etc.De asemenea sa observam ca orice tablou poate fi privit ca un caz special de structura arborescenta.
Definitie
Un arbore binar este o multime finita de noduri care este fie vida,fie reprezinta un arbore ordonat in care fiecare nod are cel mult 2 descendenti.
Din definitie rezulta ca un arbore binar contine cel mult doi sub-arbori binari(stang sau drept).Ei se obtin deci prin suprimarea radacinii si a muchiilor incidente cu aceasta.Oricare din ei poate sa fie vid.Daca arborele binar este format dintr-un singur nod,atunci ambii subarbori sunt vizi.
Un nod fara descendenti se numeste nod terminal sau frunza.
Un arbore binar in care fiecare nod care nu este terminal are exact doi descendenti,se numeste arbore binar complet.
Propozitie
Un arbore binar complet care are n noduri terminale, toate situate pe acelasi nivel,are in total 2n-1 noduri.
Corolar
Un arbore binar complet are un numar impar de noduri.
Reprezentarea arborilor binari
Exista mai multe moduri de reprezentare a arborilor binari;astfel putem avea:
a.Reprezentarea standard:se specifica radacina RAD si,pentru fiecare varf,se precizeaza descendentul stang si drept.Modul concret in care se precizeaza descendentii unui varf poate sa varieze:putem utiliza vectori,asa cum vom detalia imediat,sau putem folosi avantajele alocarii dinamice,care ne permite sa legam un nod de parintele sau utilizand adrese reale de memorie.
In prima varianta se folosesc doi vectori S si D,pentru fiecare varf I,S[i] fiind descendentul stang,D[i]-descendentul drept,iar INF[i] reprezentand informatia asocoata nodului.Lipsa unui descendent se indica prin valoarea zero in S sau D.
Pentru arborele binar din figura de mai jos avem n=7,RAD=1 si S=(2,0,5,0,6,0,0),D=(3,0,4,0,7,0,0).Sa observam ca in general nu este esential sa precizam radacina,ea putand fi dedusa din vectorii S si D,dat fiind faptul ca radacina nu este singurul varf care nu este descendentul vreunui alt varf.
b.Se dau vecorii TATA,care precizeaza pentru fiecare varf I,nodul TATA[i]care reprezinta parintele sau si DESC,care indica prin valoarea -1 sau 1,daca varful i este decendentul stang sau drept al parintelui sau TATA[i].Pentru nodul radacina care nu are un nod parinte asociat,componenta corespunzatoare din vectorul TATA va fi 0.Pentru arborele binar di figura de mai sus avem:
TATA=(0,1,1,3,3,5,5) si
DESC=(0,-1,1,1,-1,-1,1)
Parcurgerea arborilor binari
Exista multi algoritmi de prelucrare a a structurilor arborescente,dar una dintre problemele care apar in mod frecvent in acesti algoritmi este necesitatea de a parcurge sau de a traversa arborele.
Prin parcurgerea unui arbore se intelege examinarea in mod sistematic a nodurilor sale astfel incat fiecare nod sa fie atins o singura data.Aceasta actiune este numita si "vizitare" a varfurilor arborelui,scopul ei fiind de a stationa in fiecare varf pentru a efectua o prelucrare a informatiei asociata varfului respectiv.Arborele este o structura neliniara de organizare a datelor,iar rolul traversarii sale este tocmai conceperea unei aranjari liniare a nodurilor in vederea trecerii de la unul la altul,fructificand avantajul acestei organizari.
Exista trei modalitati principale de parcurgere a arborilor binari:nodurile pot fi vizitate in preordine,inordine si postordine.Aceste trei metode sunt definite recursiv:daca arborele este vid atunci el este traversat fara a se face nimic;altfel,traversarea se face in trei etape:
a.Travesarea in preordine
I.Se viziteaza radacina;
II.Se traverseaza subarborele stang;
III. Se traverseaza subarborele drept.
b.Traversarea in inordine
I.Se traverseaza subarborele stang;
II.Se viziteaza radacina;
III.Se traverseaza subarborele drept.
c.Traversarea in postordine
I.Se traverseaza subarborele stang;
II.Se traverseaza subarborele drept;
III.se viziteaza radacina.
Pentru arborele din figura de mai sus parcurgerea in preordine furnizeaza varfurile in ordinea: 1,2,3,5,6,7,4;parcurgerea in inordine furnizeaza varfurile in ordinea: 2,1,6,5,7,3,4;iar parcurgerea in postordine conduce la:2,6,7,5,4,3,1.
|
