Pentru problemele în care se
impune o ierarhizare a informaţiilor ce corespund vârfurilor arborelui, astfel
încât anumite vârfuri să fie subordonate altora, este utilă introducerea unei
noi noţiuni de arbore cu rădăcină.
Arborii cu rădăcină (Figura nr.2)
sunt o prezenţă cotidiană. Fiecare şi-a reconstituit la un moment dat arborele
genealogic şi, după cum vom vedea, cea mai mare parte a termenilor folosiţi în limbajul
informatic derivă de aici.
 |
Figura nr. 2 – Arbore cu rădăcină
|
Definiţie: Un arbore cu
rădăcină este o mulţime finită de noduri care, fie este vidă, fie:
• există un nod special numit
rădăcina arborelui;
• toate celelalte noduri sunt
partiţionate în n≥0 clase A1, A2, ...,An, fiecare clasă fiind un arbore cu
rădăcină. Rădăcina arborelui este unită prin muchii de rădăcinile arborilor A1,
A2, ...,An.
Definiţia este recursivă, orice
nod al unui arbore fiind rădăcina unui subarbore.
 |
Figura nr. 3 –Arbore cu rădăcină, nivele
|
Să observăm că definiţia conduce
la o ierarhizare a nodurilor arborelui :
·
considerăm că rădăcina r se situează pe nivelul 0.
·
dacă notăm cu r1, r2, ...,
rn respectiv rădăcinile arborilor A1, A2, ...,
An, nodurile r1, r2, ..., rn vor
constitui nivelul 1 în arbore, ş.a.m.d.
Nodurile r1, r2,
..., rn, se numesc fiii nodului rădăcină, iar rădăcina r reprezintă
părintele nodurilor r1, r2, ..., rn, rădăcina fiind singurul nod din arbore care
nu are părinte. Fiecărei muchii din
arbore îi putem asocia o orientare de la părinte spre fiu. În plus, fiii nodurilor de pe nivelul i≥0,
vor constitui nivelul i+1.
Nivelul maxim din arbore va
constitui înălţimea (adâncimea) arborelui respectiv. Să observăm că orice nod x poate fi atins din
rădăcină pe un drum unic. Orice nod y
care se găseşte pe drumul unic de la r la x se numeşte ascendent (strămoş) al
lui x. Dacă y este un ascendent al lui x, atunci x se numeşte descendent al lui
y. Mai exact, toţi descendenţii unui nod x sunt nodurile din subarborele cu
rădăcina x. Dacă un nod nu are descendenţi, el se numeşte nod terminal sau
frunză. Două noduri care au acelaşi părinte se numesc fraţi.
În exemplul de mai sus (Figura
nr.3), 4 este un ascendent al lui 8. Nodurile
5, 6, 3, 8, 9 sunt noduri terminale. Nodurile 8, 9 sunt fraţi, iar
descendenţii nodului 4 sunt nodurile 7, 8, 9.