Albero binario: differenze tra le versioni

Versione delle 01:33, 8 lug 2006

Versione delle 18:54, 17 lug 2006

Riga 6:

==Implementare gli alberi binari==

In questa sezione trattiamo l'implementazione degli alberi binari dal punto di vista teorico, facendo ricordoricorso a strutture di programmazione generiche,; sarà poi compito del [[programmatore]] decidere come implementare queste strutture sulla base del [[linguaggio di programmazione]] che si troverà ad usare.

Esistono vari sistemi, ma il più semplice risulta essere quello che utilizza un [[array]] che contiene i nodi dell'albero secondo questa logica: Lala radice occupa la prima posizione dell'[[array]] e i figli di questa radice sono a loro volta nell'[[array]] e occupano come posizione (2i) e (2i+1) dove i è la posizione della radice, del padre, dei due figli.

Si fa notare che questa implementazione è ottimale se l'albero è completo cioè se tutti gli elementi che costituiscono l'albero hanno esattamente due figli, tranne ovviamente le foglie, altrimenti è necessario un flag [[booleano]], in realtà un array di accompagnamento, che ci indica se la posizione è valida o meno.