1
1. Definitia arborelui si proprietatile sale
Un arbore este un graf neorientat conex si aciclic. Echivalent, un arbore cu n noduri are exact n-1 muchii.
Proprietatile esentiale ale unui arbore:
- Conexitate: intre oricare doua noduri exista exact un lant
- Aciclic: nu contine cicluri (nu exista lant de la un nod la el insusi)
- n noduri => n-1 muchii (proprietate numerica definitorie)
- Eliminarea oricarei muchii deconecteaza arborele in doua componente
- Adaugarea oricarei muchii creeaza exact un ciclu
Verificare in Python — conditia n-1 muchii:
# Un arbore cu n noduri are exact n-1 muchii n_noduri = 5 muchii = [(1,2), (1,3), (2,4), (2,5)] print(f"Graf cu {n_noduri} noduri si {len(muchii)} muchii:") print(f" Este arbore? {len(muchii) == n_noduri - 1}") print(f" Proprietate: n={n_noduri} noduri => n-1={n_noduri-1} muchii (exact {len(muchii)})")
Output real (rulat cu python):
Graf cu 5 noduri si 4 muchii: Este arbore? True Proprietate: n=5 noduri => n-1=4 muchii (exact 4)
Reprezentare vizuala — arbore cu 6 noduri:
1 <-- radacina (nivel 0)
/ \
2 3 <-- nivel 1
/ \ \
4 5 6 <-- nivel 2 (frunze)
Noduri: 6 Muchii: 5 = 6-1 ✓
2
2. Terminologia arborelui cu radacina
Un arbore cu radacina (rooted tree) este un arbore in care un nod special — radacina — defineste ierarhia. Toate muchiile devin orientate implicit: dinspre parinte spre fii.
Termeni esentiali (cu exemplu pe arborele de mai jos):
1 Radacina = 1
/ \
2 3 Parinte(2)=1, Parinte(3)=1, Parinte(6)=3
/ \ \
4 5 6 Frunze = {4, 5, 6} (grad 1, fara fii)
Nivel(1)=0, Nivel(2)=Nivel(3)=1, Nivel(4)=Nivel(5)=Nivel(6)=2
Inaltime arbore = max nivel frunza = 2
Subarbore(2) = nodul 2 impreuna cu 4 si 5
Tabel de terminologie:
Termen | Definitie --------------+------------------------------------------ Radacina | Nodul fara parinte (nivelul 0) Parinte | Nodul direct superior in ierarhie Fiu (copil) | Nod direct inferior unui parinte Frunza | Nod fara fii (nod terminal) Nod intern | Nod cu cel putin un fiu (non-frunza) Nivel | Distanta (nr. muchii) de la radacina Inaltime (h) | Nivelul maxim al unei frunze Subarbore | Un nod + toti descendentii sai Adancime nod | Nivelul nodului (sinonim cu nivel)
Calcul nivel si parinte (Python):
# BFS pe arbore pentru nivel si parinte from collections import deque adj = {1:[2,3], 2:[1,4,5], 3:[1,6], 4:[2], 5:[2], 6:[3]} nivel = {1: 0} parinte = {1: "radacina"} coada = deque([1]) vizitat = {1} while coada: nod = coada.popleft() for vecin in adj[nod]: if vecin not in vizitat: vizitat.add(vecin) nivel[vecin] = nivel[nod] + 1 parinte[vecin] = nod coada.append(vecin) for nod in range(1, 7): print(f" Nod {nod}: nivel={nivel[nod]}, parinte={parinte[nod]}")
Output real (rulat cu python):
Nod 1: nivel=0, parinte=radacina Nod 2: nivel=1, parinte=1 Nod 3: nivel=1, parinte=1 Nod 4: nivel=2, parinte=2 Nod 5: nivel=2, parinte=2 Nod 6: nivel=2, parinte=3
3
3. Parcurgerea arborelui — DFS si BFS
Algoritmii de parcurgere a grafurilor (DFS si BFS) se aplica direct pe arbori. Pe un arbore, DFS genereaza o parcurgere in adancime (ramura completa inainte de alta ramura), iar BFS genereaza o parcurgere nivel cu nivel.
DFS pe arbore (Python) — O(n+m) = O(n):
# DFS recursiv pe arbore def dfs_arbore(adj, nod, vizitat, ordine): vizitat[nod] = True ordine.append(nod) for vecin in sorted(adj.get(nod, [])): if not vizitat[vecin]: dfs_arbore(adj, vecin, vizitat, ordine) adj = {1:[2,3], 2:[1,4,5], 3:[1,6], 4:[2], 5:[2], 6:[3]} vizitat = [False] * 7 ordine = [] dfs_arbore(adj, 1, vizitat, ordine) print(f"DFS pe arbore (radacina=1):") print(f"Ordine vizitare: {ordine}") print(f"Toate 6 noduri vizitate: {all(vizitat[1:])}")
Output real (rulat cu python):
DFS pe arbore (radacina=1): Ordine vizitare: [1, 2, 4, 5, 3, 6] Toate 6 noduri vizitate: True
Comparatie DFS vs BFS pe acelasi arbore:
Arbore: 1 - 2 - 4
| \- 5
\- 3 - 6
DFS (adancime): 1, 2, 4, 5, 3, 6 (ramura stanga completa, apoi dreapta)
BFS (latime): 1, 2, 3, 4, 5, 6 (nivel 0, nivel 1, nivel 2)
Pe un arbore, BFS = parcurgere pe niveluri (level-order traversal)
Pe un arbore, DFS = parcurgere preordine (R-S-D) daca vecinii sunt sortati
4
4. Arborele binar si parcurgerile sale
Un arbore binar este un arbore cu radacina in care fiecare nod are cel mult doi fii: fiul stang si fiul drept. Un Arbore Binar de Cautare (BST) adauga proprietatea: valorile din subarborele stang < radacina < valorile din subarborele drept.
Cele trei parcurgeri ale arborelui binar:
Cele trei parcurgeri:
Inordine (S-R-D): Stang -> Radacina -> Drept
Preordine (R-S-D): Radacina -> Stang -> Drept
Postordine (S-D-R): Stang -> Drept -> Radacina
BST cu valorile 5, 3, 7, 1, 4, 6, 8:
5
/ \
3 7
/ \ / \
1 4 6 8
Inordine: 1, 3, 4, 5, 6, 7, 8 (sortat crescator!)
Preordine: 5, 3, 1, 4, 7, 6, 8 (radacina prima)
Postordine: 1, 4, 3, 6, 8, 7, 5 (radacina ultima)
Implementare BST in Python — inserare si parcurgeri:
class Nod: def __init__(self, val): self.val = val self.stang = None self.drept = None def insereaza(radacina, val): if radacina is None: return Nod(val) if val < radacina.val: radacina.stang = insereaza(radacina.stang, val) else: radacina.drept = insereaza(radacina.drept, val) return radacina def inordine(nod, rezultat): if nod is None: return inordine(nod.stang, rezultat) rezultat.append(nod.val) inordine(nod.drept, rezultat) def preordine(nod, rezultat): if nod is None: return rezultat.append(nod.val) preordine(nod.stang, rezultat) preordine(nod.drept, rezultat) def postordine(nod, rezultat): if nod is None: return postordine(nod.stang, rezultat) postordine(nod.drept, rezultat) rezultat.append(nod.val) valori = [5, 3, 7, 1, 4, 6, 8] radacina = None for v in valori: radacina = insereaza(radacina, v) rez_in, rez_pre, rez_post = [], [], [] inordine(radacina, rez_in) preordine(radacina, rez_pre) postordine(radacina, rez_post) print(f"Arbore Binar de Cautare (BST) cu valorile: {valori}") print(f"Parcurgere inordine (S-R-D): {rez_in}") print(f"Parcurgere preordine (R-S-D): {rez_pre}") print(f"Parcurgere postordine(S-D-R): {rez_post}") print(f"Observatie: inordine produce valorile sortate crescator!")
Output real (rulat cu python):
Arbore Binar de Cautare (BST) cu valorile: [5, 3, 7, 1, 4, 6, 8] Parcurgere inordine (S-R-D): [1, 3, 4, 5, 6, 7, 8] Parcurgere preordine (R-S-D): [5, 3, 1, 4, 7, 6, 8] Parcurgere postordine(S-D-R): [1, 4, 3, 6, 8, 7, 5] Observatie: inordine produce valorile sortate crescator!
5
5. Inaltimea arborelui binar si calcul recursiv
Inaltimea unui arbore binar este lungimea celui mai lung lant de la radacina la o frunza. Un arbore cu un singur nod are inaltimea 0. Arborele vid are inaltimea -1 (conventie frecventa in informatica).
Calcul recursiv al inaltimii, numarului de noduri si frunze (Python):
def inaltime(nod): if nod is None: return -1 # conventie: arborele vid return 1 + max(inaltime(nod.stang), inaltime(nod.drept)) def nr_noduri(nod): if nod is None: return 0 return 1 + nr_noduri(nod.stang) + nr_noduri(nod.drept) def nr_frunze(nod): if nod is None: return 0 if nod.stang is None and nod.drept is None: return 1 return nr_frunze(nod.stang) + nr_frunze(nod.drept) # BST cu valorile 5, 3, 7, 1, 4, 6, 8 (construit anterior) h = inaltime(radacina) n = nr_noduri(radacina) f = nr_frunze(radacina) print(f"BST cu valorile {valori}:") print(f" Inaltime h = {h}") print(f" Numar noduri n = {n}") print(f" Numar frunze = {f}") print(f" Numar noduri interne = {n - f}")
Output real (rulat cu python):
BST cu valorile [5, 3, 7, 1, 4, 6, 8]: Inaltime h = 2 Numar noduri n = 7 Numar frunze = 4 Numar noduri interne = 3
Relatii importante pentru arbori binari (de memorat):
Arbore binar cu inaltime h: - Are MINIM h+1 noduri (lant - arbore degenerat) - Are MAXIM 2^(h+1) - 1 noduri (arbore complet) Arbore binar COMPLET cu n noduri: - Inaltime h = floor(log2(n)) - Ex: n=7 => h=2, n=15 => h=3, n=31 => h=4 Numar frunze = numar noduri interne + 1 (valabila pentru arbori binari COMPETI cu toti fiii)
6
6. Arbore binar in C++ EXCLUSIV INTENSIV
⚡ Sectiune exclusiv pentru profil intensiv informatica
La profilul intensiv vei implementa BST cu alocare dinamica (new/delete) si pointeri. Parcurgerile sunt identice ca logica cu Python, dar sintaxa C++ impune declararea explicita a tipurilor si gestionarea memoriei.
#include <iostream> using namespace std; struct Nod { int val; Nod* stang; Nod* drept; Nod(int v): val(v), stang(nullptr), drept(nullptr) {} }; Nod* insereaza(Nod* radacina, int val) { if (!radacina) return new Nod(val); if (val < radacina->val) radacina->stang = insereaza(radacina->stang, val); else radacina->drept = insereaza(radacina->drept, val); return radacina; } void inordine(Nod* nod) { if (!nod) return; inordine(nod->stang); cout << nod->val << " "; inordine(nod->drept); } int inaltime(Nod* nod) { if (!nod) return -1; return 1 + max(inaltime(nod->stang), inaltime(nod->drept)); } int main() { int valori[] = {5, 3, 7, 1, 4, 6, 8}; Nod* radacina = nullptr; for (int v : valori) radacina = insereaza(radacina, v); cout << "BST cu valorile: 5 3 7 1 4 6 8" << endl; cout << "Parcurgere inordine: "; inordine(radacina); cout << endl; cout << "Inaltime: " << inaltime(radacina) << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
BST cu valorile: 5 3 7 1 4 6 8 Parcurgere inordine: 1 3 4 5 6 7 8 Inaltime: 2
Diferente C++ fata de Python:
Python C++ (intensiv)
--------------------------+---------------------------
class Nod: struct Nod {
self.stang = None Nod* stang = nullptr;
}
(garbage collector) delete nod; // manual
radacina.stang radacina->stang
return Nod(val) return new Nod(val)