Java中的通用树实现

Question

是否有人知道Java的通用树(节点可能有多个子节点)实现？它应该来自一个值得信赖的来源,必须经过全面测试.

它本身似乎没有正确实现它.几乎让我想起我的大学时代,我们应该自己写完所有藏品.

编辑:在java.net上找到这个项目,可能值得研究.

Answer 1

它来了:

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

我很信任,但尚未测试实施.

Answer 2

使用番石榴

Guava 15.0为树遍历引入了一个很好的API,所以你不需要在代码库中的第几个时间重新实现它.

即,TreeTraverser和一些专门的实现,如BinaryTreeTraverser.

非常受欢迎的补充,以避免重新实现这么简单的事情和额外的奖励:

• 安心,稳定,支持图书馆等......,
• 好的设计,
• 内置了几种遍历模式.

当你在那里......

请注意,Guava现在还为其Files实用程序类提供了使用的新方法TreeTraverser,例如Files.fileTreeTraverser(),它可以满足您的TreeTraverser<File>文件系统遍历需求.

Answer 3

Collections库中没有Tree类.但是,有是一个在Swing框架.DefaultTreeModel的

我过去曾经使用过它,效果很好.它会在您的应用程序中引入其他类,尽管这可能是也可能不是.

您还可以使用另一个集合模拟树并在其中存储集合.例如.列表清单.

Answer 4

在Java中实现真正的通用树实现相当困难,它实际上将树操作和属性与底层实现分开,即交换RedBlackTreeNode并覆盖几个方法以获得RedBlackTree实现,同时保留BinaryTree的所有泛型操作界面包含.

此外,理想的抽象将能够交换低级树表示,例如存储在数组中的隐式二叉树结构,用于具有左右子指针的Heap或Node-base接口,或者多个子指针,或者使用父指针扩充上述任何一个,或者对叶子节点等进行线程处理等.

我确实试过自己解决这个问题,但结果却是一个非常复杂的界面,它仍然强制实现类型安全.这是一个概念的框架,它设置了一个带有非平凡操作(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;
   }    
}

Answer 5

啊,我打算在我的解决方案上发布一个无耻的插件,看到有人已经发布了一个链接.是的,我有同样的问题,我基本上最终编写了自己的通用树.我已经测试了树节点和树本身.

我将节点实现为具有数据字段和节点列表(该节点的子节点)的对象.

http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/

Answer 6

我在这里找到了一个Generic Tree(带有测试)的实现:

http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/

我想这就是你要找的东西.