[C++] Cammino Albero

[Tigre851]

la seguente funzione dovrebbe stabilire se esiste un cammino che ci permette di totalizzare un determinato punteggio... solo che non mi va...

la chiamata è la seguente:

bool esiste = esiste_cammino(tree,0,15);

mentre la funzione:

bool esiste_cammino(nodo *t,int tot,int punteggio){
	if (t == NULL){
		return false;
	}
	if (foglia(t) && tot==punteggio) return true;
		else return false;
	bool l = esiste_cammino(t->left,tot+t->info,punteggio);
	bool r = esiste_cammino(t->right,tot+t->info,punteggio);
	if ((l == true) || (r == true))
		return true;
	return false;
	
	}

grazie

[anx721]

L'errore sta nel fatto che chiami ricorsivamente la funzioen sui figli senza aver prima verificato se i figli esistono, causando un errore di memoria. Precisaemnte l'errore si ha nel caso in cui un nodo ha un solo figlio, in questo caso non è una foglia e quindi il secondo if non è eseguito e si passa alle chiamate ricorsive sui figli.

Una versione corretta è:

bool esiste_cammino(nodo *t,int tot,int punteggio){
	if (t == NULL){
		return false;
	}
	if (foglia(t) && tot==punteggio) return true;
		else return false;
	bool l = false, r = false;
        if(t->left)
              l = esiste_cammino(t->left,tot+t->info,punteggio);
	if(t->right)
               r = esiste_cammino(t->right,tot+t->info,punteggio);
	return l || r;
}

[Tigre851]

Grazie! ora funziona... avevo fatto anche un altro errore... tornavo false se tot era diverso dal punteggio senza controllare negli altri rami... grazie ancora ciao!

bool esiste_cammino(nodo *t,int tot,int punteggio){
	if (t == NULL){
		return false;
	}
	if (foglia(t) && tot==punteggio) return true;

	if (t->left!=NULL)
	return esiste_cammino(t->left,tot+t->info,punteggio);
	if (t->right !=NULL)
	return esiste_cammino(t->right,tot+t->info,punteggio);



	
	}

[anx721]

guarda che l'ultima versione che hai scritto no e corretta perche potrebbe non controllare il cammino sul figlio destro....

[Tigre851]

ok penso di aver capito anche il xchè... grazie...