Arbori: terminologie și reprezentare

Ce este un arbore

Un arbore e un graf conex și fără cicluri.

Proprietatea fundamentală: un arbore cu $n$ noduri are exact $n - 1$ muchii. Între oricare două noduri există un singur lanț elementar.

Terminologie (arbore cu rădăcină)

• Rădăcină: nodul de pornire, ales convențional.
• Descendent: orice nod aflat mai jos pe ramură.
• Descendent direct (fiu): nodul legat imediat dedesubt.
• Ascendent: orice nod aflat mai sus pe drumul spre rădăcină.
• Ascendent direct (părinte/tată): nodul legat imediat deasupra.
• Frați: noduri cu același părinte.
• Nod terminal (frunză): nod fără descendenți.

Rădăcina e singurul nod fără părinte.

Metodele de reprezentare cerute de programă

1. Matricea de adiacență

Ca la orice graf. Simplă, dar ocupă $n^2$ memorie.

2. Liste „de descendenți"

Pentru fiecare nod, lista fiilor lui.

3. Vectorul „de tați"

Cel mai economic și cel mai des cerut la BAC. $t[i]$ = părintele nodului $i$, iar pentru rădăcină $t[i] = 0$.

Exemplu: t = [0, 1, 1, 2, 2] pentru 5 noduri înseamnă:

• nodul 1 e rădăcina (t[1] = 0);
• nodurile 2 și 3 au părintele 1;
• nodurile 4 și 5 au părintele 2;
• frunzele sunt 3, 4 și 5.

Din vectorul de tați poți afla imediat:

• rădăcina: singurul $i$ cu $t[i] = 0$;
• frunzele: nodurile care nu apar în vector;
• drumul spre rădăcină: urci din tată în tată.

Greșeli frecvente

1. Se spune că un arbore cu $n$ noduri are $n$ muchii. Are $n - 1$.
2. Se confundă descendentul direct (fiul) cu orice descendent.
3. În vectorul de tați se caută frunzele printre valori. Frunzele sunt nodurile care nu apar ca valoare.

#include <iostream>
using namespace std;

int main() {
    int n, t[101], esteTata[101] = {0};
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        if (t[i] != 0) esteTata[t[i]] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (t[i] == 0) cout << "radacina=" << i << " ";

    cout << "frunze:";
    for (int i = 1; i <= n; i++)
        if (!esteTata[i]) cout << " " << i;
    return 0;
}