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