Structuri de Date Arborescente Implementate Dinamic – Arbori 12
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore și proprietățile acestuia.
- Să învețe cum să implementeze un arbore binar folosind alocarea dinamică a memoriei.
- Să implementeze operații comune pe arbori: inserare, traversare (în ordine, preordine, postordine) și căutare.
2. Ce este un arbore?
- Definiție:
Un arbore este o structură de date non-liniară care conține noduri organizate ierarhic. Fiecare nod poate avea copii, iar primul nod este numit rădăcină (root). - Proprietăți ale arborilor:
- Un arbore are un singur nod rădăcină.
- Fiecare nod are un părinte, cu excepția rădăcinii.
- Nodurile fără copii se numesc frunze (leaves).
- Un arbore poate avea subarbori.
- Tipuri de arbori:
- Arbore binar: Fiecare nod poate avea cel mult doi copii.
- Arbore binar de căutare (BST): Valorile din subarborele stâng sunt mai mici decât rădăcina, iar cele din subarborele drept sunt mai mari.
3. Avantaje și dezavantaje
Avantaje | Dezavantaje |
Eficient pentru căutări rapide în structuri mari (BST). | Implementarea și gestionarea sunt mai complexe. |
Structură flexibilă pentru date ierarhice. | Consumul de memorie crește cu dimensiunea arborelui. |
4. Structura unui nod
- Structura unui nod pentru un arbore binar:
struct Nod {
int valoare; // Informația stocată
Nod* stanga; // Pointer către subarborele stâng
Nod* dreapta; // Pointer către subarborele drept
};
- Pointerul către rădăcina arborelui:
Nod* radacina = nullptr;
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)
- Funcția de inserare:
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
- Funcția de căutare:
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. 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);
}
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);
}
}
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;
cout << „Căutare valoare 40: ” << (cautaValoare(radacina, 40) ? „Găsită” : „Negăsită”) << endl;
cout << „Căutare valoare 25: ” << (cautaValoare(radacina, 25) ? „Găsită” : „Negăsită”) << endl;
return 0;
}
6. Activități practice pentru elevi
- Implementați o funcție care determină numărul de noduri dintr-un arbore.
- Realizați o funcție care calculează înălțimea unui arbore.
- Scrieți un program care determină dacă un arbore este arbore binar de căutare.
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 sunt structuri de date esențiale pentru gestionarea informațiilor ierarhice și pentru căutări rapide.
- Implementarea arborilor binari necesită înțelegerea recursivității.
- Practica ajută la stăpânirea conceptelor și implementării eficiente.