Implementazione dell'albero (grafico aciclico diretto)

Question

Ho bisogno di un albero / implementazione grafica aciclica diretta qualcosa del genere:

public class TreeNode<K, V> {
    private K key; // 'key' for this node, always present
    private V value; // 'value' for this node, doesn't have to be set

    private TreeNode<K, V> parent;
    private Set<TreeNode<K, V>> children; 
}

• Non esiste alcun ordinamento di alcun tipo.
• Il TreeNode è solo un wrapper attorno alla chiave e un possibile valore (i nodi non devono avere valori impostati).
• Ho bisogno di collegamenti sia con il genitore che con i figli.

Esiste qualcosa nelle API standard, nei Commons ecc. che lo farà per me?

Non mi dispiace scriverlo da solo (e certamente non chiedo a te di farlo) non voglio reinventare la ruota.

Answer 1

Non sembra esserci nulla del genere. Ho fatto a una domanda simile la settimana scorsa e ho finito per implementare il mio albero. La mia implementazione è stata molto simile a quella che stai proponendo:

public class TreeNode<T>
{
    private LinkedList<TreeNode<T>> children = new LinkedList<TreeNode<T>>();
    public T value { get; set; }

    public TreeNode(T value)
    {
        this.value = value;
    }
    public LinkedList<TreeNode<T>> GetChildren()
    {
        return children;
    }
}

Dovrai aggiungere un link ai genitori.

Answer 2

Esiste anche http://www.jgrapht.org , che dispone di software concesso in licenza ai sensi della LGPL. Devo avvertirti però, implementare il tuo è pieno di pericoli. Se prevedi di utilizzare la ricorsione sulla tua struttura (che è un grafico), dovrai assicurarti che sia aciclico o incorrerai in infiniti problemi di loop. Meglio usare codice di terze parti in cui hanno già affrontato i problemi.

Answer 3

Direi che è meglio implementare la tua implementazione (inoltre, hai già l'interfaccia ben pensata). Quali sono le operazioni che prevedi di eseguire su questo albero? Probabilmente vorresti progettare la tua API attorno alle cose che desideri ... accesso diretto ai singoli nodi per chiave / valore? tipi di attraversamenti? aggiungere / rimuovere operazioni?

Answer 4

Se stai cercando funzionalità grafiche aggiuntive, JDigraph ' Digraph dovrebbe rientrare nel conto.