Вот оно:

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

Мне доверяют, но я не проверял реализацию.

В библиотеках коллекций нет класса Tree. Однако в Swing Frameworks он есть. DefaultTreeModel

Я использовал это в прошлом, и это работает хорошо. Он включает дополнительные классы в ваше приложение, хотя это может быть или не быть желательным.

Вы также можете смоделировать дерево, используя другую коллекцию и сохраняя в ней коллекции. Например. Список списков.

Используйте гуаву

Гуава 15.0 представлен удобный API для обхода дерева, поэтому вам не нужно в тысячу раз заново реализовывать его в кодовой базе.

А именно, TreeTraverser и некоторые специализированные реализации, такие как BinaryTreeTraverser.

Очень желательно дополнение, чтобы избежать повторной реализации чего-то такого простого и с дополнительным бонусом:

• с душевным спокойствием (стабильность, поддерживаемая библиотека и т. д.),
• хороший дизайн,
• несколько встроенных режимов обхода.

Пока ты там...

Обратите внимание, что Guava теперь также предоставляет новые методы для своего вспомогательного класса Files, которые используют TreeTraverser, например. Files.fileTreeTraverser()< /a>, который дает вам TreeTraverser<File> для ваших нужд обхода файловой системы.

Довольно сложно сделать на Java настоящую реализацию универсального дерева, которая действительно отделяла бы операции и свойства дерева от базовых реализаций, т. е. заменяла RedBlackTreeNode и переопределяла пару методов, чтобы получить реализацию RedBlackTree, сохраняя при этом все общие операции, которые выполняет BinaryTree. интерфейс содержит.

Кроме того, идеальная абстракция могла бы заменить низкоуровневое представление дерева, например. неявная двоичная древовидная структура, хранящаяся в массиве для кучи или базового интерфейса узла с левыми и правыми дочерними указателями или несколькими дочерними указателями, или дополнение любого из вышеперечисленного родительскими указателями, или потоки конечных узлов и т. д. и т. д., и Т. Д.

Я пытался решить эту проблему сам, но в итоге получил довольно сложный интерфейс, который по-прежнему обеспечивает безопасность типов. Вот основа идеи создания абстрактного класса BinaryTree с нетривиальной операцией (Euler Tour), которая будет работать, даже если базовый класс узла или класс дерева изменен. Вероятно, его можно было бы улучшить, представив идею курсоров для навигации и позиций в древовидной структуре:

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

А, я собирался выложить беспардонный плагин к своему решению и увидел, что кто-то уже разместил ссылку на него. Да, у меня была та же проблема, и в итоге я написал свое собственное Generic Tree. У меня есть тесты для узла дерева и самого дерева.

Я реализовал узел как объект, имеющий поле данных и список узлов (которые являются дочерними элементами этого узла).

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

Я нашел реализацию Generic Tree (с тестами) здесь:

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

Я думаю, это то, что вы ищете.

Я нашел совершенно фантастическую библиотеку http://jung.sourceforge.net, см. javadoc http://jung.sourceforge.net/doc/api/index.html . Это гораздо больше, чем просто реализация графа. С его помощью вы можете визуализировать и раскладывать графики; плюс, у него есть набор стандартных графических алгоритмов, которые вы можете использовать из коробки. Иди, посмотри! Хотя в итоге я реализовал свой собственный базовый граф (раньше я не знал о JUNG), я использую эту библиотеку для визуализации. Выглядит очень аккуратно!

Я использую XML DOM (XML описывает древовидную структуру) и, в частности, XOM с открытым исходным кодом (http://www.xom.nu ). Это легкий, узлы могут быть подклассифицированы, если это необходимо, и очень часто используется и тестируется. Он может быть больше, чем вам нужно, но у него есть то преимущество, что любые методы навигации по дереву (предки, братья и сестры и т. д.) полностью управляются через XPath. Вы также можете сериализовать дерево и преобразовать его проверенными методами XML. Существует также сильное сообщество пользователей

Когда мне нужно дерево, я обычно использую следующий интерфейс и реализую его соответствующим образом.

  /**
   * 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();

  }

Реализация может быть

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

  }

Преимуществом здесь является гибкость, получаемая за счет реализации алгоритмов по отношению к интерфейсу. Достаточно простым примером может быть

  public <T, N extends Node<T, ? extends N>> N performAlgorithm(N node)
  {
    if (!node.getChildren().isEmpty())
      return node.getChildren().get(0);

    return node;
  }

Метод может использоваться с типом интерфейса или конкретными реализациями.

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

Если вам нужно дерево узлов корпоративного уровня, вы можете заглянуть в репозиторий содержимого Java (JCR) . Но это далеко не простые решения дерева узлов в памяти, предлагаемые здесь, и многопользовательская база данных XML с SQL и XPath.