Informatică Programare
Arbori binari de cautare implementare C++
Un arbore binar de căutare (ABC) este o structură de date arborescentă în care fiecare nod are cel mult doi copii, iar pentru orice nod, toate nodurile din subarborele stâng au valori mai mici, iar cele din subarborele drept au valori mai mari. În C++, ABC-ul poate fi implementat folosind clase și pointeri pentru gestionarea eficientă a operațiilor de inserare, căutare și ștergere.
Structura unui nod ABC
- 1 Pasul 1: Definirea clasei Nod Creează o clasă care reprezintă un nod, cu date (valoare) și pointeri către copilul stâng și drept. Exemplu: class Nod { public: int val; Nod* stanga; Nod* dreapta; Nod(int v) : val(v), stanga(nullptr), dreapta(nullptr) {} };
- 2 Pasul 2: Inserarea unui nod Adaugă un nod nou comparând valoarea cu nodurile existente și parcurgând arborele recursiv. Exemplu: dacă val < nod->val, mergi la stânga; altfel, mergi la dreapta.
- 3 Pasul 3: Căutarea unei valori Parcurge arborele comparând valoarea căutată cu nodurile; returnează true dacă este găsită, false altfel.
Operații avansate pe ABC
- Ștergerea unui nod Implică trei cazuri: nod fără copii (șterge direct), cu un copil (înlocuiește cu copilul), cu doi copii (găsește succesorul în ordine și înlocuiește).
- Parcurgeri Parcurgere în inordine (stânga, rădăcină, dreapta) afișează valori sortate; preordine și postordine sunt alternative.
- Exemplu numeric Pentru valorile 5, 3, 7, 2, 4, arborele are rădăcina 5, cu stânga 3 (copii 2 și 4) și dreapta 7. Parcurgerea în inordine dă 2, 3, 4, 5, 7.
Începe prin a implementa inserarea și căutarea pentru un ABC simplu, apoi adaugă ștergerea pentru a înțelege gestionarea pointerilor.