Albero binario: differenze tra le versioni

Versione delle 07:43, 24 giu 2006

Versione delle 00:49, 25 giu 2006

Riga 1:

Un albero binario è una [[struttura dati]] formata da nodi collegati tra loro da archi.

Ogni nodo è strutturato in modo particolarmente semplice, ovvero una chiave, il ''contenuto'' del nodo, e poi due puntatori, ovvero un puntatore al figlio desto e uno al figlio sinistro. Questa è una limitazione rispetto agli [[Albero (informatica)|alberi]] tradizionali per i quali non si era mai messo un limite alla ramificazione, invece in questo caso, ogni nodo può avere al massimo due figli.

Ecco quali sono le caratteristiche che denotano un albero binario, premettendo che se anche uno solo di questi parametri è trascurato allora l'albero non è più binario.

# Ogni nodo ha al più due figli

# I figli sono ordinati tra loro

# Ogni figlio può essere radice di un nuovo albero

I vantaggi di questa implementazione non sono subito evidenti, si accetti come postulato che la visita di una lista implementata con un albero binario è molto efficiente.