mattiie

User info:

Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

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.

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

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

mattiie

User info:

Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

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..

asgar

User info:

Registered: Jun 2009
Posts: 78 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 10:31:23 [...]
Status: Offline

Post actions:

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

mattiie

User info:

Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

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

mattiie

User info:

Registered: Oct 2010
Posts: 46 (0.01 al dì)
Location: milano
Corso: Informatica F94
Anno: Primo (Magistrale)
Time Online: 9:28:41 [...]
Status: Offline

Post actions:

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(...);

Stefano2912

User info:

Registered: Sep 2008
Posts: 101 (0.02 al dì)
Location: San Donato Milanese
Corso: Informatica
Anno: II
Time Online: 3 Days, 1:59:19 [...]
Status: Offline

Post actions:

Se vuoi ti passo quello che ho fatto io.