Modul 09 — Arbori cu rădăcină

Un graf special — definiții echivalente

Arborele e un graf neorientat care poate fi descris în mai multe feluri — toate spun ACELAȘI lucru (întrebare favorită la BAC!).

conex + fără cicluri

Definiția „oficială". Exact ce a construit Prim în M08 — arborele parțial!

conex + n−1 muchii

Minimul de muchii care ține totul legat — una în minus și se rupe, una în plus și apare ciclu.

exact UN lanț între oricare două noduri

Fără cicluri = fără rute alternative: drumul dintre oricare două noduri e unic.

Arborele CU RĂDĂCINĂ: alegi un nod ca rădăcină și „atârni" restul de el — fiecare muchie primește sens de citire: de sus (tată) în jos (fiu). Aceeași structură, dar cu ierarhie: directorul general sus, angajații pe niveluri.

Arborele viu — atinge un nod

Organigrama unei firme cu 10 „angajați". Click pe orice nod: portocaliu = tatăl, albastru = fiii, verde = frații.

click pe un nod 👆 — încearcă 3, apoi 10, apoi 1…

Convenția nivelurilor: aici rădăcina e pe nivelul 1, iar înălțimea = numărul de niveluri. Unele culegeri numără de la 0 — la BAC, citește întâi definiția din enunț și abia apoi calculează!

Cum ține calculatorul ierarhia minte

Două oglinzi ale aceluiași arbore — alese după întrebarea la care vrei răspuns rapid.

1// C++: frunzele, din vectorul de tați

2// frunza = nod care NU e tatăl nimănui

3for (int i = 1; i <= n; i++) eTata[t[i]] = 1;

4for (int i = 1; i <= n; i++)

5 if (!eTata[i]) cout << i << " ";

1# Python: liste de fii cu dict (X·M08!)

2fii = {1: [2,3,4], 2: [5,6], 3: [7], ...}

3def h(u): # înălțimea, recursiv

4 if not fii.get(u): return 1

5 return 1 + max(h(f) for f in fii[u])

Care, când? Vectorul de tați (organizația din programă: „fiecare angajat are UN manager") răspunde instant la „cine e șeful lui x?" și la drumul spre rădăcină. Listele de fii — la „pe cine coordonează x?" și la coborâri recursive (înălțime, subarbori). Observă: t[i] e memorie fixă n; listele de fii — tot n−1 referințe, dar pe dict.

Fișa de sinteză

Arborele, condensat.

Arbore = graf conex fără cicluri = conex cu n−1 muchii = exact un lanț între oricare două noduri.

Cu rădăcină: un nod ales sus; fiecare alt nod are exact UN tată; fiii aceluiași tată sunt frați.

Frunza = nod fără fii · nivelul = distanța față de rădăcină (+1) · înălțimea = numărul de niveluri.

Vectorul de tați: t[i] = tatăl lui i, t[rădăcină] = 0; frunzele = nodurile care nu apar ca tată.

Listele de fii: pentru fiecare nod, copiii lui — perfecte pentru recursivitate: h(u) = 1 + max(h(fii)).

Rudele: arborele parțial (M08) E un arbore · drumul spre rădăcină ↔ tata[] de la Dijkstra (M07)!

Urmează: arborele BINAR — cel mult doi fii, stânga și dreapta — și cele trei parcurgeri celebre: preordine, inordine, postordine. Plus clasica de BAC: reconstruirea arborelui din două parcurgeri.

Ierarhia devine arbore