Structuri de date neliniare (arbori binari, grafuri)

Structurile de date neliniare sunt fundamentale în informatica modernă, deoarece modelează relații complexe între elemente, spre deosebire de structurile liniare (liste, stive, cozi). Două dintre cele mai importante sunt arborii binari și grafurile.

Un arbore binar este o structură ierarhică în care fiecare nod are cel mult doi copii: stânga și dreapta. Proprietățile cheie includ: rădăcina (primul nod), nodurile interne (cu cel puțin un copil) și frunzele (fără copii). Înălțimea arborelui este numărul maxim de muchii de la rădăcină la o frunză.

Arborii binari sunt utilizați în căutări rapide (arbori binari de căutare – BST), heap-uri pentru priorități, arbori de expresii matematice și multe altele. Parcurgerile clasice sunt: în preordine (rădăcină, stânga, dreapta), în inordine (stânga, rădăcină, dreapta – pentru BST dă elemente sortate), în postordine (stânga, dreapta, rădăcină) și pe niveluri (BFS). Operațiile uzuale sunt inserarea, ștergerea, căutarea, aflarea înălțimii și traversările recursive sau iterative.

Un graf este o mulțime de noduri (vârfuri) conectate prin muchii. Se clasifică în: orientat (muchii cu direcție) și neorientat (muchii bidirecționale); ponderat (muchii cu cost) și neponderat. Reprezentările uzuale sunt matricea de adiacență (O(n^2) memorie) și lista de adiacență (eficientă pentru grafuri rare).

Parcurgerile fundamentale sunt BFS (breadth-first search) și DFS (depth-first search), esențiale pentru probleme de conectivitate, componente conexe, drumuri minime (Dijkstra, Bellman-Ford), sortare topologică (grafuri orientate aciclice) și determinarea arborelui minim de acoperire (Kruskal, Prim). Complexitățile variază: O(n+m) pentru parcurgeri, O((n+m) log n) pentru Dijkstra cu heap.

La BAC, elevii trebuie să implementeze în C++/Python operații pe arbori binari (creare, traversări, căutare) și pe grafuri (BFS, DFS, determinare componente conexe, verificare ciclicitate, drum minim neponderat). Înțelegerea proprietăților de conexitate, aciclicitate și a modului de stocare în memorie este crucială.

Exemple practice: arborele binar de căutare pentru stocarea unui dicționar; grafurile pentru rețele sociale sau hărți rutiere. Abordarea pedagogică presupune începerea cu definiții, trecerea la reprezentări vizuale, apoi la implementări pas cu pas, subliniind cazurile particulare (arbore vid, graf fără muchii, etc.).

Exemple

• Exemplul 1: Parcurgerea în inordine a unui arbore binar de căutare (BST). Se consideră arborele cu rădăcina 10, copil stânga 5 (care are stânga 2, dreapta 7) și copil dreapta 15 (cu stânga 12, dreapta 20). Parcurgerea în inordine (stânga, rădăcină, dreapta) va produce: 2, 5, 7, 10, 12, 15, 20. Observăm că elementele sunt sortate crescător. Implementarea recursivă în C++: void inorder(Nod* rad) { if(rad==NULL) return; inorder(rad->st); cout<<rad->val<<' '; inorder(rad->dr); } Complexitatea este O(n), unde n = numărul de noduri.
• Exemplul 2: Parcurgerea BFS (breadth-first) a unui graf neorientat reprezentat prin liste de adiacență. Fie graful cu 6 noduri (numerotate 1..6) și muchiile: 1-2, 1-3, 2-4, 2-5, 3-6. Pornind din nodul 1, BFS vizitează: nivel 0: 1; nivel 1: 2, 3; nivel 2: 4, 5, 6 (ordinea poate varia în funcție de ordinea listelor). Algoritmul folosește o coadă. În C++: queue<int> q; q.push(1); visited[1]=true; while(!q.empty()) { int u = q.front(); q.pop(); for(int v: adj[u]) if(!visited[v]) { visited[v]=true; q.push(v); } }. Se observă că BFS găsește drumul cel mai scurt (în muchii) de la sursă la orice nod.
• Exemplul 3: Verificarea dacă un graf orientat conține un ciclu, folosind DFS. Se consideră graful cu nodurile A, B, C, D și muchiile: A->B, B->C, C->A, A->D. Se porneste DFS din A, marcând nodurile în stivă (în proces). La vizitarea lui C, se descoperă muchia C->A, iar A este deja în stiva curentă, deci există un ciclu (A->B->C->A). Algoritmul ține un vector visited (3 stări: nevizitat, în curs, procesat). Implementare pseudocod: DFS(u): marchez u ca 'in curs'; pentru fiecare v adiacent: dacă v este 'in curs' -> ciclu; dacă v e 'nevizitat' -> DFS(v). La final, marchezi u ca 'procesat'. Complexitate O(n+m).

Concepte cheie: Arbore binar: definiție, noduri, rădăcină, frunze, înălțime, Parcurgeri: preordine, inordine, postordine, BFS (pe niveluri), Arbore binar de căutare (BST): proprietatea de ordonare, operații (căutare, inserare, ștergere), Graf: definiție, noduri, muchii, orientat/neorientat, ponderat/neponderat, Reprezentări: matrice de adiacență, listă de adiacență, Parcurgeri graf: BFS (coadă), DFS (stivă/recursiv), aplicații (componente conexe, drum minim în muchii), Detectare cicluri în graf orientat/neorientat, Sortare topologică (graf orientat aciclic – DAG), Arbore minim de acoperire (MST): algoritmii Kruskal și Prim, Drum minim: algoritmul Dijkstra, Bellman-Ford (pentru muchii cu costuri negative)