Arbore binar

Într-un arbore binar, fiecare nod are cel mult doi fii, numiți stâng și drept. Pozițiile contează: un singur fiu stâng nu este același lucru cu un singur fiu drept. Pentru rădăcina 5, fiu stâng 2 și fiu drept 8, ordinea în inordine este 2, 5, 8.

Într-un arbore binar, fiecare nod are cel mult doi fii, numiți fiu stâng și fiu drept. Un nod poate avea zero, unul sau doi fii, iar poziția fiului face parte din structură: un fiu unic aflat la stânga dă alt arbore decât același fiu aflat la dreapta. Subarborele stâng și subarborele drept sunt tot arbori binari, eventual goi.

Parcurgerile uzuale sunt preordine (nod, stânga, dreapta), inordine (stânga, nod, dreapta) și postordine (stânga, dreapta, nod). Pentru arborele cu rădăcina 5 și fiii 2, 8, rezultatele sunt 5, 2, 8; 2, 5, 8; respectiv 2, 8, 5. Dacă un fiu lipsește, subarborele său este gol și nu produce valori.

Exemplul 1 — reprezentarea cu legături și cele trei parcurgeri. Fiecare nod memorează valoarea și doi pointeri, stang și drept; un fiu lipsă este nullptr, astfel încât diferența dintre stânga și dreapta se păstrează explicit. Arborele are rădăcina 5, fiii 2 și 8, nodul 2 are fiii 1 și 4, iar nodul 8 are numai fiul drept 9:

#include <iostream>
using namespace std;
struct Nod { int v; Nod *stang, *drept; };
void preordine(Nod* p) {
    if (!p) return;
    cout << p->v << " ";
    preordine(p->stang);
    preordine(p->drept);
}
void inordine(Nod* p) {
    if (!p) return;
    inordine(p->stang);
    cout << p->v << " ";
    inordine(p->drept);
}
void postordine(Nod* p) {
    if (!p) return;
    postordine(p->stang);
    postordine(p->drept);
    cout << p->v << " ";
}
int main() {
    Nod n1{1, nullptr, nullptr}, n4{4, nullptr, nullptr}, n9{9, nullptr, nullptr};
    Nod n2{2, &n1, &n4}, n8{8, nullptr, &n9}, n5{5, &n2, &n8};
    preordine(&n5); cout << "\n";
    inordine(&n5); cout << "\n";
    postordine(&n5);
}

Se afișează 5 2 1 4 8 9, apoi 1 2 4 5 8 9, apoi 1 4 2 9 8 5. Cele trei parcurgeri vizitează aceleași șase noduri, în ordini diferite: ce se schimbă este momentul în care se vizitează nodul curent, înainte, între sau după cei doi subarbori. Fiecare nod este vizitat o singură dată, deci parcurgerea costă $O(n)$.

Exemplul 2 — proprietăți numerice ale aceluiași arbore. Arborele are $n=6$ noduri și deci $n-1=5$ muchii între părinți și fii. Frunzele (nodurile fără fii) sunt 1, 4 și 9, deci sunt 3. Înălțimea, măsurată în muchii pe cel mai lung lanț de la rădăcină la o frunză, este 2, de exemplu 5–2–1. Fiecare nod are două legături, în total $2n=12$, dintre care $n-1=5$ indică un fiu; celelalte $12-5=7=n+1$ sunt nullptr. Relația „$n+1$ legături nule” este adevărată pentru orice arbore binar cu $n$ noduri.

Exemplul 3 — reconstituirea din două parcurgeri. Un arbore binar cu valori distincte este determinat de preordine împreună cu inordine. Preordinea 5 2 1 4 8 9 arată că rădăcina este 5. În inordinea 1 2 4 5 8 9, valorile din stânga lui 5 (1, 2, 4) alcătuiesc subarborele stâng, iar cele din dreapta (8, 9) pe cel drept. Pentru subarborele stâng, preordinea 2 1 4 dă rădăcina 2, iar inordinea 1 2 4 așază pe 1 în stânga și pe 4 în dreapta. Pentru cel drept, preordinea 8 9 dă rădăcina 8, iar inordinea 8 9 arată că 9 este în dreapta. Postordinea este 1 4 2 9 8 5. O singură parcurgere nu determină arborele: inordinea 1 2 3 corespunde atât unui lanț care urcă spre dreapta, cât și arborelui cu rădăcina 2 și fiii 1 și 3.

Exemplu în formatul examenului. Un arbore binar are preordinea 5 2 1 4 8 9 și inordinea 1 2 4 5 8 9. Care este postordinea lui?

• a) 1 4 2 9 8 5
• b) 4 1 2 9 8 5
• c) 1 4 2 8 9 5
• d) 5 2 1 4 8 9

Răspunsul corect este a), obținut prin reconstituirea de mai sus. Varianta b) inversează fiii nodului 2, deși preordinea arată că 1 se vizitează înaintea lui 4. Varianta c) pune pe 8 înaintea lui 9, ca și cum 9 ar fi frate sau părinte al lui 8; preordinea arată însă că 8 este părintele lui 9. Varianta d) este preordinea, nu postordinea.

Greșeli frecvente

• Greșit: un nod binar trebuie să aibă exact doi fii.
  Corect: poate avea zero, unu sau doi.
• Greșit: fiul stâng și cel drept sunt interschimbabili fără a schimba arborele.
  Corect: poziția lor face parte din structură.
• Greșit: inordinea vizitează rădăcina prima.
  Corect: vizitează mai întâi subarborele stâng.

Înainte și după