Ricorsione alberi

[Nikopol]

Grazie mille! Finalmente grazie a te sono riuscito a risolverlo.

Figurati!

Per quanto riguarda la somma degli elementi puoi vederla in questo modo:
cosa significa calcolare la somma degli elementi di un albero?
- caso base: se un albero ha un solo elemento (è una foglia) allora la somma equivale al valore della foglia
- caso ricorsivo: la somma degli elementi di un sottoalbero è il valore del nodo corrente più la somma dei valori calcolati nei sottoalberi del nodo corrente.

Quindi a ogni passo di ricorsione devi calcolare la somma dei sottoalberi, indipendentemente da quella che hai già calcolato.
Se invece passi ai sottoalberi la somma che hai gia calcolato (come stai facendo) finirai per calcolare il valore degli stessi nodi più volte.

//non passo più la somma come parametro
ppublic static int sum(Tree<Integer> t, Position<Integer> p) {
        if(t.isExternal(p))
            return p.element();
        if(t.isInternal(p)) {
            int somma = 0 // inizializzo qui la somma a zero 
            for(Position<Integer> i:t.children(p))
                somma = somma + p.element() + sum(t,i);//calcolo la somma solo dei sottoalberi
        }
        return somma;//la ricorsione penserà a fare via via tutte le somme dei sottoalberi mentre risalirà verso l'alto
    }

[Aleandro23]

Figurati!

Per quanto riguarda la somma degli elementi puoi vederla in questo modo:
cosa significa calcolare la somma degli elementi di un albero?
- caso base: se un albero ha un solo elemento (è una foglia) allora la somma equivale al valore della foglia
- caso ricorsivo: la somma degli elementi di un sottoalbero è il valore del nodo corrente più la somma dei valori calcolati nei sottoalberi del nodo corrente.

Quindi a ogni passo di ricorsione devi calcolare la somma dei sottoalberi, indipendentemente da quella che hai già calcolato.
Se invece passi ai sottoalberi la somma che hai gia calcolato (come stai facendo) finirai per calcolare il valore degli stessi nodi più volte.

//non passo più la somma come parametro
ppublic static int sum(Tree<Integer> t, Position<Integer> p) {
        if(t.isExternal(p))
            return p.element();
        if(t.isInternal(p)) {
            int somma = 0 // inizializzo qui la somma a zero 
            for(Position<Integer> i:t.children(p))
                somma = somma + p.element() + sum(t,i);//calcolo la somma solo dei sottoalberi
        }
        return somma;//la ricorsione penserà a fare via via tutte le somme dei sottoalberi mentre risalirà verso l'alto
    }

Grazie ancora! Grazie a te sto finalmente capendo la logica che c'è dietro la ricorsione .