Informatică Programare
Arbori binari de cautare implementare C++ 12a
Un arbore binar de căutare (ABC) în C++ este o structură de date î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 dreapta au valori mai mari. În clasa a 12-a, implementezi ABC-uri pentru a învăța algoritmi de căutare și sortare eficiente.
Componentele unui ABC
- Structura unui nod Conține o valoare (ex: int), și pointeri către nodul copil stâng și drept: struct Nod { int val; Nod* stg; Nod* dr; };
- Operații de bază Inserare, căutare, ștergere și parcurgere (în ordine, preordine, postordine).
- Proprietatea de ordine Pentru orice nod, valoarea din stânga < valoarea nodului < valoarea din dreapta.
Exemplu de implementare a inserării
- 1 Definește funcția de inserare Nod* insereaza(Nod* rad, int val) { if (!rad) return new Nod{val, nullptr, nullptr}; if (val < rad->val) rad->stg = insereaza(rad->stg, val); else rad->dr = insereaza(rad->dr, val); return rad; }
- 2 Creează un ABC Nod* rad = nullptr; rad = insereaza(rad, 10); rad = insereaza(rad, 5); rad = insereaza(rad, 15);
- 3 Parcurge în ordine Funcția 'afiseazaInOrdine' va afișa 5, 10, 15, demonstrând ordonarea.
Pentru bac, exersează scrierea recursivă a funcțiilor pentru ABC și verifică proprietățile de ordine cu exemple numerice pentru a înțelege structura.