Ricorsione alberi

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