Albero binario

Questa voce o sezione sull'argomento informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Questa voce o sezione sull'argomento informatica ha problemi di struttura e di organizzazione delle informazioni.

Motivo: La voce sarebbe da riscrivere in un tono meno colloquiale (ad es. "In questa sezione trattiamo..."). La sezione "Implementare gli alberi di ricerca binari su array" sarebbe forse da spostare nella pagina "Albero binario di ricerca". Inoltre la sezione "Algoritmi elementari su alberi binari" sarebbe da sistemare secondo il manuale. Per riorganizzare la pagina si potrebbe prendere spunto da quella su en.wiki

---

Risistema la struttura espositiva, logica e/o bibliografica dei contenuti. Nella discussione puoi collaborare con altri utenti alla risistemazione. Segui i suggerimenti del progetto di riferimento.

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.