Arbori cu rădăcină și arbori binari

Structura directoarelor de pe un disc, organigrama unei firme și arborele genealogic al unei familii au în comun o ierarhie: fiecare element, în afară de unul singur, este subordonat direct unui alt element. Modelul lor este arborele cu rădăcină. Când fiecare element are cel mult doi subordonați, ale căror poziții se deosebesc, modelul este arborele binar.

Lecția prezintă:

• arborele cu rădăcină, terminologia și reprezentările lui;
• arborele binar, tipurile speciale de arbori binari, proprietățile și parcurgerile lor;
• arborele binar de căutare;
• ansamblul heap și operațiile lui.

Implementarea dinamică a arborilor binari și a arborilor binari de căutare, cu toate operațiile, este prezentată în subcapitolul Structuri de date implementate dinamic. Aici se folosește implementarea statică, cu vectori.

Noțiuni preliminare

Arborii cu rădăcină se definesc pornind de la arbore:

• un arbore este un graf neorientat conex și fără cicluri; un arbore cu n noduri are n − 1 muchii;
• între oricare două noduri ale unui arbore există un singur lanț elementar;
• un nod terminal are gradul 1.

Arborii și proprietățile lor sunt prezentați în subcapitolul Arbori. Arbori parțiali de cost minim.

Arborele cu rădăcină

Definiție și terminologie

Se mai folosesc termenii:

• ordinul unui nod este numărul fiilor lui; nodul 2 are ordinul 2, nodul 3 ordinul 1;
• nivelul unui nod este numărul muchiilor de pe lanțul de la rădăcină la el; rădăcina este pe nivelul 0, iar nodul 7 pe nivelul 3;
• înălțimea arborelui este cel mai mare nivel al unui nod; arborele din desen are înălțimea 3;
• subarborele unui nod este format din nodul respectiv și din toți descendenții lui; subarborele nodului 2 are nodurile 2, 4, 5 și 7.

Arborele cu rădăcină are și o definiție recursivă: un arbore cu rădăcină este format din rădăcină și din zero, unul sau mai mulți arbori cu rădăcină, numiți subarbori, legați de ea. Rădăcinile subarborilor sunt fiii rădăcinii. Doi subarbori ai aceluiași arbore fie nu au noduri comune, fie unul este inclus în celălalt.

Reprezentarea arborilor cu rădăcină

Arborele cu rădăcină se poate memora ca orice graf, cu matricea de adiacență, dar reprezentările specifice folosesc legătura dintre tată și fii:

• reprezentarea cu referințe ascendente (vectorul de tați): pentru fiecare nod i se reține în t[i] eticheta tatălui lui; pentru rădăcină t[i] = 0;
• reprezentarea cu referințe descendente: pentru fiecare nod se rețin fiii lui, de exemplu într-o listă a fiilor.

Pentru arborele cu rădăcina 1:

Din vectorul de tați se obțin:

• rădăcina — nodul i cu t[i] = 0;
• tatăl nodului x — valoarea t[x], într-un singur pas;
• fiii nodului x — nodurile i cu t[i] = x, printr-o parcurgere a vectorului;
• frunzele — nodurile care nu apar ca valori în vectorul t;
• frații nodului x — nodurile i ≠ x cu t[i] = t[x];
• nivelul nodului x — numărul de pași x ← t[x] până la rădăcină.

Vectorul de tați este potrivit pentru operațiile care urcă spre rădăcină, iar listele de fii pentru cele care coboară spre frunze. Manualul EDP folosește denumirile invers: numește vectorul tată „implementare prin referințe descendente”. Programa școlară din 2009, citată în subiectul de Titularizare 2026, și rezolvarea de pe site folosesc denumirile din tabelul de mai sus.

Operații cu vectorul de tați

#include <iostream>
using namespace std;

const int MAX = 101;
int t[MAX], stramos[MAX], n;

void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i];
}

/* Nivelul nodului x este numarul de pasi facuti urcand din x,
   din tata in tata, pana la radacina. */
int nivel(int x) {
    int k = 0;
    while (t[x] != 0) {
        x = t[x];
        k++;
    }
    return k;
}

/* Pentru fiecare nod: tatal, nivelul si fiii, adica nodurile i cu t[i]
   egal cu nodul respectiv. Nodul fara fii este frunza. */
void afisare() {
    int h = 0;
    for (int x = 1; x <= n; x++) {
        cout << "nodul " << x << ": tata " << t[x] << ", nivel " << nivel(x) << ", fii:";
        int nrFii = 0;
        for (int i = 1; i <= n; i++)
            if (t[i] == x) {
                cout << " " << i;
                nrFii++;
            }
        if (nrFii == 0)
            cout << " - (frunza)";
        cout << "\n";
        if (nivel(x) > h)
            h = nivel(x);
    }
    cout << "Inaltimea arborelui: " << h << "\n";
}

/* Se marcheaza stramosii lui x, inclusiv x, apoi se urca din y
   pana la primul nod marcat. */
int stramosComun(int x, int y) {
    for (int k = x; k != 0; k = t[k])
        stramos[k] = 1;
    int k = y;
    while (k != 0 && stramos[k] == 0)
        k = t[k];
    return k;
}

int main() {
    int x, y;
    citire();
    afisare();
    cin >> x >> y;
    cout << "Primul stramos comun al nodurilor " << x << " si " << y << ": "
         << stramosComun(x, y) << "\n";
    return 0;
}

Pentru datele 7, 0 1 1 2 2 3 5 și nodurile 4 7 programul afișează:

nodul 1: tata 0, nivel 0, fii: 2 3
nodul 2: tata 1, nivel 1, fii: 4 5
nodul 3: tata 1, nivel 1, fii: 6
nodul 4: tata 2, nivel 2, fii: - (frunza)
nodul 5: tata 2, nivel 2, fii: 7
nodul 6: tata 3, nivel 2, fii: - (frunza)
nodul 7: tata 5, nivel 3, fii: - (frunza)
Inaltimea arborelui: 3
Primul stramos comun al nodurilor 4 si 7: 2

Descrierea soluției. Subprogramul nivel urcă din nod în nod folosind vectorul t și numără pașii. Subprogramul afisare caută, pentru fiecare nod x, indicii i cu t[i] = x, care sunt fiii lui, și reține cel mai mare nivel, adică înălțimea. Subprogramul stramosComun marchează în vectorul stramos drumul de la x la rădăcină, apoi urcă din y. Afișarea fiilor tuturor nodurilor cere O(n²) pași, iar nivelul și strămoșul comun cer câte O(h) pași, unde h este înălțimea.

Operațiile se pot urmări pas cu pas în simulatorul arborelui cu rădăcină, pe același arbore.

Construirea vectorului de tați și parcurgerile

Un arbore dat prin muchii devine arbore cu rădăcină după alegerea rădăcinii r. Parcurgerea în adâncime din r ajunge în fiecare nod j dintr-un nod x, iar x este tatăl lui j.

Arborele cu rădăcină se parcurge astfel:

• în preordine — se prelucrează rădăcina, apoi se parcurg, pe rând, subarborii fiilor ei;
• în postordine — se parcurg subarborii fiilor, apoi se prelucrează rădăcina;
• pe niveluri (în lățime) — se prelucrează rădăcina, apoi nodurile de pe nivelul 1, apoi cele de pe nivelul 2 și așa mai departe, cu ajutorul unei cozi.

Enunț. Se citesc numărul de noduri n, rădăcina r și cele n − 1 muchii ale unui arbore. Să se construiască vectorul de tați și să se afișeze parcurgerile în preordine, în postordine și pe niveluri. Fiii unui nod se iau în ordinea crescătoare a etichetelor.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], t[MAX], viz[MAX], coada[MAX], n, r;

/* Se citesc n, radacina r si cele n - 1 muchii ale arborelui. */
void citire() {
    int x, y;
    cin >> n >> r;
    for (int k = 1; k < n; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in adancime din radacina: nodul j atins din nodul x
   are tatal x. */
void construiesteTati(int x) {
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && viz[j] == 0) {
            t[j] = x;
            construiesteTati(j);
        }
}

/* Nodul x, apoi subarborii fiilor lui, luati in ordinea etichetelor. */
void preordine(int x) {
    cout << x << " ";
    for (int j = 1; j <= n; j++)
        if (t[j] == x)
            preordine(j);
}

/* Subarborii fiilor lui x, apoi nodul x. */
void postordine(int x) {
    for (int j = 1; j <= n; j++)
        if (t[j] == x)
            postordine(j);
    cout << x << " ";
}

/* Pe niveluri: in coada intra, pe rand, fiii nodului din capul cozii. */
void niveluri() {
    int p = 1, u = 1;
    coada[1] = r;
    while (p <= u) {
        for (int j = 1; j <= n; j++)
            if (t[j] == coada[p]) {
                u++;
                coada[u] = j;
            }
        p++;
    }
    for (int i = 1; i <= u; i++)
        cout << coada[i] << " ";
}

int main() {
    citire();
    construiesteTati(r);
    cout << "Vectorul de tati:";
    for (int i = 1; i <= n; i++)
        cout << " " << t[i];
    cout << "\nPreordine: ";
    preordine(r);
    cout << "\nPostordine: ";
    postordine(r);
    cout << "\nPe niveluri: ";
    niveluri();
    cout << "\n";
    return 0;
}

Pentru arborele din desen, cu muchiile [1,2], [1,3], [2,4], [2,5], [3,6], [5,7], programul afișează:

Descrierea soluției. Subprogramul construiesteTati este parcurgerea în adâncime din subcapitolul Parcurgerea grafurilor, în care nodul nevizitat j primește tatăl x. Subprogramele preordine și postordine se autoapelează pentru fiecare fiu, adică pentru fiecare j cu t[j] = x, înainte sau după afișarea nodului. Subprogramul niveluri pune în coadă fiii nodului din capul cozii. Căutarea fiilor în vectorul de tați face ca fiecare parcurgere să ceară O(n²) pași.

Arborele binar

Definiție

Tipuri speciale de arbori binari

Se definesc următoarele tipuri de arbori binari:

• arborele binar strict — fiecare nod are 0 sau 2 fii;
• arborele binar complet — este strict și are toate frunzele pe același nivel; fiecare nivel k, până la ultimul, are 2ᵏ noduri;
• arborele binar aproape complet — toate nivelurile, cu excepția ultimului, sunt complete, iar nodurile de pe ultimul nivel sunt așezate cât mai la stânga;
• arborele binar degenerat — fiecare nod are cel mult un fiu, iar înălțimea este n − 1.

Manualele nu folosesc aceleași denumiri. Manualul EDP definește tipurile ca mai sus. Manualul Niculescu numește „arbore binar complet” arborele în care fiecare nod intern are exact doi fii, adică arborele strict de mai sus. La examen se scrie definiția folosită, nu doar denumirea.

Proprietăți ale arborilor binari

• Pe nivelul k al unui arbore binar se află cel mult 2ᵏ noduri, fiindcă fiecare nod de pe nivelul k − 1 are cel mult doi fii.
• Un arbore binar cu înălțimea h are cel mult 1 + 2 + … + 2ʰ = 2ʰ⁺¹ − 1 noduri. Prin urmare, un arbore binar cu n noduri are înălțimea cel puțin [log₂ n] și cel mult n − 1.
• Un arbore binar complet cu înălțimea h are 2ʰ frunze și 2ʰ⁺¹ − 1 noduri.
• Într-un arbore binar nevid, numărul frunzelor este cu 1 mai mare decât numărul nodurilor cu doi fii. Dacă n₀, n₁, n₂ sunt numerele de noduri cu 0, 1 și 2 fii, numărul muchiilor se scrie în două feluri: n − 1 = n₀ + n₁ + n₂ − 1 și n₁ + 2n₂, câte o muchie spre fiecare fiu. Rezultă n₀ = n₂ + 1.
• Un arbore binar strict cu f frunze are f − 1 noduri interne, deci 2f − 1 noduri, un număr impar.

Pentru arborele binar din desen, n₂ = 2 (nodurile 1 și 2) și n₀ = 3 (nodurile 4, 5, 7).

Reprezentarea arborilor binari

Arborele binar se reprezintă static prin:

• vectorii st și dr — st[i] și dr[i] sunt etichetele fiului stâng și fiului drept ale nodului i, sau 0 dacă fiul lipsește; informația din nod se reține în vectorul info;
• vectorii tata și fiu — tata[i] este tatăl nodului i, iar fiu[i] este −1 dacă i este fiul stâng și 1 dacă este fiul drept; pentru rădăcină ambele valori sunt 0;
• un singur vector, pentru arborii aproape compleți — nodurile se numerotează pe niveluri, de la stânga la dreapta, începând cu 1; nodul de pe poziția i are fiul stâng pe poziția 2i, fiul drept pe poziția 2i + 1 și tatăl pe poziția [i/2].

Pentru arborele binar din desen:

Rădăcina este singurul nod care nu apare în vectorii st și dr, iar frunzele sunt nodurile cu st[i] = dr[i] = 0. Implementarea dinamică, cu un câmp info și adresele celor doi subarbori, este prezentată în subcapitolul despre structurile implementate dinamic.

Parcurgerea arborilor binari

Arborele binar se parcurge pe niveluri, ca orice arbore cu rădăcină, sau în adâncime. Parcurgerile în adâncime diferă prin momentul în care se prelucrează rădăcina; subarborele stâng se parcurge înaintea celui drept:

Parcurgerile se pot urmări pas cu pas, cu stiva apelurilor recursive, în simulatorul parcurgerilor de arbore binar, pe același arbore.

Enunț. Se citește un arbore binar cu n noduri: pentru fiecare nod, informația, fiul stâng și fiul drept. Să se afișeze rădăcina, parcurgerile RSD, SRD și SDR, înălțimea, numărul frunzelor și dacă arborele este arbore binar de căutare.

#include <iostream>
using namespace std;

const int MAX = 101;
int info[MAX], st[MAX], dr[MAX], n, ultim, ordonat;

/* Pentru fiecare nod i se citesc informatia, fiul stang si fiul drept;
   0 inseamna ca fiul lipseste. */
void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> info[i] >> st[i] >> dr[i];
}

/* Radacina este singurul nod care nu este fiul niciunui nod. */
int radacina() {
    int esteFiu[MAX] = {0};
    for (int i = 1; i <= n; i++)
        esteFiu[st[i]] = esteFiu[dr[i]] = 1;
    for (int i = 1; i <= n; i++)
        if (esteFiu[i] == 0)
            return i;
    return 0;
}

void Preordine(int i) {
    cout << info[i] << " ";
    if (st[i] != 0) Preordine(st[i]);
    if (dr[i] != 0) Preordine(dr[i]);
}

void Inordine(int i) {
    if (st[i] != 0) Inordine(st[i]);
    cout << info[i] << " ";
    if (dr[i] != 0) Inordine(dr[i]);
}

void Postordine(int i) {
    if (st[i] != 0) Postordine(st[i]);
    if (dr[i] != 0) Postordine(dr[i]);
    cout << info[i] << " ";
}

/* Inaltimea subarborelui cu radacina i; subarborele vid are inaltimea -1. */
int inaltime(int i) {
    if (i == 0)
        return -1;
    int hs = inaltime(st[i]), hd = inaltime(dr[i]);
    return 1 + (hs > hd ? hs : hd);
}

int frunze(int i) {
    if (i == 0)
        return 0;
    if (st[i] == 0 && dr[i] == 0)
        return 1;
    return frunze(st[i]) + frunze(dr[i]);
}

/* Parcurgerea SRD compara fiecare informatie cu cea afisata inainte:
   arborele este de cautare daca sirul obtinut este strict crescator. */
void verificaCautare(int i) {
    if (st[i] != 0) verificaCautare(st[i]);
    if (ultim != 0 && info[i] <= info[ultim])
        ordonat = 0;
    ultim = i;
    if (dr[i] != 0) verificaCautare(dr[i]);
}

int main() {
    citire();
    int r = radacina();
    cout << "Radacina: " << info[r] << "\nRSD: ";
    Preordine(r);
    cout << "\nSRD: ";
    Inordine(r);
    cout << "\nSDR: ";
    Postordine(r);
    cout << "\nInaltimea: " << inaltime(r) << ", frunze: " << frunze(r) << "\n";
    ordonat = 1;
    verificaCautare(r);
    cout << (ordonat ? "Este" : "Nu este") << " arbore binar de cautare\n";
    return 0;
}