albero

[DarkSepiroth]

Salve a tutti, ho un problema di programmazione in c.
l'esercizio è il seguente:
è dato un albero binario i cui nodi contengono valori interi positivi. Scrivere una funzione ricorsiva che dato il puntatore a un elemento di tipo albero 'a' e un valore intero positivo 'val' restituisce -1 se esiste almeno un sottoalbero di 'a' la cui somma degli elementi è pari a 'val' e restituisce un numero positivo altrimenti.

Qui c'è una bozza di quello a cui avevo pensato io:

int sottoalbero (*albero a, int val){

int somma1=0;
int somma2=0;

if(a->sin !=null){
somma1= somma1 + sottoalbero (a->sin, val - a->sin->valore);
if (somma1 ==val) return -1;
}

if(a->des!=null){
somma2= somma2 + sottoalbero (a->des, val - a->des->valore);
if (somma2 ==val) return -1;
}

if((somma1+somma2+a->val)==val) return -1;
return (somma1+somma2+a-val);

}


C'è però qualcosa che non torna. Qualcuno può indirizzarmi sulla strada giusta?

[MindFlyer]

C'è però qualcosa che non torna.

E ci credo, boia! Ma hai provato ad eseguire un debug o ad eseguirlo a mano su un caso semplice??
Finché usi le chiamate ricorsive a sottoalbero() nelle formule senza curarti del fatto che possono restituire -1, non può funzionare...
Inoltre è insensato passare "val - a->sin->valore" e simili a sottoalbero(), devi passargli sempre val!
Poi faresti meglio a cambiare questo: "return (somma1+somma2+a-val);" in questo: "return (somma1+somma2+a->val);".
Infine fai una serie di operazioni superflue, ma che non compromettono la correttezza.

[DarkSepiroth]

Mh, infatti quella era solo una bozza che in un primo tempo non riuscivo a correggere, non l'avevo implementata ma avevo problemi di 'costruzione' della logica della funzione
Anycase, nel frattempo ero arrivato alla versione giusta. Eccola.


struct nodo{
int val;
struct nodo *sin;
struct nodo *des;
};

int sottoalbero (*struct nodo r, int s){

int somma1=0;
int somma2=0;

if(r->sin !=null){ //esiste sottoalbero sinistro
somma1= sottoalbero (r->sin, s);
if (somma1 == -1) return -1;
}

if(r->des!=null){ // esiste sottoalbero destro
somma2= sottoalbero (r->des, s);
if (somma2 ==-1) return -1;
}

if((somma1+somma2+r->val)==s) return -1;
return (somma1+somma2+r->val);

}

[MindFlyer]

Ok, a parte un leggero errore di sintassi, l'algoritmo torna!