Ricorsione alberi

[Aleandro23]

Salve, io devo fare un esercizio sugli alberi:"Scrivere la funzione public static <E>boolean isContained(Tree<E> T, E x)
che restituisce true se e solo se x contenuto in qualche nodo dell�albero."
Premetto che io e la ricorsione siamo 2 cose distinte e separate, non riesco a capire una cosa. Quando il programma va a effettuare la ricorsione, restituisce tanti false e un true quando trova l'elemento. Come posso fare in modo che il programma restituisca true? Grazie a tutti!

    public static <E> boolean isContained(Tree<E> t, E x) {       
         if(t.isEmpty()){
            throw new EmptyTreeException("L'albero è vuoto.");
        }
        return find(t,t.root(),x);
        
    }


    public static <E> boolean find(Tree<E> t, Position<E> p, E x) {
        System.out.println(p.element());
        if(p.element().equals(x)) {
            return true;
        } else {
            if(!p.element().equals(x) && t.isInternal(p)) {
                for(Position<E> i: t.children(p)) {
                    find(t,i,x);
                }
            }
            return false;
        }
    }

[Aleandro23]

Nessuno lo sa?

[Nikopol]

Ciao, non conoscendo esattamente la struttura dell'albero posso solo mostrarti con dello pseudocodice come potresti risolvere il problema, poi sta a te implementarlo in Java:

     boolean isContained(Tree t, Elememt x) {       
        return find(t.root(),x);
        
    }
    boolean find(Node n, Element x){
        se n è una foglia allora restituisci n uguale x    
        altrimenti per ogni figlio f del nodo n
           se find(f,x) è uguale a true allora restituisci true
        restituisci false //non hai trovato alcun nodo uguale a x      
    }

[Aleandro23]

Ciao, non conoscendo esattamente la struttura dell'albero posso solo mostrarti con dello pseudocodice come potresti risolvere il problema, poi sta a te implementarlo in Java:

     boolean isContained(Tree t, Elememt x) {       
        return find(t.root(),x);
        
    }
    boolean find(Node n, Element x){
        se n è una foglia allora restituisci n uguale x    
        altrimenti per ogni figlio f del nodo n
           se find(f,x) è uguale a true allora restituisci true
        restituisci false //non hai trovato alcun nodo uguale a x      
    }

Grazie mille! Finalmente grazie a te sono riuscito a risolverlo. Ho un'altra domanda: come posso effettuare la somma degli elementi di un albero? L'esercizio in particolare è questo: "Scrivere la funzione public static int sumAllNodes(Tree<Integer> T)
che restituisce la somma di tutti gli elementi dell’albero."
Il mio codice è questo:

public static int sumAllNodes(Tree<Integer> t) {
        if(t.isEmpty()) throw new EmptyTreeException("L'albero è vuoto");
        int somma = 0;
        return sum(t,somma,t.root());
    }
    
    public static int sum(Tree<Integer> t, int somma, Position<Integer> p) {
        if(t.isExternal(p))
            return p.element();
        if(t.isInternal(p)) {
            for(Position<Integer> i:t.children(p))
                somma = somma + p.element() + sum(t,somma,i);
        }
        return somma;
    }

Fino ad una certa iterazione restituisce il valore corretto, ma poi inizia a restituire valori sballati; probabilmente calcola più volte gli stessi nodi, ma non so come fare .
Ti lascio la lista dei metodi dell'interfaccia Tree, ma puoi scrivermi anche lo pseudocodice come prima.

    /** Restituisce il numero di nodi dell'albero. */
    public int size();
    /** Restituisce un valore che specifica se l'albero è vuoto. */
    public boolean isEmpty();
    
    
    
    /** Restituisce una lista iterabile dei nodi memorizzati nell'albero. */
    public Iterable<Position<E>> positions();
    
    /** Sostituisce l'elemento memorizzato nel nodo v con e. */
    public E replace(Position<E> v, E e) throws InvalidPositionException;
    
    
    /** Restituisce la radice dell'albero. */
    public Position<E> root() throws EmptyTreeException;
    /** Restituisce il padre di u n determinato nodo. */
    public Position<E> parent(Position<E> v) throws InvalidPositionException, BoundaryViolationException;
    /** Restituisce una lista iterabile dei figli di un nodo. */
    public Iterable<Position<E>> children(Position<E> v) throws InvalidPositionException;
    
    
    /** Restituisce un valore che specifica se u n dato nodo è interno. */
    public boolean isInternal(Position<E> v) throws InvalidPositionException;
    /** Restituisce un valore che specifica se u n dato nodo è esterno. */
    public boolean isExternal(Position<E> v) throws InvalidPositionException;
    /** Restituisce un valore che specifica se u n dato nodo è la radice dell'albero. */
    public boolean isRoot(Position<E> v) throws InvalidPositionException;

[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 .

[Nikopol]

Di niente