Tree Iterator Programmer’s Guide

Generic tree traversal with the Tree Iterator

Limiting the traversal depth

Skipping the unwanted branches

Dynamic adjustment of traversal depth





Generic tree traversal with the Tree Iterator

Top

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

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.

Limiting the traversal depth

Top

Tree traversal algorithms usually go over all nodes of a tree assuming that full traversal is required by the calling code. However, oftentimes calling code needs to process only the subset of the tree’s levels meaning that it doesn’t need to go all the way to the leaf level of a tree. Needless to say that in this case full traversal carries significant overhead since it traverses the nodes that are simply ignored by the calling code.

setMaxDepth() method or maxDepth parameter of the tree iterator constructor set the maximum level (path length from the root of a tree) that should be traversed by the iterator. This parameter is checked in the next() method of the iterator before moving to the children of the current node. Effectively, all “low growing” nodes of a tree (on levels below specified) won’t be traversed. Note that root is considered level 0. Example:


public static final int idLevel = 2;
//...
// xdoc -- tree root
TIterator tIterator = new TIterator ( xdoc , new DOMAdapter(), idLevel );
for( Node node = xdoc; node!=null; node=(Node)tIterator.next() ){
  // perform processing...
}

Skipping the unwanted branches

Top

Oftentimes there is a need to process nodes selectively, based on conditions applied to one of the parent nodes. In other words, the condition is checked against the parent node (control node), and if condition is met, the entire branch that originates from this node should be processed. Otherwise, children of this node should be ignored.

Normally, this kind of processing is performed using nested loops and multiple iterators. The tree iterator allows for doing it in one loop by using its skipChildren() method. Example below processes only nodes with the specific id (nodes of type “id ” constitutes the second level in the testing XML file).



import com.myarch.treeiterator.TreeIterator;
import com.myarch.treeiterator.DOMAdapter;

import org.w3c.dom.Node;
import org.w3c.dom.Element;

/**
 * Demonstrates the selecive traversal using skipChildren.
 *
 */
public class SelectiveSkipTraversal {

  /**
   * Selectively traverses the tree using skipChildren.
   * Traverses only the branch of "K.Tamura" and ignores other branches.
   *
   * @param rootNode root of the DOM tree.
   */
  public void traverse ( Node rootNode ) {

    // create an iterator.
    int idLevel = 2;
    TreeIterator tIterator = new TreeIterator ( rootNode, new DOMAdapter());
    Node node = null;
    while( ( node=(Node)tIterator.next() )!=null ){
      // print node information
      System.out.println( node.getNodeName()+"="+node.getNodeValue());

      if  ( tIterator.getDepth() == idLevel && ! (node instanceof Element &&
        ((Element)node).getAttribute( "id").equalsIgnoreCase("K.TAMURA" ))) {
        // allow parsing all children of the node -- applies only to the current node
        tIterator.skipChildren();
      }
    }
  }

Dynamic adjustment of traversal depth

Top

The task of selective traversal can be accomplished by dynamically changing the depth of traversal for different nodes (branches). If we need to process only the branch with ID=”K.TAMURA”, the initial maximum depth should be set to 2 (depth of ID level). For the required selected ID node, depth should be adjusted to “unlimited “, so the tree iterator can process children of the node. With this approach, maximum depth can’t remain just a static parameter applied to the entire tree. Instead, the original depth should be restored when iterator returns to the level of parent node. In other words, depth becomes an attribute of a level and should be kept in the stack along with other level information (such as current node).

Calling program calls setLevelDepth() method of the iterator to change the maximum depth value for the current node (control node). When all children of the control node are processed and iterator returns to the control node level, the corresponding maximum depth is restored.



import com.myarch.treeiterator.TreeIterator;
import com.myarch.treeiterator.DOMAdapter;

import org.w3c.dom.Node;
import org.w3c.dom.Element;

/**
 * Demonstrates the selecive traversal using setLevelDepth method of
 * the TreeIterator.
 *
 */
public class SelectiveSetDepthTraversal {

  /**
   * Selectively traverses the tree using setLevelDepth.
   * Traverses only the branch of "K.Tamura" and ignores other branches.
   *
   * @param rootNode root of the DOM tree.
   */
  public void traverse ( Node rootNode ) {

    // create iterator, initially it is limited to the ID level
    int idLevel =2;
    TreeIterator tIterator = new TreeIterator ( rootNode, new DOMAdapter(), idLevel);
    Node node = null;
    while( ( node=(Node)tIterator.next() )!=null ){
      // print node information
      System.out.println( node.getNodeName()+"="+node.getNodeValue());

      if  ( tIterator.getDepth() == idLevel && (node instanceof Element &&
        ((Element)node).getAttribute( "id").equalsIgnoreCase("K.TAMURA" ))) {

        // this allows iterator to traverse children of the current  node
        tIterator.setLevelDepth( TreeIterator.DEPTH_UNLIMITED);
      }
    }
  }

In simple cases using skipChildren() method yields the same result. setLevelDepth(), however, provides much greater flexibility when it comes to more complex selective processing. It allows for applying different maximum depth to different branches of a tree. Some branches can be processed fully and some partially, up to the required depth. For example, we might need to process all levels for managers and only some levels for other entries in the personnel file.

This approach also allows for depth nesting. setLevelDepth() can be called multiple times, first for the topmost control node, then for the node within the same branch that meets some additional criteria and so on. In other words, coverage of the tree during traversal is defined by the combination of depths specified for the given set of criteria. Every criterion in the set can impose its own depth limitation on the tree. And no matter how complex these criteria are, the traversal is still performed within one loop.