Memorarea arborilor cu rădăcină

Fiind de cele mai multe ori reprezentați ca niște grafuri neorientate, arborii pot fi memorați prin aceleași metode de reprezentare în memorie ca la grafurile neorientate.

Cu toate acestea, există o metodă de reprezentare specifică arborilor cu rădăcină, anume vectorul de tați.

Vectorul de „tați” memorează, pentru fiecare nod al arborelui, ascendentul direct (tatăl).

Rădăcinii îi va corespunde valoarea $0$ în vector.

Exemplul unui vector de tați pentru un arbore cu rădăcină:

Pe poziția corespunzătoare unui nod se va trece eticheta ascendentului direct. $T$ reprezintă vectorul.

Proprietăți vector de tați

Vectorul de tați ne poate oferi mai multe informații despre arborele pe care îl reprezintă:

• un singur nod are ascendentul $0$, acela fiind chiar rădăcina arborelui;
• nodurile care nu apar ca ascendenți pentru alte noduri sunt frunze (deoarece nu au fii);
• gradul unui nod care nu este rădăcină va fi numărul de apariții în vector $+ 1$ (se adaugă legătura cu ascendentul său);
• vectorul de tați este unic pentru un arbore cu rădăcină.