Java中的通用树实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1356401/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generic tree implementation in Java
提问by Ivan Koblik
Is anyone aware of a generic tree (nodes may have multiple children) implementation for Java? It should come from a well trusted source and must be fully tested.
有没有人知道 Java 的通用树（节点可能有多个子节点）实现？它应该来自一个值得信赖的来源，并且必须经过全面测试。
It just doesn't seem right implementing it myself. Almost reminds me of my university years when we were supposed to write all our collections ourselves.
自己实施它似乎并不正确。几乎让我想起了我的大学时代，当时我们应该自己写所有的收藏。
EDIT: Found this projecton java.net, might be worth looking into.
编辑：在 java.net 上找到这个项目，可能值得研究。
回答by Zed
Here it comes:
它来了：
abstract class TreeNode implements Iterable<TreeNode> {
private Set<TreeNode> children;
public TreeNode() {
children = new HashSet<TreeNode>();
}
public boolean addChild(TreeNode n) {
return children.add(n);
}
public boolean removeChild(TreeNode n) {
return children.remove(n);
}
public Iterator<TreeNode> iterator() {
return children.iterator();
}
}
I am well trusted, but haven't tested the implementation.
我很受信任，但尚未测试实施。
回答by Fortyrunner
There isn't a Tree class in the Collections libraries. However, there isone in the Swing Frameworks. DefaultTreeModel
Collections 库中没有 Tree 类。但是，有是一个在Swing框架。默认树模型
I have used this in the past and it works well. It does pull in additional classes into your application though which may or may not be desirable.
我过去使用过这个，效果很好。它确实将额外的类引入到您的应用程序中，尽管这可能是可取的，也可能是不可取的。
You can also simulate a Tree using another collection and storing collections in it. Eg. List of Lists.
您还可以使用另一个集合模拟树并将集合存储在其中。例如。列表列表。
回答by peter.murray.rust
I use an XML DOM (XML describes a tree structure) and specifically the Open Source XOM (http://www.xom.nu). This is lightweight, nodes can be subclassed if required and very highly used and tested. It may be larger than you require but it has the advantage that any tree navigation methods (ancestors, siblings, etc.) are fully managed through XPath. You can also serialize the tree and transform it by tested XML methods. There is also a strong user community
我使用 XML DOM（XML 描述树结构），特别是开源 XOM（http://www.xom.nu）。这是轻量级的，如果需要，可以对节点进行子类化，并且高度使用和测试。它可能比您需要的大，但它的优点是任何树导航方法（祖先、兄弟等）都可以通过 XPath 完全管理。您还可以序列化树并通过经过测试的 XML 方法对其进行转换。还有一个强大的用户社区
回答by OccludedInsight
I found an implementation of a Generic Tree (with tests) here:
我在这里找到了一个通用树（带测试）的实现：
http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/
http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/
I think this is what you are looking for.
我想这就是你要找的。
回答by Vivin Paliath
Ah, I was going to post a shameless plug to my solution and saw that someone already posted a link to it. Yeah, I had the same issue and I basically ended up writing my own Generic Tree. I've got tests for the tree node and the tree itself.
啊，我打算在我的解决方案中发布一个无耻的插件，但看到有人已经发布了一个链接。是的，我遇到了同样的问题，我基本上最终编写了自己的通用树。我对树节点和树本身进行了测试。
I implemented the node as an object having a data field and a list of nodes (which are the children of that node).
我将该节点实现为一个对象，该对象具有一个数据字段和一个节点列表（它们是该节点的子节点）。
回答by Ivan Koblik
I found an absolutely fantastic library http://jung.sourceforge.net, see the javadoc http://jung.sourceforge.net/doc/api/index.html. It is much more than just a graph implementation. With it you can visualize and layout graphs; plus, it has a bunch of standard graph algorithms you can use out of the box. Go, check it out!Although I ended up implementing my own basic graph (I didn't know of JUNG before), I use this library for visualization. It looks very neat!
我发现了一个非常棒的库http://jung.sourceforge.net，请参阅 javadoc http://jung.sourceforge.net/doc/api/index.html。它不仅仅是一个图形实现。有了它，您可以可视化和布局图形；另外，它有一堆标准的图形算法，你可以开箱即用。 去看看吧！虽然我最终实现了自己的基本图（我之前不知道 JUNG），但我使用这个库进行可视化。它看起来非常整洁！
回答by Lucas
It's rather hard to do a true generic tree implementation in Java that really separated the tree operations and properties from the underlying implementations, i.e. swap in a RedBlackTreeNode and override a couple of method to get a RedBlackTree implementation while retaining all the generic operations that a BinaryTree interface contains.
在 Java 中做一个真正的通用树实现是相当困难的，它真正将树操作和属性与底层实现分开，即交换一个 RedBlackTreeNode 并覆盖几个方法来获得 RedBlackTree 实现，同时保留 BinaryTree 的所有通用操作界面包含。
Also, an ideal abstraction would be able to swap out the low-level tree representation, e.g. an implicit binary tree structure stored in an array for a Heap or a Node-base interface with left and right child pointers, or multiple child pointers, or augmenting any of the above with parent pointers, or threading the leaf nodes, etc, etc, etc.
此外，理想的抽象将能够换出低级树表示，例如存储在数组中的隐式二叉树结构，用于带有左右子指针或多个子指针的堆或基于节点的接口，或用父指针增加上述任何一个，或线程化叶节点等，等等。
I did try and solve this myself, but ended up with quite a complicated interface that still enforces type safety. Here's the skeleton of the idea that sets up a abstract BinaryTree class with a non-trivial operation (Euler Tour) that will work even if the underlying node class or tree class is changed. It could probable be improved by introducing the idea of cursors for navigation and positions within the tree structure:
我确实尝试过自己解决这个问题，但最终得到了一个相当复杂的接口，它仍然强制执行类型安全。这是使用非平凡操作 (Euler Tour) 设置抽象 BinaryTree 类的想法的框架，即使底层节点类或树类发生更改，该类也能工作。可以通过在树结构中引入用于导航和位置的光标的想法来改进它：
public interface Tree<E, P extends Tree.Entry<E, P>> extends Collection<E>
{
public P getRoot();
public Collection<P> children(P v);
public E getValue(P v);
public static interface Entry<T, Q extends Entry<T, Q>> { }
}
public interface BinaryTree<E, P extends BinaryTree.Entry<E, P>> extends Tree<E, P>
{
public P leftChild(P v);
public P rightChild(P v);
public static interface Entry<T, Q extends Entry<T, Q>> extends Tree.Entry<T, Q>
{
public Q getLeft();
public Q getRight();
}
}
public interface TreeTraversalVisitor<E, P extends BinaryTree.Entry<E, P>, R>
{
public R visitLeft( BinaryTree<E, P> tree, P v, R result );
public R visitCenter( BinaryTree<E, P> tree, P v, R result );
public R visitRight( BinaryTree<E, P> tree, P v, R result );
}
public abstract class AbstractBinaryTree<E, P extends BinaryTree.Entry<E, P>> extends AbstractCollection<E> implements BinaryTree<E, P>
{
public Collection<P> children( P v )
{
Collection<P> c = new ArrayList<P>( 2 );
if ( hasLeft( v ))
c.add( v.getLeft());
if ( hasRight( v ))
c.add( v.getRight());
return c;
}
/**
* Performs an Euler Tour of the binary tree
*/
public static <R, E, P extends BinaryTree.Entry<E, P>>
R eulerTour( BinaryTree<E, P> tree, P v, TreeTraversalVisitor<E, P, R> visitor, R result )
{
if ( v == null )
return result;
result = visitor.visitLeft( tree, v, result );
if ( tree.hasLeft( v ))
result = eulerTour( tree, tree.leftChild( v ), visitor, result );
result = visitor.visitCenter( tree, v, result );
if ( tree.hasRight( v ))
result = eulerTour( tree, tree.rightChild( v ), visitor, result );
result = visitor.visitRight( tree, v, result );
return result;
}
}
回答by haylem
Use Guava
使用番石榴
Guava15.0introduces a nice API for tree traversal so you don't need to re-implement it for the gazillionth time in your codebase.
Guava 15.0为树遍历引入了一个很好的 API，因此您无需在代码库中无数次重新实现它。
Namely, TreeTraverserand some specialized implementations, like BinaryTreeTraverser.
也就是说，TreeTraverser还有一些专门的实现，比如BinaryTreeTraverser.
A very much welcome additionto avoid re-implementing something so simple and with added bonus:
一个非常受欢迎的补充，以避免重新实现如此简单的东西，并有额外的好处：
- with peace of mind (stability, supported library, etc...),
- good design,
- several traversal modes built-in.
- 安心（稳定性，支持的库等...），
- 好的设计，
- 内置多种遍历模式。
While You're There...
当你在那里时...
Notice that Guava also provides now new methods to its Filesutility class that make use of the TreeTraverser, e.g. Files.fileTreeTraverser()which gives you a TreeTraverser<File>for your file-system traversal needs.
请注意，Guava 现在还为其Files实用程序类提供了使用 的新方法TreeTraverser，例如Files.fileTreeTraverser()，它TreeTraverser<File>为您的文件系统遍历需求提供了 。
回答by mike
When in need of a tree I typically use following interface, and implement it accordingly.
当需要一棵树时，我通常使用以下接口，并相应地实现它。
/**
* Generic node interface
*
* @param <T> type of contained data
* @param <N> self-referential type boundary that captures the implementing type
*/
interface Node<T, N extends Node<T, N>>
{
public T getObject();
public boolean addChild(N node);
public List<N> getChildren();
}
An implementation could be
一个实现可能是
class StringNode implements Node<String, StringNode>
{
private final String value;
public StringNode(String value)
{
this.value = value;
}
@Override
public String getObject()
{
return value;
}
@Override
public boolean addChild(StringNode node)
{
// add child
return false;
}
@Override
public List<StringNode> getChildren()
{
// return children
return Collections.emptyList();
}
}
The advantage here is the flexibility gained by implementing algorithms against the interface. A rather simple example could be
这里的优势是通过针对接口实现算法而获得的灵活性。一个相当简单的例子可能是
public <T, N extends Node<T, ? extends N>> N performAlgorithm(N node)
{
if (!node.getChildren().isEmpty())
return node.getChildren().get(0);
return node;
}
The method can be used with the inteface type or concrete implementations
该方法可以与接口类型或具体实现一起使用
StringNode sn = new StringNode("0");
Node<String, StringNode> node = sn;
// perform computations on the interface type
Node<String, StringNode> result = performAlgorithm(node);
// or use a concrete implementation
StringNode result2 = performAlgorithm(sn);
