[C] Ricorsione albero binario

[ipnotic]

Ciao a tutti..... stavo studiando su un libro la ricorsione legata agli alberi binari... ho questa funzione ma nn risco proprio a capire come funziona:

void inorder (BTREE root)
{
 if (root != NULL) {
     inorder (root ->left);
     printf("%c", root-> d);
     inorder(root -> right);
     }
}

e la struttura a cui si riferisce tale funzione è la seguente:

 typedef struct node{
     DATA C;
    struct node *left;
    struct node *right;
   }NODE;
typedef NODE *BTREE;

Qualcuno mi spiega come funziona quella funzione ricorsiva ?
Perchè da come l'ho capita io (cioè male.. ).. non riesco a capire come possa mai arrivare al printf...

grazie

[anx721]

la funzione serve a relaizzare una visita inorder di un albero binario in modo ricorsivo. Visita inorder significa che visito (in questo caso stampo) prima il soottoalbero sinistro, quindi il nodo corrente e infine il sottoalbero destro. Ed è proprio quello che fa la funzione: prima viene richiamata ricorsivamente sul figlio sinistro, quindi stampa il valore del nodo e infiche è richiamato sul figlio destro. Prova ad eseguire la funzione su un albero d'esempio e vedi l'ordine in cui i nodi vengono stampati.

[ipnotic]

quello ke faceva e come funzionava la visita inorder lo sapevo (l'ho letto sul libro )

... a parte gli skerzi.. io nn sono molto pratico della ricorsione... e non riesco a spiegarmi come si compoorta la funzione... come ho gia detto nn riesco a capire coemm fa a eseguire la riga

printf("%c", root-> d);

se prima c'è la chiamata inorder (...)


riusciresti a spiegarmi un po' come si comporta la funzione ??

[anx721]

è vero che c'è prima la chiamat inorder() ma questa chiamata prima o poi si conclude e quando è cocnlusa come seconda istruzione c'è la stampa-

in particolare ti faccio notare che se il nodo è NULL la funzione non esegue nulla, quindi quando si arriva alle foglie dell'albero la funzione torna immediatamente senza continuare le chiamate ricorsive

[unomichisiada]

void inorder (BTREE root)
{
 if (root != NULL) {
     inorder (root ->left);
     printf("%c", root-> d);
     inorder(root -> right);
     }
}

Il modo migliore per capire come funziona la ricorsione è fare tre cose:
-Tenere presente che ogni invocazione della funzione è dal punto di vista del pc esattamente come la chiamata ad un'altra funzione qualunque
-Tenere presente che esiste uno stack di sistema in cui vengono accumulate le chiamate a funzione(spero chr tu sappia cos'è uno stack o pila)
-Provare a simulare passo passo con un caso semplice

Ad esempio supponi di avere un albero a tre nodi (supponiamo che DATA sia una stringa) con radice Carlo, figlio sinistro della radice Bruno, figlio destro Marco.
LA prima chiamata alla funzione sarà fatta dalla main con argomento la radice dell'albero (Carlo), il conrollo if (root != null) non fallisce (altrimenti l'albero sarebbe vuoto).La prossima istruzione richiama la funzione stessa con argomento il figlio sinistro di Carlo (Bruno), quello che succede è che La chiamata che si sta occupando di carlo viene sospesa cioè salvata nello stack (viene salavata anche la posizione attuale del "cursore di esecuzione").La chiamata che gestisce bruno trova ancora che il test non fallisce ed esegue la prima istruzione che è quella di fare una chiamata col figlio sinistro di bruno (NULL).La chiamata per bruno viene anch'essa salavata sullo stack (sopra carlo quindi ne verrà estratta prima).La chiamata che gestisce il NULL figlio sinistro di Bruno ritorna subito perchè il controllo fallisce.Allora la chiamata che gestisce bruno viene ripescata dallo stack e si riparte da dove la si era lasciata esguendo la prossima istruzione (chhe stampa Bruno su schermo) e la successiva che è dinuovo una chiamata con argomento NULL e ritorna subito.Ora anche la chiamata a Bruno è finita e si torna ad eseguire la prossima istruzione di carlo (la pintf).Non credo ci sia bisogno di continuare, dovrebbe essere chiaro come si svolge il tutto.

[ipnotic]

grazie mille..... ora ho capito... cmq ora mi metto carta e penna e simulo lo stato dello stack passo per passo così sn sicuro ke capisco ancora meglio...


grazie mille dell'aiuto

[unomichisiada]

Originariamente inviato da ipnotic
grazie mille..... ora ho capito... cmq ora mi metto carta e penna e simulo lo stato dello stack passo per passo così sn sicuro ke capisco ancora meglio...


grazie mille dell'aiuto

Esatto è il modo migliore per capire.Non c'è niente di magico o misterioso nella ricorsione se hai capito come funziona uno stack.E se hai capito come vanno le cose ti rendi anche conto del perchè se possibile è meglio evitarla se è semplice trovare na soluzione iterativa :nonostante alcuni problemi si possano risolvere mooolto più semplicemente ricorsivamente che iterativamente in generale una soluzione ricorsiva consuma più risorse di calcolo e di memoria di una iterativa e va riservata a quei casi in cui il problema stesso diciamo così "si presta".