idt_winchip
28-06-2009, 10:47
Salve a tutti ragazzi..avrei un problemino che non è tanto di linguaggio bensì di algoritmo..
Devo implementare un metodo per calcolare la lunghezza del cammino interno/esterno di un albero, ma non riesco a trovare delle informazioni chiare a riguardo.
Mi rifaccio a questo testo:
La lunghezza del cammino interno di un albero binario è la somma delle lunghezze
dei cammini che collegano la radice a tutti i nodi interni, ovvero la somma dei livelli
di tutti i nodi interni dell’albero. In modo analogo, la lunghezza del cammino esterno
di un albero binario è la somma delle lunghezze dei cammini che collegano la radice a
tutti i nodi esterni, ovvero la somma dei livelli di tutti i nodi esterni dell’albero. Un
modo semplice per calcolare la lunghezza del cammino interno (esterno) in un albero
è sommare, per ogni livello k, il prodotto di k per il numero dei nodi al livello k.
Non mi è necessario l'algoritmo, vorrei solo capire come si trova.
Cioè, io ho un albero fatto così
livello 0(radice) -----------4
livello 1--------------3---------6
livello 2----------1---------5--------7
Mi dice che per rovare il cammino devo sommare per ogni livello k, il prodotto di k per il numero di nodi al livello k.
quindi? Cammino interno = 2*1 e Cammino esterno = 2*1+3*2 ?
Avrei da consegnare l'elaborato domani, per il momento il metodo lo calcola così ma non ne sono molto sicuro..se qualcuno mi può confermare o smentire lo apprezzerei molto.. :)
Grazie a tutti in anticipo
Devo implementare un metodo per calcolare la lunghezza del cammino interno/esterno di un albero, ma non riesco a trovare delle informazioni chiare a riguardo.
Mi rifaccio a questo testo:
La lunghezza del cammino interno di un albero binario è la somma delle lunghezze
dei cammini che collegano la radice a tutti i nodi interni, ovvero la somma dei livelli
di tutti i nodi interni dell’albero. In modo analogo, la lunghezza del cammino esterno
di un albero binario è la somma delle lunghezze dei cammini che collegano la radice a
tutti i nodi esterni, ovvero la somma dei livelli di tutti i nodi esterni dell’albero. Un
modo semplice per calcolare la lunghezza del cammino interno (esterno) in un albero
è sommare, per ogni livello k, il prodotto di k per il numero dei nodi al livello k.
Non mi è necessario l'algoritmo, vorrei solo capire come si trova.
Cioè, io ho un albero fatto così
livello 0(radice) -----------4
livello 1--------------3---------6
livello 2----------1---------5--------7
Mi dice che per rovare il cammino devo sommare per ogni livello k, il prodotto di k per il numero di nodi al livello k.
quindi? Cammino interno = 2*1 e Cammino esterno = 2*1+3*2 ?
Avrei da consegnare l'elaborato domani, per il momento il metodo lo calcola così ma non ne sono molto sicuro..se qualcuno mi può confermare o smentire lo apprezzerei molto.. :)
Grazie a tutti in anticipo