BinaryTree - cambiare il valore delle foglie

[stefano86]

Ciao a tutti, dovrei creare un metodo che, preso un albero binario t, cambi il contenuto delle foglie mettendo in esse la somma dei valori contenuti nei nodi del cammino dalla radice alla foglia stessa (incluso foglia e radice).
Ho scritto questo metodo ma quando lo eseguo va il loop e non capisco perchè..

void sumInLeaf(BinTree t) {
    sumLeaf(root, 0);
}


void sumInLeaf(BinTree t, int tot) {
    if(t.left == null && t.right == null)
        t.elem = tot;
    else {
        sumLeaf(t.left, tot + t.elem);
        sumLeaf(t.right, tot + t.elem);
    }
}

Qualcuno mi aiuta?

Grazie mille

[andbin]

Innanzitutto i nomi: io vedo che i due metodi invocano un sumLeaf ma non lo vedo .... vedo solo 2 sumInLeaf in overload.

Poi comunque se c'è solo un nodo figlio (in left O right) tu tenti la ricorsione su entrambi ma uno dei due è null quindi ti si schianta sicuramente da qualche parte.

E per finire, a rigor di logica e secondo quanto hai chiesto, dovresti partire passando t.elem ... non 0 (vuoi conteggiare la radice, giusto?) e idem per il elem delle foglie (che non stai conteggiando).

Pertanto rivedi bene il codice.

[stefano86]

Grazie per la risposta, ho modificato così:

void leafSum(BinTree t) {
	leafSumAus(t, t->elem);
}


void leafSumAus(BinTree t, int tot) {
	if(isLeaf(t)) { // se è una foglia
		printf("foglia\n");
		printf("tot: %s\n", tot);
		t->elem = tot;
	}
	else {
		printf("non foglia\n");
		if(t->left != NULL)
			leafSumAus(t->left, tot + t->elem);
		if(t->right != NULL)
		leafSumAus(t->right, tot + t->elem);
	}
}

Aggiungendo le stampe sembra che si pianti quando entra nel ramo if perchè non stampa mai "foglia" e va in loop...

[andbin]

Ma ... quello è c++ ... non Java!

E comunque invece di isLeaf(t) dovrebbe essere un metodo di istanza di BinTree, ovvero t.isLeaf() che è più object-oriented.

[stefano86]

Si scusa, ho cambiato linguaggio, ma il loop resta.. Tanto il ragionamento ricorsivo non cambia.. isLeaf funziona perchè testato

[stefano86]

Quindi? Non sono ancora riuscito a trovare una soluzione

[LeleFT]

Qui si parla di Java, quindi non ha senso "cambiare linguaggio in corsa".
Se hai deciso di sviluppare in C++, riapri una nuova discussione nel forum "Programmazione".
Se intendi proseguire con Java, posta qui sorgenti in Java... i miscugli non aiutano nessuno, men che meno te.


Ciao.

[stefano86]

Qui si parla di Java, quindi non ha senso "cambiare linguaggio in corsa".
Se hai deciso di sviluppare in C++, riapri una nuova discussione nel forum "Programmazione".
Se intendi proseguire con Java, posta qui sorgenti in Java... i miscugli non aiutano nessuno, men che meno te.


Ciao.

Ciao, pensavo non fosse un problema visto che per una funzione semplice come questa non cambia molto tra C e Java. Comunque chiedo scusa.
Non mi sembra il caso di aprire una nuova discussione uguale a questa quindi posto qui sotto il codice Java sperando in un vostro aiuto.

public void leafSum(BinTree t) {
	leafSumAus(t, t.elem);
}


private void leafSumAus(BinTree t, int tot) {
	if(isLeaf(t)) {
		t.elem = tot;
	}
	else {
		if(t.left != null)
			leafSumAus(t.left, tot + t.elem);
		if(t.right != null)
		leafSumAus(t.right, tot + t.elem);
	}
}

Il problema è che va in loop quando entra nel ramo if.
Grazie

[andbin]

Il problema è che va in loop quando entra nel ramo if.

Intanto .. quale dei 3 if?

Comunque il codice che hai postato, ad occhio, non mi pare sbagliato. Insomma, mi "quadra".

Ci sono solo due questioni:
1) cosa fa isLeaf? La implementazione è banale.
2) La struttura dell'albero è corretta cioè non è che per sbaglio ci sono ricircoli tra i nodi? Se ci fossero cicli ... ovvio che un metodo ricorsivo va in loop!

[stefano86]

Intanto .. quale dei 3 if?

Il primo, quello più esterno, quello che controlla se l'albero è una foglia.

1) cosa fa isLeaf? La implementazione è banale.

isLeaf è un semplice metodo che ritorna true se l'albero passato come parametro è una foglia (entrambi i sotto alberi figli sono nulli), false altrimenti.
isLeaf è stato testato e funziona.

2) La struttura dell'albero è corretta cioè non è che per sbaglio ci sono ricircoli tra i nodi? Se ci fossero cicli ... ovvio che un metodo ricorsivo va in loop!

No non è possibile ci siano cicli, è un albero binario quindi non possono esserci cicli. La struttura è corretta perchè ho fatto una sfilza di metodi su gli alberi binari e questo è l'unico che va in loop..