[C] Lunghezza di cammino in un albero binario

[leffy85]

Ricordiamo che la lunghezza di cammino in un albero con radice è la somma delle distanze dei nodi dalla radice.
Progettare un algoritmo ricorsivo per calcolare le lunghezze di cammino in un albero binario con radice qualsiasi.

ho questo esercizio da svolgere ma non ho idea di come implementare la funzione ricorsiva per il calcolo della lunghezza di un cammino.
chi mi da qualche consiglio per favore??
grazie

[leffy85]

help help help

[MrX87]

ciao, ma spiega meglio il tuo problema...cioè a te serve implementare una funzione ricorsiva che lavori su un albero binario(supponiamo che memorizzi interi) che, dato in input un valore, calcoli la lunghezza del percorso che c'è dalla radice a quel valore (nodo). giusto?

[leffy85]

io dovrei passare come parametro alla funzione ricorsiva il puntatore della radice del (sotto)albero. la funzione deve calcolare la lunghezza di cammino.
ma che è questa lunghezza di cammino per definizione???

[PeppePes88]

Più o meno la definizione è questa :

Ricordiamo che la lunghezza di cammino in un albero con radice è la somma delle distanze dei nodi dalla radice.

l'algoritmo è semplice, basta una funzione ricorsiva che somma uno per ogni nodo che trova, finché non trova il nodo cercato o arriva alla fine!

Pero tu hai posto male il problema!!! Che percorso ti serve?? Cioè dalla radice a quale nodo??

[leffy85]

la traccia dell'esercizio l'ho riportata tutta nel primo messaggio. anche secondo me il problema è mal posto, ma me l'hanno assegnato così e la professoressa non risponde.
comunque per lunghezza di cammino si intende la lunghezza da una radice (di qualsiasi livello essa sia) a una foglia??
o puo fermarsi anche in un nodo non foglia???

[MrX87]

bhè ma scusa se ti dice così l'esercizio è strano, perchè dovrebbe dirti il nodo di partenza( che supponiamo sia la radice) ma anche il nodo di arrivo!! non è detto che sia per forza una foglia!

[PeppePes88]

[quote]
comunque per lunghezza di cammino si intende la lunghezza da una radice (di qualsiasi livello essa sia) a una foglia??
[quote]

la radice in un albero è unica.....

Il camino è il percorso tra la radice è un nodo!!!

per esempio, il un albero binario di ricerca, il percorso tra la radice è il nodo x si ottiene cosi:

int camino ( nodo * radice, int valore ) { 
               if (!radice) return 0; 
               if ( radice->valore == valore) return 1; 
               if ( radice->valore > valore)  return 1 + camino(nodo->sinistra); 
                else return 1 + camino ( nodo->destra);
}+

[MrX87]

Ehm...okay la programmazione ma in genere si studia prima il linguaggio ITALIANO:

Il camino è il percorso tra la radice e un nodo!!!
...
il percorso tra la radice e il nodo x si ottiene cosi:

per il resto si è corretto, nel caso di un BST, anche se sarebbe:

int camino ( nodo * radice, int valore ) { 
               if (!radice) return 0; 
               if ( radice->valore == valore) return 1; 
               if ( radice->valore > valore)  return 1 + camino(nodo->sinistra, valore); 
                else return 1 + camino ( nodo->destra, valore);
}

[PeppePes88]

Non avevo riletto il messaggio....

Poi l'avevo scritto appena svegliato!! E già tanto che il codice è corretto.....