10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
GLI ALBERI DEF : Un ALBERO A è un particolare tipo di GRAFO CONNESSO E SENZA CICLI
Un albero A gode SEMPRE delle seguenti 3 PROPRIETA ’: 1 . se un albero possiede n nodi allora conterrà n-1 archi ( N . B . non è vero il viceversa ): 2 . due nodi qualsiasi in un albero sono sempre connessi da un unico cammino semplice ; 3 . rimuovendo un qualsiasi arco dell ’ albero , la struttura dati risultante
- non è più connessa - rimane divisa in due strutture dati astratte non lineari che risultano essere anch ’ esse alberi
I tipi più utili di alberi usati in informatica sono gli alberi con radice ossia quegli alberi ai quali ad un nodo detto “ radice ” viene attribuito un significato speciale .
In un albero ogni nodo può essere considerato radice del sottoalbero che da esso trae origine . I nodi dai quali non vengono originati sottoalberi , vengono chiamate foglie .
Esempio di albero con radice
Nodo Radice |
A |
Sottoalbero del nodo A con nodo radice C |
B
C
G
Nodi Foglie
Notazione : radice dell ’ albero : foglie dell ’ albero : nodi intermedi dell ’ albero :
A H , I , D , E , G B , C , F
Gli alberi che considereremo saranno alberi ordinati ( nei quali si possono distinguere gli elementi primo , secondo , … n-esimo secondo un determinato criterio ) alberi per i quali l ’ ordinamento dei sottoalberi è importante .
DEF . In un albero A si dice grado di un nodo il numero dei sottoalberi di quel nodo .
DEF . In un albero A si dice livello di un nodo il numero di nodi attraversati da un cammino semplice dalla radice al nodo . Se il nodo è la radice dell ’ albero , il livello è uguale ad 1 .
DEF . Si dice altezza o profondità h di un albero A la lunghezza ( ossia il numero di nodi ) del
cammino semplice più lungo esistente tra nodo radice e nodi foglie , escludendo dal conteggio il nodo radice .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 47