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:

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:

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:

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 se deplasează spre rădăcină, iar listele de fii pentru cele care se deplasează spre frunze. Denumirile se folosesc uneori invers: vectorul de tați este numit și „implementare prin referințe descendente”. Programa școlară din 2009, citată în subiectul de Titularizare 2026, folosește 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 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 trece din y
   din tata in tata 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 trece din nod în tatăl lui cu ajutorul vectorului 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 trece din y din tată în tată. 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:

Denumirile nu sunt aceleași la toți autorii. Denumirea „arbore binar complet” este folosită uneori pentru arborele în care fiecare nod intern are exact doi fii, adică pentru 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;
}