ordinamento di un alb_bin in C...

[marcus81]

Dunque ho un abero binario su cui inserisco delle strutture così composte in ogni nodo:

typedef struct squadre{
char nome_squadra[12];
int punti;
}SQUADRE;

nel primo inserimento l'ordinamento viene fatto in base al campo nome_squadra(ordinamento lessicografico), e i punti vengono inizializzati tutti a zero.
Una procedura mi aggiorna i punti a seconda di vittoria(+3), pareggio(+1),sconfitta(nulla).
l'obbiettivo è di mettere in ordine la classifica tramite un'altra funzione...e li vengono i miei problemi!
Come ordinare un albero binario già costruito in base al campo punti?
l'ordinamento lo vorrei fare in modo tale che posso leggere l'albero in ordine simmetrico...
Come fare?grazie x l'aiuto

[marcus81]

nessuno?

[marcus81]

[marcus81]

nessuno ha qualke soluzione?
nemmeno il "maestro" cionci?

[cionci]

Il metodo migliore per ordinare un albero binario dovrebbe essere lo heap sort...

L'unica cosa che mi lascia un po' perplesso è la visita simmetrica...
Se non sbaglio con lo heap sort standard si fa un ordinamento per la visita posticipata...

Cerco qualche algoritmo e te lo posto...

[/\/\@®¢Ø]

Originariamente inviato da marcus81
[b]
Come ordinare un albero binario già costruito in base al campo punti?
l'ordinamento lo vorrei fare in modo tale che posso leggere l'albero in ordine simmetrico...
Come fare?grazie x l'aiuto

Il modo piu' semplice e' quello di estrarre l'elemento da aggiornare, aggiornare il campo e reinserirlo. Con uno heap potresti invece evitare le eliminazioni e gli inserimenti (sempre che tu aggiorni solo "verso l'alto" i punteggi ), pero' in tal caso non riusciresti a fare ricercche, ma solo a prendere la squadra col valore piu' alto ( oppure a fare una scansione come in un normale array ).
Se i valori dei punteggi li cambi in blocco ( i punteggi di tutte le squadre dopo ogni giornata ad esempio ) un'altra alternativa e' quella di tenerti i valori in un semplice array e usare un algoritmo di ordinamento 'classico' , alcuni sono buoni se i valori sono "abbastanza ordinati". Per le ricerche potrai usare sempre una ricerca binaria sull'array e quindi non perdi in performance.

[/\/\@®¢Ø]

Non ho risposto a tutta la domanda... cosa intendi per "ordine simmetrico" ?

[cionci]

Originariamente inviato da /\/\@®¢Ø
[b]Non ho risposto a tutta la domanda... cosa intendi per "ordine simmetrico" ?

Forse intende "visita simmetrica"...cioè una cosa del genere :

visita(figlioSx);
visualizza valore del nodo;
visita(figlioDx);

In questo modo alla Sx del nodo ci dovranno essere tutti valori minori del nodo corrente...mentre alla destra tutti valori maggiori (solo per fare un esempio)...

[/\/\@®¢Ø]

Ah grazie ! Io la conosco come "ordine infisso".
In tal caso allora il primo metodo ( rimozione - aggiornamento - rimozione ) funziona senza problema ( basta appunto fare una "visita infissa" ), nel terzo caso ancora piu' semplice : scorri linearmente l'array. Nel caso dell'heap invece temo che la cosa non funzioni...

[cionci]

L'unico problema sarebbe costruirsi lo heap, ma non è poi così difficile...dopo applicare l'ordinamento standard porta a risultati sicuri...

Però lo heap sort crea un albero con un ordinamento valido solo per la visita anticipata e posticipata...ma non per quella simmetrica...

[marcus81]

dunque ragazzi:
per quanto riguarda lo heap nn ci ho mai messo mano,quindi nn saprei....
cmq ordinare l'albero a me serve soltanto per poi visualizzare una classifica in base al campo punti...nn per ricerca...e nn mi interesse se visito l'albero in ordine simmetrico,anticipato o posticipato: l'importante è che riesca poi a visualizzare sta classifica dalla squadra che ha + punti a scendere...
..inoltre ho già fatto tutte le funzioni con allocazione dinamica della memoria non con array quindi...

[/\/\@®¢Ø]

Beh, se fai un array di puntatori devi cambiare poco penso. Ovviamente le routine di inserimento/rimozioni andranno cambiate, ma quelle che operano sulla struct squadre non penso. E in piu' potresti usare le funzioni di ordinamento della libreria standard.
Comunque se vuoi tenerti l'albero basta appunto che fai la trafila rimozione-aggiornamento-inserimento, non sara' il massimo dell'eleganza ma funziona. Poi visitando l'albero in modalita' infissa ( figlio sinistro - padre - figlio destro ) ottieni i punteggi in ordine crescente ( o decrescente a seconda di come lo ordini ) come serve a te.

Se infine decidi di passare al C++, c'e' il 'set' che ti attende a braccia aperte .

[marcus81]

potresti essere un pò + preciso su questo metodo di rimozione-inserimento-aggiornamento?nn l'ho mai fatto...
se nn sbaglio dovrei prelevare ogni nodo e reinserirlo nell'albero?cominciando da dove?

[/\/\@®¢Ø]

Come non detto, ho sbagliato... se usi come chiave i punteggi poi non puoi fare una ricerca per il nome della squadra ( a meno di passare al setaccio tutto l'albero ).

Comunque una domanda: ti e' proprio necessario l'albero binario ? Se non hai tanti valori ( e non penso tu abbia migliaia di squadre ) probabilmente il gioco non vale la candela...

[cionci]

Scusa, ma non ti basta fare un vettore con tutti i puntatori agli elementi dell'albero...poi ordini spostando questi puntatori all'interno del vettore (in base ad un membro della struttura del nodo)...e dopo, eventualmente, puoi ricostruirti l'albero binario...

[/\/\@®¢Ø]

Originariamente inviato da cionci
[b]Scusa, ma non ti basta fare un vettore con tutti i puntatori agli elementi dell'albero...poi ordini spostando questi puntatori all'interno del vettore (in base ad un membro della struttura del nodo)...e dopo, eventualmente, puoi ricostruirti l'albero binario...

Si, ma allora a questo punto visto che le squadre sono quelle, e' piu' pratico tenersi solo l'array e ordinarlo quando ce n'e' bisogno

[cionci]

Originariamente inviato da /\/\@®¢Ø
[b]
Si, ma allora a questo punto visto che le squadre sono quelle, e' piu' pratico tenersi solo l'array e ordinarlo quando ce n'e' bisogno

Certo...infatti non vedo il motivo per cui le ha tenute in un albero...

[marcus81]

il fatto è che in questo momento nn mi interessa tanto l'efficienza...
questo programma l'avevo prima fatto con le liste concatenate e mi è venuto un pò + semplice, adesso volevo convertire il tutto in alberi, solo al fine di avere + elasticità e familiarizzare meglio con gli alberi, visto ke a brevissimo avrò un compitino di C....