Arbori

Ce este un arbore

Un arbore este un graf conex, neorientat, fara cicluri, cu n noduri si n-1 muchii.

Terminologie:

• Radacina — nodul de start (intr-un arbore cu radacina)
• Frunza — nod fara copii
• Parinte / Copil — relatia intre nod si vecinii sai
• Adancimea unui nod — distanta fata de radacina
• Inaltimea arborelui — adancimea maxima

---

Reprezentare (cu lista de adiacenta)

vector<int> copii[101];
int parinte[101] = {};

// citire arbore cu radacina:
int n; cin >> n;
for (int i = 0; i < n - 1; i++) {
    int u, v; cin >> u >> v;
    copii[u].push_back(v);
    parinte[v] = u;
}

---

Arbore binar

Fiecare nod are cel mult 2 copii: stang si drept.

struct Nod {
    int val;
    Nod *st, *dr;
    Nod(int v) : val(v), st(nullptr), dr(nullptr) {}
};

---

Parcurgeri arbore binar

Preordine (radacina - stang - drept):

void preordine(Nod* r) {
    if (!r) return;
    cout << r->val << " ";
    preordine(r->st);
    preordine(r->dr);
}

Inordine (stang - radacina - drept):

void inordine(Nod* r) {
    if (!r) return;
    inordine(r->st);
    cout << r->val << " ";
    inordine(r->dr);
}

Postordine (stang - drept - radacina):

void postordine(Nod* r) {
    if (!r) return;
    postordine(r->st);
    postordine(r->dr);
    cout << r->val << " ";
}

Inordine pe BST da elementele in ordine crescatoare.

---

Arbore binar de cautare (BST)

Proprietate: pentru orice nod x:

• toate valorile din subarborele stang < x.val
• toate valorile din subarborele drept > x.val

Inserare:

Nod* insert(Nod* r, int val) {
    if (!r) return new Nod(val);
    if (val < r->val) r->st = insert(r->st, val);
    else if (val > r->val) r->dr = insert(r->dr, val);
    return r;
}

Cautare:

bool cauta(Nod* r, int val) {
    if (!r) return false;
    if (r->val == val) return true;
    if (val < r->val) return cauta(r->st, val);
    return cauta(r->dr, val);
}

---

Inaltimea unui arbore binar

int inaltime(Nod* r) {
    if (!r) return 0;
    return 1 + max(inaltime(r->st), inaltime(r->dr));
}

---

Numararea nodurilor

int numarNoduri(Nod* r) {
    if (!r) return 0;
    return 1 + numarNoduri(r->st) + numarNoduri(r->dr);
}

---

La examen

• Preordine = radacina primul → utila pentru copiere/serializare
• Inordine = ordine crescatoare pe BST
• Postordine = radacina ultima → utila pentru stergere
• Inaltimea unui arbore binar echilibrat cu n noduri ≈ log₂(n)
• Pe un BST, cautare, inserare, stergere sunt O(h) unde h = inaltimea