PDA

Visualizza la versione completa : [ALGORITMO] Creazione e rappresentazione di un "albero binario"


blulaserstar
23-09-2006, 15:46
Salve ragazzi ho un problemuccio.
ad un orale c'è la possibilità che la prof mi scriva su di un foglio di carta tutta una serie di numeri e mi dica di metterglieli in un albero binario.
Ora se mi scrivesse:
50,20,10,40,30,35,70,90,80,100

1) come faccio a stabilire il nodo principale? sembrerà una domanda banale ma nelle dispense non lo spiega, da dei numeri e mi crea il nodo principale così senza che io capisca il perchè, o sono tordo io o mi manca una spiegazione!

2) perchè ottengo questo grafico?
http://img160.imageshack.us/img160/4897/immaginead0.png
Logicamente mi semba corretto ovvero prendo il primo numero minore e più vicino a 50, il maggiore e più vicino, poi così via ma mi incartoccio. anche qui che regola bisogna seguire!?

Il Pazzo
23-09-2006, 17:40
Allora... dovrebbe essere così (spero che qualcuno dia conferma o smentisca)...

Considera il primo numero come la radice... il resto come suoi figli... naturalmente se il figlio è più più piccolo del padre va a sinistra altrimenti a dx... quindi nel tuo caso (con quella serie di numeri che hai scritto) l'albero dovrebbe essere come segue:

blulaserstar
23-09-2006, 18:02
si ma... come trovo il primo nodo? ce ne sono tanti di numeri perchè proprio 50?
e così per i figli, dopo il primo nodo ce ne sono tanti di minori ma quali mettere per primi?
mi sfuggono queste regole di costruzione!
Comunque l'albero che hai fatto penso che sia proprio esatto perchè è quello che ho pure io!

doraemon83
24-09-2006, 01:04
non è che ci sia una regola di costruzione... puoi prendere un qualsiasi numero come radice (Puoi ad esempio rispettare l'ordine che ti da la prof)

Quindi prendi il primo numero ed è la radice... prendi il secondo: se è minore lo metti a sinistra, se è maggiore a destra; e cosi via per tutti quanti fino a che non finisci tutti i numeri.

A meno che non ti da come vincolo che l'albero deve essere bilanciato, ma non credo che sia questo il caso...

ciao ciao

blulaserstar
24-09-2006, 14:55
ah è proprio vero che le cose più semplici sono proprio quelle che ti fregano :smack: grazie mille

blulaserstar
01-02-2007, 14:13
sbaglio o l'80 dovrebbe essere nel sottoalbero sinistro del 90?

doraemon83
01-02-2007, 20:13
non sbagli :)

Loading