Introducere in Stiinta Calculatoarelor 2013 | Page 61

5.5.2. Liste nelineare (arbori)
Pentru această categorie de liste nodurile au legături cu număr variabil
şi nu doar între vecini (cu indici succesivi) – vezi figura 16. Relaţiile
între noduri nu privesc ordinea ci ierarhia: un nod are relaţii de
predecesor („părinte” – de exemplu E2) cu noduri succesor (noduri
subordonate, „fii” – exemplu E4 şi E5). Nodurile care nu au „fii” sunt
noduri finale şi au valorile indicatorilor nule (NULL).

Figura 16. Arbore binar

Funcţie de numărul maxim de fii ale unui nod (oarecare), arborele poate
fi categorisit ca arbore binar – maxim două noduri fii, arbore ternar –
maxim trei noduri fii, etc.
Reprezentarea arborilor binari
Cele mai utilizate categorii sunt cele binare –simple, cu proprietăţi dar
şi cu semnificaţii intuitive (de exemplu clasificarea în categorii
complementare – de un fel şi de altul); există algoritmi de transformare
a unui arbore oarecare într-un arbore binar.
Reprezentarea unui arbore se poate face şi folosind un tablou de muchii
(cu două coloane, indicând pe fiecare linie noduri adiacente) însă
folosirea indicatorilor permite o reprezentare ce ocupă un spaţiu minim
în memoria de lucru şi, evident, ne-limitarea dimensiunii arborelui.
61