 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
implementare alberi binari da array
Clicca QUI per vedere il messaggio nel forum |
| mattiie |
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. |
| mattiie |
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 |
| cioè devi mettere i valori che hai nell'array ordinatamente in un albero binario? |
| mattiie |
| 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 |
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 |
| Se vuoi ti passo quello che ho fatto io. |
|
|
|
|
