树（有向无环图）实现

Question

我需要一个树/有向无环图实现，如下所示：

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

• 没有任何类型的排序。
• 这 TreeNode 只是键和可能值的包装（节点不必设置值）。
• 我需要父母和孩子的链接。

标准 API 或 Commons 等中有什么可以为我做到这一点吗？

我不介意自己写（而且我当然 不是 请你们这样做）我只是不想重新发明轮子。

Answer 1

好像没有什么类似的事情。我问 类似的问题 上周并最终实现了我自己的树。我的实现与您的提议非常相似：

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

您必须添加返回父级的链接。

Answer 2

还有 http://www.jgrapht.org, ，其软件根据 LGPL 获得许可。但我必须警告你，实施你自己的方法充满了危险。如果您计划在结构（这是一个图）上使用递归，则必须确保它是非循环的，否则您将遇到无限循环问题。最好使用已经处理过问题的第三方代码。

Answer 3

我想说最好推出您自己的实现（此外，您已经精心设计了界面）。您打算对这棵树执行哪些操作？您可能希望围绕您想要的东西来设计您的 API...通过键/值直接访问各个节点？遍历的类型？添加/删除操作？

Answer 4

如果您正在寻找其他图形功能， J有向图的 有向图 类应该符合要求。