Arbori la BAC: rădăcină, frunze și vectorul de tați

Arborii sunt probabil cea mai „prietenoasă” parte din grafuri la BAC Informatică: au o structură clară, un vocabular ușor de vizualizat (rădăcină, tată, fii, frunze) și o reprezentare foarte compactă, vectorul de tați. Itemii tipici îți dau un vector de tați și te întreabă care e rădăcina, câte frunze are arborele, pe ce nivel e un nod sau care sunt descendenții lui. Cu metoda de mai jos, le rezolvi în câteva minute.

Ce este un arbore

Un arbore este un graf neorientat conex și fără cicluri. Câteva proprietăți echivalente, toate utile în grile:

• un arbore cu n noduri are exact n − 1 muchii;
• între oricare două noduri există un singur lanț elementar;
• dacă elimini orice muchie, graful nu mai este conex; dacă adaugi orice muchie, apare un ciclu.

Arborele cu rădăcină: vocabularul

Când alegi un nod drept rădăcină, arborele capătă o ierarhie, ca un arbore genealogic desenat de sus în jos:

• tatăl unui nod x este vecinul lui x aflat pe lanțul spre rădăcină; rădăcina nu are tată;
• fiii lui x sunt nodurile al căror tată este x; nodurile cu același tată se numesc frați;
• frunzele sunt nodurile fără fii;
• ascendenții lui x sunt toate nodurile de pe lanțul de la x la rădăcină (tatăl, tatăl tatălui etc.); descendenții lui x sunt toate nodurile din „subarborele” lui x;
• nivelul unui nod este distanța (numărul de muchii) de la rădăcină la el; rădăcina este pe nivelul 0, iar înălțimea arborelui este nivelul maxim.

Convenția cu rădăcina pe nivelul 0 este cea uzuală, dar citește întotdeauna enunțul: dacă precizează altă numerotare a nivelurilor, o respecți pe aceea.

Vectorul de tați

Un arbore cu rădăcină și n noduri se poate memora într-un singur vector t cu n elemente, unde t[i] este tatăl nodului i, iar pentru rădăcină t[i] = 0. Exemplu, pentru n = 8:

Hai să citim informațiile, una câte una.

Rădăcina

Este nodul cu t[i] = 0: nodul 3. Într-un vector de tați corect există exact o valoare 0.

Fiii unui nod

Fiii lui x sunt pozițiile pe care apare valoarea x. Valoarea 3 apare pe pozițiile 1 și 2, deci fiii lui 3 sunt 1 și 2. Valoarea 1 apare pe pozițiile 4 și 5, valoarea 2 pe poziția 6, valoarea 4 pe pozițiile 7 și 8. Numărul de fii ai lui x este numărul de apariții ale lui x în vector.

Frunzele

Frunzele sunt nodurile care nu apar deloc ca valori în vector, adică nu sunt tatăl nimănui. Valorile care apar sunt 3, 1, 2, 4, deci frunzele sunt 5, 6, 7, 8.

Nivelurile

Pentru un nod, urci din tată în tată până la rădăcină și numeri pașii. Pentru nodul 7: 7 → 4 → 1 → 3, adică 3 pași, deci nivelul 3. Complet:

• nivelul 0: 3
• nivelul 1: 1, 2
• nivelul 2: 4, 5, 6
• nivelul 3: 7, 8

Înălțimea arborelui este 3.

Ascendenți și descendenți

Ascendenții lui 7 se obțin urcând: 4, 1, 3. Descendenții lui 1 sunt fiii lui (4, 5), apoi fiii fiilor (7, 8): în total 4, 5, 7, 8.

Lanțul dintre două noduri

Pentru lanțul dintre două noduri, urci din amândouă spre rădăcină până la primul nod comun. Pentru 7 și 6: din 7 urci prin 4, 1, 3; din 6 urci prin 2, 3. Primul nod comun este 3, deci lanțul este 7, 4, 1, 3, 2, 6, de lungime 5.

Aceeași muchii, altă rădăcină

Vectorul de tați depinde de rădăcina aleasă. Arborele din exemplu are muchiile [1,3], [2,3], [1,4], [1,5], [2,6], [4,7], [4,8]. Dacă alegi ca rădăcină nodul 1, tatăl lui 3 devine 1, iar tatăl lui 2 rămâne 3:

Mulțimea frunzelor (5, 6, 7, 8) rămâne aceeași aici, dar nivelurile se schimbă: acum nodul 6 este pe nivelul 3. În general, dacă rădăcina nouă era frunză, ea nu mai e frunză în arborele nou, așa că și frunzele se pot schimba. Grilele cu „care ar fi vectorul de tați dacă rădăcina ar fi nodul x” testează exact acest lucru: muchiile rămân, sensul „spre rădăcină” se schimbă doar pe lanțul dintre rădăcina veche și cea nouă.

Prelucrarea vectorului de tați în C++

Programul citește n și vectorul de tați, afișează frunzele și calculează înălțimea arborelui:

#include <iostream>
using namespace std;

int n, t[101], fii[101];

int nivel(int x)
{
    int niv = 0;
    while (t[x] != 0)      // urcăm până la rădăcină
    {
        x = t[x];
        niv++;
    }
    return niv;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
        if (t[i] != 0)
            fii[t[i]]++;   // t[i] mai are un fiu
    }
    cout << "Frunze: ";
    for (int i = 1; i <= n; i++)
        if (fii[i] == 0)
            cout << i << ' ';
    cout << '\n';
    int h = 0;
    for (int i = 1; i <= n; i++)
        if (nivel(i) > h)
            h = nivel(i);
    cout << "Inaltime: " << h;
    return 0;
}

Pentru datele 8 și 3 3 0 1 1 2 4 4, programul afișează Frunze: 5 6 7 8 și apoi Inaltime: 3. Observă că vectorul fii este de fapt un vector de frecvență pentru valorile din t, aceeași tehnică pe care o folosești la tablouri.