Generic tree implementation in Java

Question

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.

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 project on java.net, might be worth looking into.

Answer 1

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.

Answer 2

There isn't a Tree class in the Collections libraries. However, there is one in the Swing Frameworks. DefaultTreeModel

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.

Answer 3

Use Guava

Guava 15.0 introduces a nice API for tree traversal so you don't need to re-implement it for the gazillionth time in your codebase.

Namely, TreeTraverser and some specialized implementations, like BinaryTreeTraverser.

A very much welcome addition to 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 Files utility class that make use of the TreeTraverser, e.g. Files.fileTreeTraverser() which gives you a TreeTraverser<File> for your file-system traversal needs.

Answer 4

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.

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:

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

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

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

Answer 6

I found an implementation of a Generic Tree (with tests) here:

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

I think this is what you are looking for.

Answer 7

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!

Answer 8

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

Answer 9

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

Answer 10

If you need an enterprise-level node tree, you could look into Java Content Repository (JCR). But it is far from the simple in-memory node tree solutions suggested here and more of a multi-user XML database with SQL and XPath.