Albero binario

In informatica un albero binario è un albero i cui nodi hanno grado compreso tra 0 e 2. Per albero si intende un grafo non diretto, connesso e aciclico mentre per grado di un nodo si intende il numero di sotto alberi del nodo, che è uguale al numero di figli del nodo.

Anche l'albero costituito da un solo nodo e nessun arco si considera un albero binario valido, sebbene il grado del nodo in questo caso sia nullo.

Come nel caso generale degli alberi è possibile individuare (in maniera non unica) un nodo radice: qualunque nodo di grado minore di 3 può essere scelto come radice dell'albero binario. Stabilito un nodo radice è possibile costruire delle relazioni di parentela tra nodi: il nodo radice non ha padre e può avere 0, 1 o 2 figli, ed ogni nodo è ovviamente padre dei suoi figli. Poiché tutti i nodi tranne la radice hanno un padre, per via della limitazione sul grado dei nodi ogni nodo può avere al massimo 2 figli (da qui il nome "albero binario").

I nodi senza figli vengono detti foglie o nodi terminali; un nodo non foglia è un nodo interno.