[C] Alberi binari e ricorsione. Come capirli?

[xxxyyy]

Ciao,
allora... i problemi sono iniziati col meccanismo della ricorsione.
Qunado e' semplice semplice, nessun problema.
Ma quando si complica un po' devo "spaccarmi" la testa per per capirci qualcosa... figuriamoci se devo scrivere un programma...

Mi consigliate come/dove imparare bene questo metodo?

No perche' piu' o meno ero a posto cosi'... non devo diventare un genio della programmazione... ma poi sono arrivati sti maledetti alberi binari che bisogna trattarli per forza con la ricorsione.

Ed ecco la seconda domanda: come/dove imparo bene a districarmi ricorsivamentio tra gli alberi?

Grazie!

[cionci]

Leggi questa discussione e vedi se ti serve: http://www.hwupgrade.it/forum/showth...ght=condizione

[WarDuck]

La ricorsione non è un concetto immediatamente comprensibile, ma non è neanche impossibile.

La ricorsione prevede:

PASSO BASE: quando bisogna fermarsi.

PASSO RICORSIVO: richiamare la stessa funzione con un nuovo argomento che dipende dal precedente (non è sempre vero se operi su dati esterni alla funzione stessa).

Ad esempio per il calcolo del massimo comun divisore, applicando l'algoritmo di euclide:

int gcd(x, y) {
if (x==y) return x; // passo base
if (x>y) return gcd(x-y, y); // passo ricorsivo
if (x<y) return gcd(x, y-x); // passo ricorsivo
}

Innanzitutto devi pensare a quando devi fermarti.

Un algoritmo di visita in profondità per un albero binario è il seguente:

deep(node n) {
if (n==null) return; // passo base, se il nodo da visitare è nullo termina
print n; // stampa nodo visitato
deep(n.left); // visita nodo sinistro
deep(n.right); // visita nodo destro
}

Facciamo un esempio con qualche nodo:

NODO A
NODO B
NODO C
NODO D

A.RIGHT = B
B.LEFT = D
B.RIGHT = C

E' un albero sbilanciato sulla destra:
A
\
B
/ \
D C

Chiamo deep(A):

Visito A
Visito A.LEFT => null
Visito A.RIGHT => B
Visito B.LEFT => D
Visito D.LEFT => null
Visito D.RIGHT => null
Visito B.RIGHT, => C
Visito C.LEFT => null
Visito C.RIGHT => null

Per capire perché opera in questo modo devi tenere presente che la struttura dati implicita nella ricorsione è una pila (o stack).

Immagina una pila di piatti, dove l'ultimo piatto che metti è il primo che puoi togliere.

Ad ogni visita che fai metti nello stack i nodi figli dopodiché questi vengono estratti uno alla volta e visitati.

Naturalmente man mano che visiti possono essere aggiunti nuovi nodi nello stack, per cui è possibile che se hai molti nodi sinistri passi del tempo prima di visitare i sotto-alberi destri.

Lo so l'ho spiegato male... spero che qualcosa risulti comprensibile.

[wingman87]

Il mio consiglio per scrivere una funzione ricorsiva sugli alberi è rifarsi sempre al principio di induzione strutturale: distinguere e risolvere il caso base (albero vuoto) e il caso generico (albero non vuoto) sapendo che le eventuali chiamate ricorsive restituiranno un risultato corretto.

[fero86]

Originariamente inviato da wingman87

Il mio consiglio per scrivere una funzione ricorsiva sugli alberi è rifarsi sempre al principio di induzione strutturale:

esatto: quotone!!
c'é chi dice (non in questo thread, in generale) che le funzioni ricorsive sono quelle che chiamano se stesse, ma é sbagliatissimo. un algoritmo ricorsivo é un algoritmo che é possibile definire induttivamente, e si parla di induzione strutturale di cui l'induzione matematica é un caso particolare. in particolare non é detto che ci sia un solo caso base e un solo caso induttivo: quando si fa induzione strutturale in generale ci sono tanti casi base e tanti casi induttivi.

definire funzioni ricorsive sugli alberi binari é facilissimo se li si pensa come elementi di un insieme definito per induzione strutturale. una definizione induttiva degll'insieme degli alberi binari tipicamente avrá un costruttore per il caso base che sará solo una funzione che spara un nodo, e un costruttore per il caso induttivo che sará una funzione che presi due alberi ne produce un altro attaccandoli come figli di un nuovo nodo.

essendoci due costruttori tu, nel definire induttivamente funzioni ricorsive, devi porti solamente due domande:
1) cosa faccio nel caso rappresentato dal primo costruttore?
2) cosa faccio nel caso rappresentato dal secondo costruttore?

traduzione:
1) cosa faccio nel caso particolare in cui come albero mi arriva solamente un nodo senza figli?
2) cosa faccio altrimenti in generale?

ovviamente devi considerare prima i casi base e poi quelli induttivi.

se non sai cos'é l'induzione strutturale probabilmente non avrai capito niente
peró almeno questo post ti avrá dato un punto di partenza per capire le funzioni ricorsive: studia l'induzione strutturale e le capirai perfettamente

[fero86]

tra l'altro chi l'ha detto che gli alberi binari vanno trattati con la ricorsione?

in programmazione funzionale si parla di tail-call optimization, un'ottimizzazione che permette di convertire algoritmi ricorsivi di un certo tipo in algoritmi iterativi. in genere gli algoritmi sugli alberi binari possono essere convertiti in algoritmi iterativi. per esempio é possibile visitare iterativamente un albero binario (scusa se non ti scrivo il codice di esempio ma é troppo complicato la versione ricorsiva é 100 volte piu semplice).

[fero86]

comunque cambia il titolo: il C non c'entra niente con questi argomenti, lascia perdere il fatto che qualche troglodita all'universitá te li sta facendo studiare utilizzando il C

puoi lasciare il subject senza alcun tag, se cionci mi conferma: l'uso tag é stato introdotto in questa sezione per quegli utenti che credono che nell'universo esiste solo quello che fanno loro e se ne escono con 2 pagine di supercazzola pretendendo un universo di aiuti e una soluzione istantanea ad un problema tecnico molto specifico di una sola piattaforma senza aver neanche specificato la piattaforma. questa invece é una questione teorica, addirittura uno dei pilastri portanti dell'informatica.

[xxxyyy]

Hummm...

vi scrivo un esempio "trovare la profondita' di un abero binario":

typedef struct NodoAlbero {
Tipo dato;
struct NodoAlbero *left;
struct NodoAlbero *right;
} nodo;
typedef nodo *tree;

int depth ( tree t )
{
int D, S;
if (t == NULL)
return 0;
S = depth( t->left );
D = depth( t->right );
if ( S > D )
return S + 1;
else
return D + 1;
}

Come si fa ad arrivare al ragionamento induttivo? La condizione base, perche' non si metta, ad esempio, anche:

if t->left==NULL && t->right==NULL return 1?

Fini a dove si deve arrivare aspecificare le condizioni base?

Un programma che non riesco proprio a fare e' "sapere se due alberi binari contengono gli stessi elementi (trascurando le ripetizioni)" (alberi ovviamente con numero di nodi differenti, in generale)
Come (diavolo) di fa?

[cionci]

Puoi mettere anche:

if(t->left==NULL && t->right==NULL) return 1;

Ha perfettamente senso.
Però devi gestire anche il caso dell'albero vuoto (passo 0 del ragionamento induttivo), quindi quella sopra te la puoi risparmiare perché comunque quando depth verrà richiamata su t->left e t->right tornerebbe zero e di fatto la funzione avrebbe comunque 1 come valore di ritorno.
Ci sono anche casi in cui la condizione di arresto è molto più complicata. Non sempre è semplice come quella sopra.

Inoltre la funzione sopra ti dovrebbe ritornare almeno un warning perché manca il return in fondo alla funzione (anche se non verrà mai raggiunto).

if ( S > D )
   return S + 1;

return D + 1;

Secondo me l'ultimo quesito ha non c'entra niente con la ricorsione (o meglio c'entra solo di riflesso).
Sai ricercare un elemento all'interno di un albero ? Mi immagino di sì. Sai fare una qualsiasi visita dell'albero (anticipata, simmetrica, posticipata) ? Mi immagino di sì. Quindi il problema è già risolto.
Ogni volta in cui ti trovi in un nodo non NULL, fai una ricerca sull'altro albero. Se non l'elemento non viene trovato allora ritorni false e termini la visita.

[xxxyyy]

Originariamente inviato da cionci

Sai fare una qualsiasi visita dell'albero (anticipata, simmetrica, posticipata) ? Mi immagino di sì. Quindi il problema è già risolto.

la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...

[WarDuck]

Originariamente inviato da xxxyyy

la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...

Qual è la condizione base per cui è elementare la soluzione del problema?

Come ha detto cionci è l'albero vuoto. Ragiona su questo.

L'albero vuoto che profondità ha?

[cionci]

Originariamente inviato da xxxyyy

la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...

Scrivimi questa:
trovare quante volte un dato valore è ripetuto all'interno dell'albero.

Descrivimi a parole il ragionamento (prima di scrivere qualsiasi codice).
Ricordati di analizzare: passo 0, passo 1 e passo N. Al pari di una dimostrazione per induzione.

[xxxyyy]

Originariamente inviato da cionci

Scrivimi questa:
trovare quante volte un dato valore è ripetuto all'interno dell'albero.

Descrivimi a parole il ragionamento (prima di scrivere qualsiasi codice).
Ricordati di analizzare: passo 0, passo 1 e passo N. Al pari di una dimostrazione per induzione.

Se non c'e albero, 0.
Se c'e' solo la radice, 1.
E poi?
Vado a sinistra... e tengo la somma incrementando una variabile quando trovo l'elemento, se no vado a destra e faccio la stessa cosa.
Alla fini ritorno la variabile.







,

[cionci]

Il passo N esprimilo sotto forma di formula. f(p, v) è la funzione e p è il puntatore, v è il valore da cercare.

Il passo 1 non mi torna (stai attento perché non sempre il passo 1 va espresso in codice). Perché ritorni 1 ?

[xxxyyy]

Originariamente inviato da cionci

Il passo N esprimilo sotto forma di formula. f(p, v) è la funzione e p è il puntatore, v è il valore da cercare.

Il passo 1 non mi torna (stai attento perché non sempre il passo 1 va espresso in codice). Perché ritorni 1 ?

Ritorno 1 perche' se c'e' solo un elemento nell'albero... c'e' solo lui e il risultato e' 1.

Non saprei proprio da dove incominciare per fare il passo generico...

PS: la funzione che mi cerca un elemento nell'albero la so fare (nel senso che ce l'ho gia' fatta e ho capito piu' o meno come funziona).

[cionci]

Originariamente inviato da xxxyyy

Ritorno 1 perche' se c'e' solo un elemento nell'albero... c'e' solo lui e il risultato e' 1.

E chi ti dice che sia l'elemento che stavi cercando ?
Devi analizza i dati che hai a disposizione al passo generico:
- il valore del nodo corrente
- il numero di ricorrenze nel sotto albero destro (dando per scontato che il valore ritornato sia corretto, così come si fa nelle dimostrazioni per induzione al passo generico)
- il numero di ricorrenze nel sotto albero sinistro

[xxxyyy]

No aspetta... non stavamo facendo la funzione che mi diceva quante volte un elemento e' ripetuto in un albero?

Comunque, a me servirebbe capire questo:
Ho la funzione che mi dice se un elemento particolare c'e' o non c'e' in un albero.

Se l'albero sinistro e' vuoto, e quello destro pure, ritorno 1, sono uguali.
Se il sinistro e' vuoto e il destro no, ritorno 0.

Ora mi metto sul primo elemento dell'albero sinistro (la radice) e controllo che ci sia nel destro. Se c'e', 1. Se non c'e', 0.

Adesso come faccio a controllare, a fissare, gli altri elementi dell'albero sinistro e farli passare tutti? e farli controllare tutti con quelli dell'albero destro?

[cionci]

Originariamente inviato da xxxyyy

No aspetta... non stavamo facendo la funzione che mi diceva quante volte un elemento e' ripetuto in un albero?

Sì appunto.
Continuiamo un secondo con questa.

[xxxyyy]

Be', allora, se l'elemnto non e' quello cercato, ritorno 0.
Se e' quello cercato, 1.
Parlo sempre della radice dell'albero.
Il passo successivo?
Potrei cercarlo sul ramo sinistro e se lol trovo incremento una variabile contatore.
Poi sul destro.
E poi ritorno questa varabile contatore.

[cionci]

Assumiamo che la funzione ritorni correttamente il numero di ricorrenze in un albero.

Non pensare al passo successivo pensa al passo generico in cui tu hai a disposizione solamente il nodo corrente.
Dal punto di vista logico quante saranno le occorrenze in un albero composto dal nodo corrente e dai suoi due sottoalberi siniistro e destro.