# Arbori: terminologie și reprezentare

> Pagina: https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori/arbori-reprezentare
> Markdown: https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori/arbori-reprezentare.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Grafuri orientate și arbori](https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori)
Actualizat: 2026-09-22

Rădăcină, descendenți, ascendenți, frunze, și cele trei metode de 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ă.

> [!RETINE]
> 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

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.