MyArch.com

Java Frameworks

API   Contents

Generic tree traversal with the Tree Iterator

Tree iterator is capable of traversing any type of a treelike structure. This is accomplished by using the adapter class for each unique type of a tree. Adapter provides the link between generic methods used by the iterator and methods used by the particular Node class. In fact, just two methods are needed to implement the adapter for the tree iterator:


/**
 * Returns java.util.Iterator to iterate over children of the node.
 * @param node node
 * @return java.util.Iterator for the collection that contains
 children
 * of the given node.
 */
public Iterator getChildren( Object node );

/**
 * Returns true if the node has children.
 * @param node node
 * @return true if the node has children
 */
public boolean hasChildren( Object node );

Most of the times adapter class is fairly trivial and doesn't do much. swing.tree.TreeNode adapter is a perfect example. Its simplicity stems from the fact that TreeNode natively supports Enumeration interface for child nodes:


package com.myarch.treeiterator;

import java.util.Iterator;
import javax.swing.tree.TreeNode;

/**
 * Maps javax.swing.tree.TreeNode interface to
 * the generic methods required by TIterator.
 */
public class SwingAdapter implements TreeNodeAdapter {

  /**
   * Note that EnumarationAdapter is used since
   * TreeNode doesn't
   * implement the Iterator interface directly.
   */
  public Iterator getChildren( Object node ) {
    return new EnumerationAdapter( ((TreeNode)node).children() );
  }

  public boolean hasChildren( Object node ) {
    return ! ((TreeNode)node).isLeaf();
  }
}
 

When there is no native Enumeration or Iterator support, implementation can be a bit trickier. DOMAdapter (adapter for org.w3c.dom.Node) includes additional adapter class to support Iterator. This class uses org.w3c.dom.Node.getNextSibling() method to enumerate over the list of children.

In Java environment, Iterator seems to be a natural choice of the interface for collection of nodes, so additional Iterator adapter is rarely required. DOM specification, being language independent, does not natively support Iterator, however vendors of XML parsers sometimes extend the basic interface of org.w3c.dom by adding Iterator support.

Adapter object should be passed to the tree iterator constructor along with the tree's root, for example:


// Initialization code for Xerces parser
DOMParser parser = new DOMParser();
parser.parse( new InputSource( new FileReader( fileName )));
Document xdoc = parser.getDocument();

// Initialize iterator
TreeIterator tIterator = new TreeIterator ( xdoc , new DOMAdapter() );
 

The traversal itself is trivial . Tree iterator supports both next() and hasNext() methods provided by java.util.Iterator interface.

But unlike, for instance, java.util.ListIterator, tree iterator does not throw NoSuchElementException if the end of a tree is reached, instead it simply returns null. This is done because hasNext() call may have performance overhead for some trees, so it is more efficient to use the comparison with null instead:


Node node = null;
while( (node=(Node)tIterator.next()) != null )  {
  // print node information
  System.out.println( node.getNodeName()+"="+node.getNodeValue());
}
See TreeIterator class documentation for more details.

API   Contents