Alberi

Indice

๐Ÿ“ Definizione 1

Un albero consiste di un insieme di nodi e un insieme di archi orientati che connettono coppie di nodi, con le seguenti proprietร :

๐Ÿ“ Definizione 2

Un albero รจ dato da:

๐Ÿ“š Terminologia

Profonditร  di un nodo (depth)

La lunghezza del percorso dalla radice al nodoย (cioรจ il numero di archi tra la radice e il nodo).

Livello (level)

Lโ€™insieme di nodi alla stessa profonditร .

Altezza albero (height)

La profonditร  massima della sue foglie.

โŒจ๏ธ Implementazione

Esistono diversi modi per memorizzare un albero, piรน o meno indicati a seconda del numero massimo e medio di figli presenti.

Realizzazione con vettore dei figli

ImplVettoreFigli.png500

Campi memorizzati nei nodi:

Realizzazione primo figlio, prossimo fratello

Implementato come una lista di fratelli

ImplListaFigli.png500

Realizzazione con vettore dei padri

Lโ€™albero รจ rappresentato da un vettore i cui elementi contengono il valore associato al nodo e lโ€™indice della posizione del padre nel vettore.

ImplVettorePadri.png500

Per ogni nodo in posizione i nel vettore: