.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- implementare alberi binari da array (http://www.dsy.it/forum/showthread.php?threadid=41393)

implementare alberi binari da array

Salve a tutti. Sto seguendo il corso di lab con la professoressa Lonati.
Nella scheda 8 ci chiede di implementare un albero binario (non di ricerca) da un array. Non riesco a trovare un algoritmo che vada bene.
Inserimento deve essere in ampiezza..
Qualcuno ha qualche idea?
thnx
M.P.

http://it.wikipedia.org/wiki/ Alber...binari_su_array

Avevo già letto su wikipedia come implementare un albero binario su array ma quello che mi servirebbe è proprio il contrario: implementare un albero binario DA array. Dove ogni nodo è una struttura con un campo per il valore e due per puntare al sottoalbero sx e dx.
Ringrazio comunque..

cioè devi mettere i valori che hai nell'array ordinatamente in un albero binario?

Sì, sembra semplice ma è più difficile di quello che si pensi. Ho passato tutto ieri a pensarlo e riguardando gli appunti l'unica idea che ho trovato è quella di utilizzare una coda, senza non si riesce a riempirlo in ampiezza..però non sono ancora arrivato all'algoritmo soluzione

Sono riuscito a creare un algoritmo in pseudo-codice che funziona ma secondo me si può migliorare ancora:

procedura main:
root (che è il puntatore all'albero) è null?
se sì allora
root=malloc (sizeof(Bit_node));
se no
inserisci root in una coda
chiama la procedura new

procedura new:
prendo un nodo dalla coda
ha due figli?
se sì
li aggiungo entrambi alla coda
chiamo la procedura new
se no
il figlio sx è occupato?
se sì
figlio sx= malloc(...);
se no
figlio dx= malloc(...);

Se vuoi ti passo quello che ho fatto io.