funzioni per gestione albero ennario

[melmar20]

ciao a tutti, ho una struttura ad albero ennario e ho bisogno di alcune funzioni che calcolino il numero di foglie dell'albero, la profondità e il numero di nodi.

Ho fatto una ricerca ma non ho trovato niente di implementato.

Sapreste dirmi se c'è qualcosa che fa al caso mio e che ancora non sono riuscito a scovare???

[andbin]

Originariamente inviato da melmar20
ciao a tutti, ho una struttura ad albero ennario e ho bisogno di alcune funzioni che calcolino il numero di foglie dell'albero, la profondità e il numero di nodi.

Ho fatto una ricerca ma non ho trovato niente di implementato.

Sapreste dirmi se c'è qualcosa che fa al caso mio e che ancora non sono riuscito a scovare???

Non hai precisato cosa contiene il tuo albero, quali classi hai usato e quali metodi offrono (la sua API in pratica) ecc.... Insomma .. non hai precisato nulla.

Allora ecco un esempio pratico che ho buttato giù al volo:

import java.util.*;

public class TreeTest {
    public static void main(String[] args) {
        TreeNode<String> radice = new TreeNode<String>("Radice");
        TreeNode<String> a = new TreeNode<String>("A");
        TreeNode<String> b = new TreeNode<String>("B");
        TreeNode<String> c = new TreeNode<String>("C");
        TreeNode<String> d = new TreeNode<String>("D");
        TreeNode<String> e = new TreeNode<String>("E");
        TreeNode<String> f = new TreeNode<String>("F");
        TreeNode<String> g = new TreeNode<String>("G");

        radice.addChild(a);
        radice.addChild(b);
        radice.addChild(c);
        a.addChild(d);
        a.addChild(e);
        c.addChild(f);
        f.addChild(g);

        /*
                  Radice
                 /  |   \
                A   B    C
               / \        \
              D   E        F
                            \
                             G
        */

        System.out.println("numero foglie = " + numeroFoglie(radice));
    }

    public static int numeroFoglie(TreeNode<?> nodo) {
        if (nodo.getChildCount() == 0) {
            // È una foglia!
            return 1;
        } else {
            // Non è una foglia
            int count = 0;

            for (int i = 0; i < nodo.getChildCount(); i++) {
                count += numeroFoglie(nodo.getChild(i));
            }

            return count;
        }
    }
}


class TreeNode<E> {
    private E element;
    private ArrayList<TreeNode<E>> children;

    public TreeNode(E element) {
        this.element = element;
        children = new ArrayList<TreeNode<E>>();
    }

    public E getElement() {
        return element;
    }

    public int getChildCount() {
        return children.size();
    }

    public TreeNode<E> getChild(int index) {
        return children.get(index);
    }

    public void addChild(TreeNode<E> node) {
        children.add(node);
    }
}

Il programma stampa 4, che è il numero delle foglie (D E B G).
Come determinare le altre informazioni te lo lascio come esercizio .....

[melmar20]

ciao, grazie mille per i tuoi preziosissimi consigli. Io però per costruire il mio albero non ho utilizzato la classe TreeNode che mette a disposizione java, ma ho creato due classi :

-Nodo e Tree.

Nella classe Nodo ho gli attributi :

padre,succ,primoFiglio

Pertanto capisco se un nodo è una foglia quando primoFiglio == null .

Il problema che trovo nel codice che gentilmente mi hai postato è che non posso utilizzare il metodo getChildCount, per il motivo che ho detto sopra

[andbin]

Originariamente inviato da melmar20
Io però per costruire il mio albero non ho utilizzato la classe TreeNode che mette a disposizione java

Nemmeno io ho usato strutture "ad albero" già presenti nel framework!!!

Originariamente inviato da melmar20
ma ho creato due classi :

-Nodo e Tree.

Ok ... Nodo è concettualmente come mio TreeNode nell'esempio che ho fatto mentre Tree immagino che sia una semplice classe che ha come principale proprietà il nodo "radice". Ma questo cambia poco .....

Originariamente inviato da melmar20
Nella classe Nodo ho gli attributi :

padre,succ,primoFiglio

Pertanto capisco se un nodo è una foglia quando primoFiglio == null .

Il problema che trovo nel codice che gentilmente mi hai postato è che non posso utilizzare il metodo getChildCount, per il motivo che ho detto sopra

E allora?

a) Puoi determinare se il nodo è una foglia? (sì ... l'hai appena detto tu)
b) Puoi "iterare" sui figli di un nodo?

Se puoi fare queste cose, allora puoi scrivere un metodo numeroFoglie() concettualmente simile al mio ma ovviamente cambiando il modo di gestire i due punti che ho appena detto!