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ร :
- Un nodo dellโalbero รจ designato come nodo radice
- Ogni nodo n, a parte la radice, ha esattamente un arco entrante
- Esiste un cammino unico dalla radice ad ogni nodo
- Lโalbero รจ connesso
๐ Definizione 2
Un albero รจ dato da:
- Un insieme vuoto, oppure
- Un nodo radice e zero o piรน sottoalberi, ognuno dei quali รจ un albero; la radice รจ connessa alla radice di ogni sottoalbero con un arco orientato
๐ 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
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/ImplVettoreFigli.png)
Campi memorizzati nei nodi:
- parent: reference al nodo padre
- vettore dei figli: a seconda del numero di figli, puรฒ comportare una discreta quantitร di spazio sprecato
Realizzazione primo figlio, prossimo fratello
Implementato come una lista di fratelli
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/ImplListaFigli.png)
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.
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/ImplVettorePadri.png)
Per ogni nodo in posizione
- Il figlio sinistro si trova nella posizione
- Il figlio destro si trova nella posizione