ARBORI BINARI
Un arbore binar este un caz special de arbore, în care fiecare nod poate avea maxim doi descendenţi:
- nodul stâng
- nodul drept.
Exemplu de arbore binar:
Fig.
În funcţie de elementele ce pot fi reprezentate în noduri şi de restricţiile aplicate arborelui, se pot crea structuri de date cu proprietăţi deosebite: heap-uri, arbori AVL, arbori roşu-negru, arbori Splay şi multe altele.
REPREZENTAREA ARBORILOR BINARI
Arborii binari pot fi reprezentați în mai multe moduri. Structura din spatele acestora poate fi un simplu vector, alocat dinamic sau nu, sau o structură ce folosește pointeri
PARCURGEREA ARBORILOR BINARI
A. Parcurgerea ca un graf clasic
B. Parcurgri specifive arborilor binari
Fie arborele din figura
Fig.
-
Parcurgeri în adâncime specifice arborilor binari
Parcurgerea în Preordine
- Se parcurge rădăcina
- Se parcurge subarborele stâng
- Se parcurge subarborele drept
Parcurgerea în Inordine
- Se parcurge subarborele stâng
- Se parcurge rădăcina
- Se parcurge subarborele drept
Parcurgerea în Postordine
- Se parcurge subarborele stâng
- Se parcurge subarborele drept
- Se parcurge rădăcina
Fig.
Strabaterea in Preordine
Strabaterea in Inordine
Strabaterea in Postordine
Se implementeaza foarte usor recursiv:
Se folosește o coadă, iar la fiecare pas se extrage din această coadă câte un nod și se adăugă înapoi în coadă nodul stâng, respectiv drept al nodului scos. Acest algoritm continuă până când coada devine goală.
Nodurile frunză nu au descendenţi → nodul stâng şi nodul drept pointează la NULL şi nu trebuie adăugate în coadă.
EXEMPLE DE APLICAŢII PENTRU EXPLOATAREA ARBORILOR BINARI
A. Crearea unui arbore binar
15 3
0 5 4 15 0 1 6 11 0 0 0 0 8 13 0
0 0 14 7 0 0 0 0 0 12 0 0 10 2 9
B. Strabaterea unui arbore binar
Fig.
