Реализация общего дерева в Java - PullRequest
Новая
       47

Реализация общего дерева в Java

37 голосов
/ 31 августа 2009

Кто-нибудь знает о реализации общего дерева (узлы могут иметь несколько дочерних элементов) для Java? Он должен исходить из надежного источника и должен быть полностью протестирован.

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

РЕДАКТИРОВАТЬ: Найдено этот проект на java.net, возможно, стоит посмотреть.

Ответы [ 9 ]

23 голосов
/ 31 августа 2009

Вот так: 

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

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

10 голосов
/ 23 сентября 2013

Использование гуавы

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

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

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

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

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

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

9 голосов
/ 31 августа 2009

В библиотеках коллекций нет класса Tree. Тем не менее, - это единица в Swing Frameworks. DefaultTreeModel

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

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

8 голосов
/ 01 июня 2010

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

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

Я попытался решить это сам, но в итоге получил довольно сложный интерфейс, который все еще обеспечивает безопасность типов. Вот скелет идеи, которая устанавливает абстрактный класс 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;
   }    
}
6 голосов
/ 31 января 2010

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

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

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

5 голосов
/ 31 января 2010

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

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

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

2 голосов
/ 02 февраля 2010

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

0 голосов
/ 12 июня 2019

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

  /**
   * 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);
0 голосов
/ 31 августа 2009

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

...