Capitolul 17 · Lecția 17.2 din 2

Arbori: terminologie și reprezentare

Rădăcină, descendenți, ascendenți, frunze, și cele trei metode de reprezentare.

Capitolul 17: Grafuri orientate și arbori

Pe această pagină4 secțiuni

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ă.

Reține

Vectorul de tați e formatul preferat la examen pentru că e compact. Exercițiul-tip: „dat vectorul de tați, precizați rădăcina, frunzele și înălțimea arborelui."

Greșeli frecvente

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

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#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;
}

Date de intrarese trimit programului la citire

Instrumente pentru lecția asta

Laborator de grafuri

Construiește graful apăsând pe noduri și vezi pe loc matricea de adiacență, listele, gradele și parcurgerile.

Numărul de noduri

Apasă un nod, apoi altul, ca să adaugi sau să scoți muchia dintre ele.

Noduri: 6
Muchii: 5
Suma gradelor: 10
Componente conexe: 2
Conex: nu
Complet: nu

Suma gradelor e 10, adică dublul celor 5 muchii. Nu e o coincidență: fiecare muchie adaugă câte 1 la gradul ambelor capete.

	0	1	2	3	4	5
0	0	1	0	1	0	0
1	1	0	1	0	0	0
2	0	1	0	1	0	0
3	1	0	1	0	0	0
4	0	0	0	0	0	1
5	0	0	0	0	1	0

Explorează interactiv

Se încarcă instrumentul…

Bifează când ai terminat, ca s-o vezi citită pe toate dispozitivele.

Testează-te pe capitolul 17

Lecția în clipuri

Clipuri scurte, cu voce și subtitrări.