Baum (gerichteter azyklischer Graph) Umsetzung

Question

Ich benötige ein Baum / gerichtete azyklische Graph Umsetzung etwas wie folgt aus:

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

• Es gibt keine Sortierung aller Art.
• Die TreeNode ist nur ein Wrapper um den Schlüssel und einem möglichen Wert (Knoten müssen keine Werte festgelegt haben).
• Ich benötige Links sowohl für die Eltern und die Kinder.

Gibt es etwas, da draußen in den Standard-APIs oder Commons etc, dass dies für mich tun?

Ich habe nichts dagegen, es selbst nicht zu schreiben (und ich bin sicher nicht Sie Leute fragen nach) Ich will nur nicht, das Rad neu erfinden.

Answer 1

Es scheint nicht, etwas Derartiges zu sein. Ich fragte eine ähnliche Frage letzte Woche und am Ende meines eigenen Baum zu implementieren. Meine Implementierung war sehr ähnlich zu dem, was Sie vorschlagen:

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

In Kürze erhalten Sie haben einen Link zurück zu dem übergeordneten (n) hinzuzufügen.

Answer 2

Es gibt auch http://www.jgrapht.org , die Software unter der LGPL lizenziert. Ich muss Sie allerdings warnen, Ihre eigene Implementierung ist voller Gefahren. Wenn Sie sich mit Rekursion auf Ihrer Struktur planen (was ein Graph ist), müssen Sie sicherstellen, dass es azyklisch ist, oder Sie werden in Endlosschleife Probleme stoßen. Besser Code von Drittanbietern zu verwenden, wo sie bereits mit den behandelten Themen.

Answer 3

Ich würde sagen, es ist besser, eine eigene Implementierung, Roll-out (außer, haben Sie bereits bekam schön die Schnittstelle dacht). Was sind die Operationen, die Sie auf jeden Fall an diesem Baum auszuführen planen? Sie würden wahrscheinlich wollen Ihre API um die Dinge entwerfen Sie ... direkten Zugriff auf einzelne Knoten, die durch Schlüssel / Wert wollen? Arten von Traversierungen? Hinzufügen / Entfernen Operationen?

Answer 4

Wenn Sie suchen zusätzliche Graph-Funktionen, JDigraph 's Digraph Klasse sollte die Rechnung passen.