Structuri de Date Arborescente Implementate Dinamic – Arbori Binari 14
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore binar și proprietățile acestuia.
- Să învețe cum să implementeze un arbore binar dinamic.
- Să implementeze operații comune pe arbori binari: inserare, căutare, traversare (în ordine, preordine, postordine).
2. Ce este un arbore binar?
- Definiție:
Un arbore binar este o structură de date arborescentă în care fiecare nod are cel mult doi copii:- Subarborele stâng
- Subarborele drept
- Proprietăți:
- Arborele binar poate fi complet, perfect sau degenerat.
- Într-un arbore binar, numărul maxim de noduri la nivelul hhh este 2h2^h2h.
- Înălțimea arborelui este dată de lungimea drumului de la rădăcină la cea mai adâncă frunză.
- Tipuri de arbori binari:
- Arbore binar complet: Fiecare nivel, cu excepția ultimului, este complet populat.
- Arbore binar de căutare (BST): Subarborele stâng conține valori mai mici, iar subarborele drept conține valori mai mari decât rădăcina.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Structură flexibilă pentru gestionarea datelor ierarhice. | Gestionarea dinamică necesită atenție pentru integritate. |
| Traversare eficientă pentru căutare, inserare și ștergere. | Performanța poate scădea în cazuri de arbori dezechilibrați. |
| Este baza pentru alte structuri complexe, cum ar fi heap-uri. |
4. Structura unui nod
struct Nod {
int valoare; // Valoarea stocată în nod
Nod* stanga; // Pointer către subarborele stâng
Nod* dreapta; // Pointer către subarborele drept
};
5. Operații comune pe arbori binari
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
2. Inserarea unui nod într-un arbore binar de căutare (BST)
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
3. Traversări ale arborelui
- Traversare în ordine (in-order):
Vizitează nodurile în ordinea: stânga → rădăcină → dreapta.
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
- Traversare preordine (pre-order):
Vizitează nodurile în ordinea: rădăcină → stânga → dreapta.
void traversarePreOrdine(Nod* radacina) {
if (radacina == nullptr) return;
cout << radacina->valoare << ” „;
traversarePreOrdine(radacina->stanga);
traversarePreOrdine(radacina->dreapta);
}
- Traversare postordine (post-order):
Vizitează nodurile în ordinea: stânga → dreapta → rădăcină.
void traversarePostOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversarePostOrdine(radacina->stanga);
traversarePostOrdine(radacina->dreapta);
cout << radacina->valoare << ” „;
}
4. Căutarea unui element
bool cautaValoare(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return false;
}
if (valoare == radacina->valoare) {
return true;
} else if (valoare < radacina->valoare) {
return cautaValoare(radacina->stanga, valoare);
} else {
return cautaValoare(radacina->dreapta, valoare);
}
}
5. Ștergerea unui nod
Nod* stergeNod(Nod* radacina, int valoare) {
if (radacina == nullptr) return radacina;
if (valoare < radacina->valoare) {
radacina->stanga = stergeNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = stergeNod(radacina->dreapta, valoare);
} else {
if (radacina->stanga == nullptr) {
Nod* temp = radacina->dreapta;
delete radacina;
return temp;
} else if (radacina->dreapta == nullptr) {
Nod* temp = radacina->stanga;
delete radacina;
return temp;
}
Nod* temp = radacina->dreapta;
while (temp->stanga != nullptr) {
temp = temp->stanga;
}
radacina->valoare = temp->valoare;
radacina->dreapta = stergeNod(radacina->dreapta, temp->valoare);
}
return radacina;
}
6. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* stanga;
Nod* dreapta;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
int main() {
Nod* radacina = nullptr;
radacina = insereazaNod(radacina, 50);
insereazaNod(radacina, 30);
insereazaNod(radacina, 70);
insereazaNod(radacina, 20);
insereazaNod(radacina, 40);
insereazaNod(radacina, 60);
insereazaNod(radacina, 80);
cout << „Traversare în ordine: „;
traversareInOrdine(radacina);
cout << endl;
return 0;
}
6. Activități practice pentru elevi
- Implementați o funcție care calculează înălțimea unui arbore binar.
- Scrieți un program care determină dacă un arbore este echilibrat.
- Implementați o funcție pentru numărarea nodurilor frunză dintr-un arbore binar.
7. Scheme logice
- Inserare:
- Verifică dacă nodul curent este gol -> Creează un nou nod -> Compară valoarea și inserează în stânga sau dreapta.
- Traversare:
- Utilizează recursivitate pentru a parcurge nodurile în ordinea specificată.
- Căutare:
- Compară valoarea căutată cu nodul curent -> Explorează subarborele corespunzător.
8. Concluzie
- Arborii binari sunt structuri de date versatile utilizate în multe aplicații informatice.
- Implementarea dinamică permite gestionarea eficientă a memoriei și flexibilitatea dimensiunii arborelui.