java 树（有向无环图）实现

Tree (directed acyclic graph) implementation

提问by SCdF

I require a tree / directed acyclic graph implementation something like this:

我需要一个树/有向无环图实现是这样的：

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

• There is no sorting of any kind.
• The TreeNodeis just a wrapper around the key and a possible value (nodes don't have to have values set).
• I require links to both the parent and the children.

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

Is there anything out there in the standard APIs or Commons etc that will do this for me?

标准 API 或 Commons 等中有什么东西可以为我做这件事吗？

I don't mind writing it myself (and I'm certainly notasking you folks to) I just don't want to re-invent the wheel.

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

采纳答案by stimms

There doesn't seem to be anything of the kind. I asked a similar questionlast week and ended up implementing my own tree. My implementation was very similar to what you're proposing:

似乎没有这样的东西。上周我问了一个类似的问题，最终实现了我自己的树。我的实现与您提出的非常相似：

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

You will have to add a link back to the parent(s).

您必须添加一个链接回父级。

回答by user10536

There's also http://www.jgrapht.org, which has software licensed under the LGPL. I have to warn you though, implementing your own is fraught with danger. If you plan on using recursion on your structure (which is a graph), you'll have to ensure that it's acyclic, or you'll run into infinite loop problems. Better to use third party code where they've already dealt with the issues.

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

回答by Zach Scrivena

I'd say it's better to roll out your own implementation (besides, you've already got the interface nicely thought out). What are the operations you are planning to perform on this tree anyway? You'd probably want to design your API around the things you want... direct access to individual nodes by key/value? types of traversals? add/remove operations?

我会说最好推出你自己的实现（此外，你已经很好地考虑了接口）。无论如何，您计划在这棵树上执行哪些操作？您可能希望围绕您想要的东西设计 API……通过键/值直接访问单个节点？遍历的类型？添加/删除操作？

回答by flicken

If you're looking for additional graph capabilities, JDigraph's Digraphclass should fit the bill.

如果您正在寻找额外的图形功能，JDigraph的有向图类应符合要求。