25/05/07 21:10
lorelapo
Ho scritto un programma che usa strutture di appoggio per ordinare, in questo caso specifico alberi binari.
Il suo funzionamento è semplice :
1)Si parte da un vettore nel nostro esempio sarà questo :
5-4-8-1-86-7
2)Si "inalbera" il vettore in un modo molto semplice
la radice dell'albero corrisponderà sempre all'elemento 0 del vettore per cui l'albero all'inizio sarà così.
5
+--+--+
3)Si mette nell'albero l'i-esimo elemento del vettore come così:
.1)Se l'elemento da inserire è maggiore o uguale alla radice dell'albero in questione si mette nel ramo sinistro, altrimenti nel destro
.2)Se il ramo è vuoto allora si piazza il valore lì altrimenti si ripete .1
4)Si ripete 3 fino alla fine del vettore
5)Ora abbiamo l'albero magicamente ordinato ma così ci serve a poco allora si "reinvettora" l'albero visitandolo simmetricamente e sovrascrivendo il vettore originale cioè
.1)Se il ramo sinistro non è nullo ripeto .1 con lui
.2)"invettoro" il valore della radice
.3)Se il ramo destro non è nullo ripeto .1 con lui
6)Vettore ordinato
Proviamo ora
Inalberazione
5
+---+--+
8 4
+-+-+ +-+
86 7 1
Allora iniziamo a visitare l'albero
-L'albero sinistro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (1)
---L'albero destro è nullo ? si allora ritorno
--Aggiungo la radice (4)
--L'albero destro è nullo ? si allora ritorno
-L'albero destro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (7)
---L'albero destro è nullo? si allora ritorno
--Aggiungo la radice (8)
--L'albero destro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (86)
---L'albero destro è nullo ? ritorno
--ritorno
-ritorno
Ora guardate la sequenza di numeri che ci siamo ritrovati
1-4-7-8-86
Ordinati!!!
Volevo solo proporre l'algoritmo e chiedere se qualcuno ne sà il nome così posso pubblicare il programma con il suo nome.Scusate la lunghezza del topic.Grazie.
Il suo funzionamento è semplice :
1)Si parte da un vettore nel nostro esempio sarà questo :
5-4-8-1-86-7
2)Si "inalbera" il vettore in un modo molto semplice
la radice dell'albero corrisponderà sempre all'elemento 0 del vettore per cui l'albero all'inizio sarà così.
5
+--+--+
3)Si mette nell'albero l'i-esimo elemento del vettore come così:
.1)Se l'elemento da inserire è maggiore o uguale alla radice dell'albero in questione si mette nel ramo sinistro, altrimenti nel destro
.2)Se il ramo è vuoto allora si piazza il valore lì altrimenti si ripete .1
4)Si ripete 3 fino alla fine del vettore
5)Ora abbiamo l'albero magicamente ordinato ma così ci serve a poco allora si "reinvettora" l'albero visitandolo simmetricamente e sovrascrivendo il vettore originale cioè
.1)Se il ramo sinistro non è nullo ripeto .1 con lui
.2)"invettoro" il valore della radice
.3)Se il ramo destro non è nullo ripeto .1 con lui
6)Vettore ordinato
Proviamo ora
Inalberazione
5
+---+--+
8 4
+-+-+ +-+
86 7 1
Allora iniziamo a visitare l'albero
-L'albero sinistro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (1)
---L'albero destro è nullo ? si allora ritorno
--Aggiungo la radice (4)
--L'albero destro è nullo ? si allora ritorno
-L'albero destro è nullo ? no allora lo visito
--L'albero sinistro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (7)
---L'albero destro è nullo? si allora ritorno
--Aggiungo la radice (8)
--L'albero destro è nullo ? no allora lo visito
---L'albero sinistro è nullo ? si allora aggiungo la radice (86)
---L'albero destro è nullo ? ritorno
--ritorno
-ritorno
Ora guardate la sequenza di numeri che ci siamo ritrovati
1-4-7-8-86
Ordinati!!!
Volevo solo proporre l'algoritmo e chiedere se qualcuno ne sà il nome così posso pubblicare il programma con il suo nome.Scusate la lunghezza del topic.Grazie.
Ultima modifica effettuata da lorelapo 25/05/07 21:12
aaa
