Ответ 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();
  }
}

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

Ответ 2

Использовать Guava

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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