[c++Alberi binari, profondità e foglie

[Pised]

Ciao a tutti, sono nuovo sul forum, vi chiedo un aiuto relativamente agli alberi binari, mi servirebbe di capire come realizzare un algoritmo per calcolare la massima profondità di un albero (meglio ricorsivo penso no?) e uno per calcolarne il numero di foglie....avete qualche link o esempio? Grazie ancora, Pised

[lionalex]

Ma ti serve sapere l'algoritmo o proprio il codice C++???

[Pised]

ciao, grazie per la risposta, beh comprendere l'algoritmo sarebbe gia utile, se trovo anche il codice sicuramente meglio Grazie ancora

[Pised]

nessuno?

[lionalex]

Cominciamo dal calcolo del numero di foglie.
Penso che il problema si possa definire così:
Hai un albero binario, le foglie sono quei nodi che non hanno nè figlio destro nè figlio sinistro.
Quindi puoi immaginare una funzione che scorra l'albero e che incrementi una variabile GLOBALE quando incontra un nodo senza figli, quindi una foglia. In pseudo linguaggio dovrebbe essere così:

conta_foglie(T)
if (T!=NIL) //controllo che non sia un albero vuoto
  if (T.dx!=NIL) //se esiste un figlio destro allora visita il figlio destro
    conta_foglie(T.dx);
  if (T.sx!=NIL) //se esiste un figlio sinistro allora visita il figlio sinistro
    conta_foglie(T.sx);
  if (T.sx==NIL)AND(T.dx==NIL) //se non ha figli, allora incrementa la variabile GLOBALE FOGLIE
    foglie=foglie+1

Per quanto riguarda il livello massimo di profondità, è un pochettino più complicato...penso possa risolversi in questo modo. Porti dietro una variabile locale che si incrementa ogni volta che scendi di livello, confronti questo valora con un valore GLOBALE e ti salvi quello massimo.

conta_livello(T,liv)
if (T!=NIL) //controlla che non sia un albero vuoto
  if (T.dx!=NIL) //se ha un figlio destro, va a destra e incrementa il livello
    conta_livello(T.dx,liv+1)
  if (T.sx!=NIL) //se ha un figlio sinistro, va a sinistra e incrementa il livello
    conta_livello(T.sx,liv+1)
  if (T.sx==NIL)AND(T.dx==NIL) //se non ha figli, ha raggiunto una foglia
    if max<liv //confronta il valore del livello con una variabile GLOBALE e se è il massimo livello
      max=liv  //aggiorna la variabile GLOBALE

Spero siano funzioni corrette e che funzionino