[C++] Algoritmo ricorsivo per la profondità di un albero binario

[Neptune]

Salve a tutti,
ho progettato un algoritmo ricorsivo per alberi binari che, dato un nodo dice quanto è lungo il cammino più lungo. Se ovviamente dai la radice ti da la profondità massima dell'albero.

Le sottofunzioni utilizzate credo che si capiscano abbastanza:

empty(): Controlla che l'albero non sia vuoto;
dx_empty(n): Dato un nodo controlla che abbia un figlio destro;
sx_empty(n): Dato un nodo controlla che abbia un figlio sinistro;

Il codice è il seguente:

template <class T,class N>
int Bin_tree<T,N>::maxProfondita(Bin_tree<T,N>::Nodo n)
{
	int c = 0, max = 0;
	if(!empty() && sx_empty(n) && dx_empty(n))
		return 0;
	else
		if(!empty())
			   {
				   if(!sx_empty(n))
				   {
						if((c = maxProfondita(sx(n))) > max)
							max = c;
				   }

				   if(!dx_empty(n))
				   {
						if((c = maxProfondita(dx(n))) > max)
							max = c;
				   }
				   if(!dx_empty(n) || !sx_empty(n))
					   return max+1;
			   }
		else return 0;
}

L'ho provato con varie configurazioni e "pare" funzionare, ma volevo averne la totale sicurezza, quindi magari se vi va di dargli un occhiata e dirmi se "la logica secondo il quale funziona" è giusta o è errata, o magari si potrebbe migliorare, ve ne sarei grato.

Del resto data la mia scarsa preparazione riguardo agli algoritmi ricorsivi volevo chiedervi se avete da consigliare qualche libro, how-to, slide o quel che sia che possa proporre qualche metodo e qualche esercizio per imparare bene a progettare algoritmi ricorsivi

[lolide]

Si l'algoritmo funziona bene... cmq io l'avrei fatto in un altro modo + semplice e con meno variabili

template <class T,class N>
int Bin_tree<T,N>::maxProfondita(Bin_tree<T,N>::Nodo n)
{
    /* se è vuoto lui stesso allora ritorno 0 */
    if (empty())
        return 0;
    /* se non ha nodi però questo nodo non è vuoto, ritorno 1 */
    if (sx_empty(n) && dx_empty(n))
        return 1;
    /* se questo nodo non è nullo e ha un nodo a sinistra ritorno 1+calcolo di
        profondita di sinistra */
    if (!sx_empty(n) && dx_empty(n))
        return 1+maxProfondita(sx(n));

    /* se questo nodo non è nullo e ha un nodo a destra ritorno 1+calcolo di
        profondita di destra */
    if (sx_empty(n) && !dx_empty(n))
        return 1+maxProfondita(dx(n));
    /* se questo nodo non è nullo e ha un nodo a sinistra ed uno a destra
        ritorno 1+calcolo di profondita di sinistra + calcolo di profondità di destra */
    if (!sx_empty(n) && !dx_empty(n))
        return 1+maxProfondita(dx(n))+maxProfondita(sx(n));
}

Questo non l'ho provato ma dovrebbe funzionare.
Ovviamente posta la condizione che se un nodo parent è vuoto allora non possa avere altri nodi child.
Cmq per le ricorsioni è un problema. E' un metodo che usano in pochi intanto perchè si rischia lo stack overflow in caso di ricorsioni lunghe (richiamare molte volte la stessa funzione, rischia di far riempire lo stack), e poi perchè è un algoritmo + difficile rispetto magari ad un normale ciclo.
Dall'altra c'è un miglioramento della leggibilità.

Per imparare devi solo applicarli, magari con funzioni facili tipo somma, differenza, calcolo delle potenze ecc...

[GliderKite]

Devi partire dal presupposto che quello che chiedi è semplicemente determinare l'altezza di un albero binario che corrisponde al massimo fra i livelli di tutti i suoni nodi (dove con livello s'intende il livello del padre del nodo più 1, con livello della radice pari a 0).

Quindi ricorsivamente si fa semplicemente:

int getHeight( const NODE *root )
{
	unsigned l, r;

	if( root == NULL )
		return -1;

	l = getHeight( root->left );
	r = getHeight( root->right );

	return (l > r ?  l+1 : r+1);
}