View Full Version : [C] Alberi binari e ricorsione. Come capirli?
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!
Leggi questa discussione e vedi se ti serve: http://www.hwupgrade.it/forum/showthread.php?t=2110523&highlight=condizione
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
10-02-2010, 16:03
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.
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 :asd:
peró almeno questo post ti avrá dato un punto di partenza per capire le funzioni ricorsive: studia l'induzione strutturale e le capirai perfettamente :)
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 :D la versione ricorsiva é 100 volte piu semplice).
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 :Puke:
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.
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?
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.
Sai fare una qualsiasi visita dell'albero (anticipata, simmetrica, posticipata) ? Mi immagino di sì. Quindi il problema è già risolto.
:help:
la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...
:help:
:help:
la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...
:help:
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? ;)
:help:
la funzione di ricerca nell'albero ce l'ho gia' fatta... e capita come funziona... ma da li a scriverla io...
:help:
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.
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.
,
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 ?
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).
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
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?
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.
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.
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.
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.
La funzione applicata al sottoalbero sinistro piu' quella al destro piu' l'eventuale 1 se c'e' l'elemento anche nel nodo in cui sono.
La funzione applicata al sottoalbero sinistro piu' quella al destro piu' l'eventuale 1 se c'e' l'elemento anche nel nodo in cui sono.
Ecco hai già finito la funzione ricorsiva :D
Rimetti tutto insieme e scrivila. Mi raccomando scrivi solo quello che hai detto ora.
salve ragazzi! sono alle prese con l'esame di programmazione I ad ingegneria informatica e mi trovo a dover risolvere lo stesso problema dell'utente precedente, cioè il conteggio dei livelli di un albero!
io avevo pensato di farla cosi
template <class T>
void Tree<T> :: aiuto_depth (TreeNode<T>* ptr, int &sin, int &des, int &n)
{
if (ptr == NULL) {
if (sin > des)
n = sin+1;
else
n = des+1;
}
else {
sin++;
aiuto_depth(ptr->leftPtr, sin, des, n);
des++;
aiuto_depth( ptr->rightPtr, sin, des, n);
}
}
in pratica questa è una funzione di servizio del template di classe Tree che prende come argomento un puntatore ad un nodo, e tre interi, i primi due per il conteggio temporaneo dei nodi visitati e l'ultimo per il conteggio finale. Ho pensato di fare tale funzione void e di aggiungere invece più parametri in modo da considerare i conteggi parziali. Questa funzione poi è utilizzata dal metodo pubblico
template <class T>
int Tree<T> :: depth ()
{
int n = 0, sin = 0, des = 0;
aiuto_depth (rootPtr, sin, des, n);
return n;
}
che restituisce il risultato. Il problema è che non funziona, cioè come risultato mi dà il numero di nodi presenti nell'albero, e non capisco il perchè! ah notate che se l'incremento sin++ e des++ vengono fatti prima delle chiamate ricorsive non cambia nulla. Mi potete dare una mano a svolgere questo algoritmo? visto che sto abbastanza in crisi in quanto l'ultimo appello non consegnai ma mi accorsi dopo che lo sapevo fare, e sto inveendo di brutto :D
vBulletin® v3.6.4, Copyright ©2000-2024, Jelsoft Enterprises Ltd.