Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 6 - ARBORI BINARI
A.Consideratii teoretice
Definitie: Numim arbore un graf conex si fara cicluri. Un arbore este determinat de cateva proprietati:
- Un nod special numit radacina in care nu intra nici un arc.
- Din fiecare nod pot iesi zero, unul sau mai multe arce, numite fii.
- Din fiecare nod (mai putin radacina) poate intra un singur arc, dintr-un nod numit parinte.
- Nodurile sunt organizate pe nivele, primul nivel este ocupat numai de radacina, iar ultimul nivel contine numai noduri din care nu iese nici un arc, numite noduri terminale, sau frunze.
- Fiecare nod poate contine o informatie numita informatie utila sau cheie a arborelui.
In acest exemplu avem un arbore cu 9 noduri, in care nodul 1 este radacina si care se afla pe nivelul 1, are trei fii - nodurile 2, 3 si 4 de pe nivelul 2, nodul are doi fii - nodurile 5 si 6, nodul 3 este un nod terminal, iar nodul 4 are un fiu - nodul 7 - toate se afla pe nivelul 3, iar pe nivelul 4 se afla fii nodului 6 - nodurile 8 si 9, pentru ca nodurile 5 si 7 sunt noduri terminale.
Definitie: Numim arbore binar un arbore in care fiecare nod are zero, unul sau cel mult doi fii (descendenti).
Definitie: Un arbore binar cu proprietatea ca fiecare nod cu exceptia frunzelor (nodurilor terminale) are exact doi descendenti se numeste arbore binar complet.
1. Se specifica radacina RAD si pentru fiecare nod se precizeaza descendentul stang si descendentul drept, in cazul in care acestia exista. Acesti descendenti de retin cu ajutorul unor vectori numiti chiar ST si DR, astfel pentru un nod I, ST[i] reprezinta descendentul stang, DR[i] descendentul drept, iar INF[i] reprezinta informatia atasata arborelui. Atunci cand un descendent lipseste se specifica valoarea zero.
Avem n = 7 noduri, RAD = 1 si ST = { 2, 0, 5, 0, 6, 0, 0 } si DR = { 3, 0, 4, 0, 7, 0, 0 }.
2. Se folosesc vectorii TATA care precizeaza pentru fiecare nod i, nodul parintelui sau – TATA[i] si DESC, vector care retine valorile –1 sau 1 in functie de nodul i care este fie descendent stang, fie descendent drept.
Pentru acelasi exemplu, vectori considerati mai sus au urmatoarele valori:
TATA = { 0, 1, 1, 3, 3, 5, 5 } si DESC = { 0, -1, 1, 1, -1, -1, 1 }.
3. Se foloseste alocarea dinamica a memoriei astfel incat fiecare nod este compus din un camp de informatie si doua campuri de adrese stanga si dreapta. Definirea unui astfel de nod se face astfel:
typedef struct pnod
{
int inf;
struct *as,*ad;
}
Parcurgerea arborilor binari
Pentru a putea prelucra informatiile dintr-un arbore, trebuie sa parcurgem nodurile arborelui. Exista trei modalitati de parcurgere a arborilor de binari: nodurile pot fi vizitate in preordine, inordine si postordine. Aceste metode sunt definite recursiv, astfel daca arborele este vid atunci el este traversat fara a se face nimic; altfel traversarea se face in trei etape.
1) Travesarea in preordine
- se viziteaza radacina
- se traverseaza subarborele stang
- se traverseaza subarborele drept
2) Travesarea in inordine
- se traverseaza subarborele stang
- se viziteaza radacina
- se traverseaza subarborele drept
3) Travesarea in postordine
- se traverseaza subarborele stang
- se traverseaza subarborele drept
- se viziteaza radacina
B.Exemple de programe
1. Prezentam in continuare programul in limbajul Borland C++ care implementeaza cele trei tipuri de parcurgere de mai sus, in reprezentarea arborilor static folosind vectorii ST si DR.
2. Prezentam in continuare programul in limbajul Borland C++ care implementeaza cele trei tipuri de parcurgere de mai sus, in reprezentarea arborilor dinamic folosind pointeri. Vom construi arborele binar recursiv:
3. Sa se creeze un arbore binar cu informatii numere intregi, apoi sa se tipareasca suma elementelor pare din arbore.
4. Sa se construiasca un arbore binar si apoi sa se caute o valoare data, specificandu-se daca este sau in arbore.
C. Exercitii si teme
1. Sa se ruleze programele prezentate mai sus.
2 Sa se scrie o functie care returneaza numarul de nivele ale unui arbore binar ( inaltimea arborelui ). Functia va primi ca parametru un pointer p catre radacina arborelui.
3. Sa se scrie o procedura care tipareste informatiile din nodurile aflate pe un anumit nivel dat. Procedura va primi ca parametri numarul nivelului, precum si un pointer catre radacina arborelui.