problemi ricorsione alberi binari

[miki miki]

sono alle prime armi con la programmazione in c e mi son imbattuto negli alberi binari.
ho trovato una funzione che ricerca un elemento e restituisce il puntatore che la punta:

tree trova ( tree t, Tipo d) {
tree temp;
if ( t == NULL || t->dato == d )
return t;
temp = trova( t->left );
if ( temp == NULL )
return trova( t->right );
else
return temp;
}

pero' non capisco come funziona la ricorsione!!
secondo me una volta chiamata per la prima volta trova con argomento al puntatore a sinistra non riesce piu' a cercare il sottoalbero a destra!!!

è sbagliato il programma? oppure mi sfugge qualcosa sulla ricorsione?
grazie in anticipo per chi mi vorrà rispondere.

[Alex'87]

Se intendi magari si capisce meglio...

tree trova (tree t, Tipo d) {
  tree temp;

  if (t == NULL || t->dato == d) {
    return t;
  }

  temp = trova(t->left);

  if (temp == NULL) {
    return trova(t->right);
  } else {
    return temp;
  }
}

Originariamente inviato da miki miki
pero' non capisco come funziona la ricorsione!!
secondo me una volta chiamata per la prima volta trova con argomento al puntatore a sinistra non riesce piu' a cercare il sottoalbero a destra!!!

Viene chiamato trova(t->left). Prima o poi però quel metodo restituirà il controllo e a quel punto si controlla se temp vale NULL ed eventualmente si chiama trova(t->right)...

[YuYevon]

L'algoritmo è corretto e di fatto è una visita pre-order dell'albero binario alla ricerca del dato (qui trovi un applet java che descrive i tre tipi di visita degli alberi binari).

In realtà c'è un errore... nelle chiamate ricorsive alla funzione trova() viene specificato solo il primo argomento e non il secondo (il dato) quindi è da riscrivere così:

tree trova (tree t, Tipo d) {
  tree temp;

  if (t == NULL || t->dato == d) {
    return t;
  }

  temp = trova(t->left, d);

  if (temp == NULL) {
    return trova(t->right, d);
  } else {
    return temp;
  }
}

Comunque la prossima volta specifica il linguaggio nel titolo del topic, oltre ad indentare il codice come ti diceva Alex.

[miki miki]

mi sembra di avere capito che in questo modo prima scandisce il sottoalbero sinistro e poi quello destro.
faccio un esempio:


quando la scansione arriva a 2(dopo essere passata da 3 e 4) prima controlla a sinistra e c'è null,allora fa trova->right e anche qui trova null!!! allora restituisce t...ma a questo punto t è il nodo che contiene 2 ed allora ripartirebbe a cercare trova t->left e ritroverebbe il null precedente...non riesco veramente a capire!!!...potreste spiegarmi in maniera piu' semplice
( scusate la banalità della domanda ma sono alle prime armi..)
credo che il mio problema stia nella ricorsione perchè la struttura binaria dell albero lo capita ed ho fatto esercizi sulle liste

                              3 
                          /       \ 
                        /           \ 
                      4               5 
                    /     \          /  \ 
                  2       9        _     1
                 /  \     /  \     -    /  \
                 _  _   _     3       _   _
                 -  -    -    / \      -   -
                             _   _
                             -   -

[Alex'87]

Originariamente inviato da miki miki

                              3 
                          /       \ 
                        /           \ 
                      4               5 
                    /     \          /  \ 
                  2       9        _     1
                 /  \     /  \     -    /  \
                 _  _   _    13       _   _
                 -  -    -    / \      -   -
                             _   _
                             -   -

Parti da 3, vai a sinistra e trovi 4. Da 4 vai a sinistra e trovi 2. Non ha figli, interrompi la discesa e si torna a livello di 4. Da qui va su 9. Da 9 vai a 13. Poi si torna su 9, non ha atlri figli e torni su 4, non ci sono altri figli vai su 3. Da 3 vai a destra su 5 e poi su 1.

[miki miki]

non riesco a capire come faccia a "risalire" i nodi senza riiniziare a scandire il nodo sinistro.
faccio un esempio: arriva al null destro di 2 la funzione poichè quel puntatore è null ridà t che è il nodo 4 a questo punto la prima istruzione del programma è:
temp = trova(t->left, d)...allora riscende a scandire 2!!!

il programma quando risale come fa a tornare alla radice e sapere che i nodi sottostanti li ha gia visti?

[Alex'87]

Originariamente inviato da miki miki
non riesco a capire come faccia a "risalire" i nodi senza riiniziare a scandire il nodo sinistro.
faccio un esempio: arriva al null destro di 2 la funzione poichè quel puntatore è null ridà t che è il nodo 4 a questo punto la prima istruzione del programma è:
temp = trova(t->left, d)...allora riscende a scandire 2!!!

???

Sei in 2 e vedi che a destra c'è NULL. La funzioni termina e restituisce il controllo a chi l'ha chiamata. Il chiamante si era interrotto sulla chiamata trova(t->right, d) e riprende da lì!

Originariamente inviato da miki miki
il programma quando risale come fa a tornare alla radice e sapere che i nodi sottostanti li ha gia visti?

La funzione è costruita in modo tale da scendere a sinistra (si fa PUSH) fino a che è possibile. Quando si incontra una foglia (nodo a NULL) si torna al nodo padre (si fa POP) e si esplora il nodo a destra (si ritorna a fare PUSH) che a sua volta viene esplorato a partire da sinistra... Hai presente come funziona la chiamata di una funzione?

[miki miki]

....ogni volta che c'è la chiamata ricorsiva alla funzione, la funzione chiama se stessa con i parametri attuali...ed ogni volta che ho il return restituisce il controllo al programma chiamante
non riesco a farti capire cosa non capisco, provo ad essere piu' chiaro


arriva a sinistra di 2,quindi temp=NULL alora ho: return trova(t->right) /*quindi ho la chiamata ricorsiva della funzione*/
allora inizio ad eseguire la funzione trova ma si verifica subito il primo if, poichè t=NULL che ritorna t; cioè a4...ma a questo punto trovo temp=trova(t->left) quindi riscenderei a 2....


ho capito che sbaglio ma non riesco a capire perchè e dove!
TU DICI
La funzioni termina e restituisce il controllo a chi l'ha chiamata. Il chiamante si era interrotto sulla chiamata trova(t->right, d) e riprende da lì!

COSA VUOL DIRE CHE RIPRENDE DA LI?


grazie per l'aiuto.

[miki miki]

HO CAPITO!!!

Mi son spaccato la testa ma ce l'ho fatta!! il mio problema è la ricorsione...non avevo capito che la prima chiamata ricorsiva si concludeva solo dopo che tutte le successive venivano eseguite!! io invece credevo che dopo la prima chiamata non dovesse piu' aspettare la risposta.
il nodo con tre chiama trova su 4 a sua volta lo chiama su 2, torna a 4 che non puo' ancora dare il suo return perchè deve scandire il suo sottoalbero destro e cosi via....

...prima fa tutte le chiamate e poi a ritroso da' le risposte....scusa per questo linguaggio poco professionale...

mi sembra d' aver capito...confermi??

grazie

[miki miki]

ora pero' sorge un problema...come posso vedere se due alberi sono uguali.....dovrei fare una doppia scansione contemporanea...