Visualizzazione dei risultati da 1 a 3 su 3
  1. #1

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

    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:

    codice:
    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
    "Estremamente originale e fantasioso" By darkiko;
    "allora sfiga crepuscolare mi sa che e' meglio di atmosfera serale" By NyXo;
    "per favore, già è difficile con lui" By fcaldera;
    "se lo apri te e invece di "amore" ci metti "lavoro", l'effetto è lo stesso" By fred84

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

    codice:
    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...

  3. #3
    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:

    codice:
    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);
    }
    Fracty - The Fractal Generator



    If you cannot choose a concise name that expresses what the method does, it is possible that your method is attempting to perform too many diverse tasks.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.