Alberi

Un albero è un particolare tipo di grafo connesso e privo di cicli. Un albero con n nodi ha esattamente n-1 archi.

Definizioni

La radice è il nodo più in alto, da cui si sviluppa tutto l'albero, e non ha un padre.
Il padre di un nodo è il nodo direttamente collegato a questo verso la radice. I figli di un nodo sono tutti i nodi direttamente collegati a questo in direzione opposta alla radice.
Le foglie sono i nodi terminali che non hanno figli.
Un sottoalbero è l'insieme di un nodo con tutti i suoi discendenti.
Un percorso è una sequenza di nodi adiacenti che connette due nodi. In un albero il percorso tra ogni coppia di nodi è unico. La lunghezza di un percorso è definita come il numero di archi che lo compongono.
La profondità di un nodo è la lunghezza del percorso che lo connette alla radice. La profondità di un albero è la profondità del nodo più profondo.