Trees and Enumerations

Note, the material in these notes will not be covered in the exam In the previous notes and lab exercises you have seen how to build lists and stacks using the basic abstract linked list data structure. These notes will introduce another very common data structure -- the binary tree.

Source code for the programs in the notes can be found in the directory /import/teaching/BSc/1st/ItP/Trees/ , assuming that you are reading this on a UNIX PC in the ITL.


The Binary Tree data structure

The list structures that you are already familiar with can be considered as a kind of `dynamic' array type; that is, a list (or stack) stores a simple linear sequence of data, but unlike an array a list can grow or shrink to accomodate the amount of data in it at any one time. As you know, you can even implement linked list structures using arrays, although it is awkward to make the dynamic resizing work properly when your array capacity is exceeded (think about how you might achieve this with your array-based Stack classes from Assignment 2).

The binary tree is a somewhat different beast, as it stores data in a two-dimensional structure with some interesting properties. The diagram below shows a small binary tree storing four integer values:

treefigs/tree1.gif
Figure 1.

As you can see, the tree is constructed from linked nodes in a similar fashion to the familiar lists and stacks, where each node contains some data (in this case an integer value) and pointer(s) to other node(s) of the tree. It should be obvious to you why this structure is known as a binary tree: each node contains pointers to two further nodes, although of course either or both of these references may be null. Other types of tree structure exist, differing mainly in the amount of data and number of node pointers maintained by each node.

Trees in computer science are a bit like family trees, in that they are usually drawn `upside down'. Thus, we will refer to the node at the `top' of the tree as the root node, and those at the `bottom' (i.e. those that do not point to any other nodes) as leaf nodes. Any node that is not a leaf node is by definition and interior node of the tree. In the diagram above, the node containing the value 19 is the root node, the nodes 19 and 10 are interior nodes and the nodes 3 and 42 are the leaves. Since any tree node be be treated as the root node of a smaller tree, we can talk about the left and right subtrees of a node N; that is, the trees whose root nodes are pointed to by the left and right hand node pointers of N.

This notation is reflected by the Java implementation of the tree structure given below:

     1	/**
     2	 * A simple binary tree class, storing integers
     3	 */
     4	public class BinaryTree {
     5	
     6	  /** The data item in this node */
     7	  protected int data;
     8	
     9	  /** The left-hand subtree (LHS) */
    10	  protected BinaryTree left;
    11	
    12	  /** The right-hand subtree (RHS) */
    13	  protected BinaryTree right;
    14	
    15	
    16	  /** Create a tree */
    17	  public BinaryTree(int data) {
    18	    this.data = data;
    19	    left = null;
    20	    right = null;
    21	  }
    22	
    23	
    24	  /** Get the data in the root node */
    25	  public int data() {
    26	    return data;
    27	  }
    28	
    29	  /** Get the LHS */
    30	  public BinaryTree left() {
    31	    return left;
    32	  }
    33	
    34	  /** Get the RHS */
    35	  public BinaryTree right() {
    36	    return right;
    37	  }
    38	}
    
Each instance of the class BinaryTree forms the root of a binary tree, with its left and right subtrees pointed to by the instance variables left and right respectively. The code below shows how you might construct the tree in Figure 1 using the BinaryTree class:

     1	public class TreeTest {
     2	
     3	  public static void main(String args[]) {
     4	    BinaryTree tree = new BinaryTree(19);
     5	    tree.left = new BinaryTree(10);
     6	    tree.right = new BinaryTree(42);
     7	    tree.left.left = new BinaryTree(3);
     8	  }
     9	}
    
This is all very well, but it doesn't immediately seem to be much use; after all, we could store the same data just as easily in a list or an array. Look more closely at the tree in Figure 1 though, and you will notice that whichever node you choose, the values stored in its left subtree are always less than the value stored in the node itself, while the values in the right subtree are always greater than the node value. Very convenient, but again, what use is it? Consider the problem of searching for a particular data value stored in the tree: if you know nothing about the arrangement of nodes in the tree, you might have to examine every node of the tree before finding the sought value, or concluding that it was not present. This is an O(N) search, similar to searching an unordered list. If however, the tree is arranged according to the scheme described above, we can make the search much more efficient. Say we are looking for the value 3. We begin by examining the root node, and noticing that 3 is less than 19. Therefore, if the value 3 is in the tree anywhere, it must lie within the left subtree of the root node (recall that all values in the left subtree are less than the value of their parent). So the search proceeds to the root of the left subtree, in this case the node containing the value 10. 3 is less than 10, so again we follow the left hand pointer, and this time find the node we are looking for. This search required a total of three comparisons between node values, rather than the four that might have been needed for a brute-force search. In fact, the number of comparisons needed for a search of this kind depends height of the tree rather than the absolute number of nodes, where the height is the length of the longest path from the root node to a leaf node, plus one. For larger trees, the difference will be much greater and the searches consequently much more efficient. Note that you can achieve the same degree of speedup when searching an ordered list -- your Introduction to Algorithms notes should have much more to say on this topic.


Adding and searching for nodes

You have probably noticed that I haven't yet mentioned how to get the nodes into this nice arrangement in the first place. The class below is an enhanced version of the simple BinaryTree above, with additional methods for searching and adding new nodes to the tree.

     1	/**
     2	 * A simple binary tree class, storing instances of OrderedObject.
     3	 */
     4	public class BinaryTree {
     5	
     6	  /** The data item in this node */
     7	  protected OrderedObject data;
     8	
     9	  /** The left-hand subtree (LHS) */
    10	  protected BinaryTree left;
    11	
    12	  /** The right-hand subtree (RHS) */
    13	  protected BinaryTree right;
    14	
    15	
    16	  /** Create a new empty tree */
    17	  public BinaryTree() {
    18	    data = null;
    19	    left = null;
    20	    right = null;
    21	  }
    22	
    23	
    24	  /** Get the data in the root node */
    25	  public OrderedObject data() {
    26	    return data;
    27	  }
    28	
    29	  /** Get the LHS */
    30	  public BinaryTree left() {
    31	    return left;
    32	  }
    33	
    34	  /** Get the RHS */
    35	  public BinaryTree right() {
    36	    return right;
    37	  }
    38	
    39	
    40	  /**
    41	   * Insert a new data item into the tree.  This will fill an empty (data ==
    42	   * null) node if it finds one, otherwise a new node is created.  The data is 
    43	   * always inserted in sorted order, using compareTo().
    44	   * Throws a TreeException if a matching object is already present.
    45	   */
    46	  public void insert(OrderedObject newData) throws TreeException, OrderedObjectException {
    47	    if (data != null) {
    48	      int a = newData.compareTo(data);
    49	      if (a < 0) {
    50		if (left == null) {
    51		  left = new BinaryTree();
    52		}
    53		left.insert(newData);
    54	      }
    55	      else if (a > 0) {
    56		if (right == null) {
    57		  right = new BinaryTree();
    58		}
    59		right.insert(newData);
    60	      }
    61	      else {
    62		throw new TreeException("Object "+newData+" is already in the tree!");
    63	      }
    64	    }
    65	    else {
    66	      data = newData;
    67	    }
    68	  }
    69	
    70	  /**
    71	   * Find a data item matching target in the tree.  Returns a subtree with the 
    72	   * matching item as its root, or null if no match was found.
    73	   */
    74	  public BinaryTree find(OrderedObject target) throws TreeException, OrderedObjectException {
    75	    if (data != null) {
    76	      int a = target.compareTo(data);
    77	      if (a < 0) {
    78		return (left == null) ? null : left.find(target);
    79	      }
    80	      else if (a > 0) {
    81		return (right == null) ? null : right.find(target);
    82	      }
    83	      else {
    84		return this;
    85	      }
    86	    }
    87	    else {
    88	      return null;
    89	    }
    90	  }
    91	
    92	
    93	  /** Generate a printable representation of the root node of the tree. */
    94	  public String toString() {
    95	    if (data != null) {
    96	      return data.toString();
    97	    }
    98	    else {
    99	      return null;
   100	    }
   101	  }
   102	}
    
Before we examine the algorithms used by the insert and find methods, let's take a closer look at the data stored by this class. The tree searching algorithm is based around the idea of one data item being `greater than' or `less than' another. These concepts are pretty easy to understand if we are just dealing with integers, but what if we want the tree to store data of some complex type, such as student records? How can we determine the ordering of such objects? In Java, and other object-oriented languages, the usual solution is to have the data objects implement a method that compares the object with another of the same type, and returns some indication of which object is `greater'. For example, the compareTo methods from the built-in String class or the Person class from Lab 16.

We also want our trees to be generic; this is, we should be able to construct a tree holding any type of ordered data without changing the implementation of the binary tree class itself. To achieve both of these goals using Java, the first step is to define an interface class, declaring the methods that we want all tree data objects to implements. Remember that an interface only supplies method headers; the bodies of the methods must be provided by the class(es) that implement the interface.

     1	/**
     2	 * Allows a class to define an ordering on its instances.
     3	 */
     4	public interface OrderedObject {
     5	
     6	  /**
     7	   * Compare the value of this object with the value of other.  Returns:
     8	   *  -1 if this object's value is 'less than' other's value
     9	   *   0 if the two object's values are equal (equals() would return true)
    10	   *   1 if this object's value is 'greater than' other's value
    11	   * Throws an OrderedObjectException if the values cannot be compared.
    12	   */
    13	  int compareTo(OrderedObject other) throws OrderedObjectException;
    14	}
    
Every class that implements this interface must provide a compareTo method with the specified arguments and return type. In object-oriented terms, every instance if a class that implements OrderedObject is-a OrderedObject and is therefore suitable as a data object type for the BinaryTree class. The OrderedString class below shows a simple example of this interface in action:

     1	/**
     2	 * Transforms a String into an OrderedObject.
     3	 */
     4	class OrderedString implements OrderedObject {
     5	
     6	  // The actual string data
     7	  private String str;
     8	
     9	
    10	  /** Create a new OrderedString encapsulating the given String */
    11	  public OrderedString(String value) {
    12	    str = value;
    13	  }
    14	
    15	
    16	  /** Implement the method from the OrderedObject interface */
    17	  public int compareTo(OrderedObject other) throws OrderedObjectException {
    18	    if (other instanceof OrderedString) {
    19	      return str.compareTo(((OrderedString)other).str);
    20	    }
    21	    else {
    22	      throw new OrderedObjectException("Illegal comparison");
    23	    }
    24	  }
    25	
    26	
    27	  /** Produce a printable representation of this object */
    28	  public String toString() {
    29	    return str;
    30	  }
    31	}
    
Instances of the OrderedString class act as `wrappers' around ordinary String objects, and implement the required method from the OrderedObject interface. You might think that since String already has a suitable compareTo method -- line 19 above simply calls this existing method to perform the comparison -- we would have been better off to just extend the String class rather than storing the String as an instance variable. Well, you're right, it would have been much more elegant to do it this way. However, the built in String class is declared to be a final class, meaning that it cannot be extended. An oversight on the part of the Java designers?

While this technique for creating ordered object classes is convenient and reasonably elegant, it is not without its drawbacks. The compareTo method must explicitly check that the other argument is in fact an instance of OrderedString and not some other type of OrderedObject. (Something to think about: why can we not just declare the method to take an OrderedString parameter?) Even with this check in place, it is still possible to construct a tree from a mixture of different OrderedObject implementations; searches or insertions on such a tree might then mysteriously fail. To work around this problem, we can extend the BinaryTree class itself to accept only OrderedString objects:

     1	/**
     2	 * A tree that enforces the use of OrderedStrings.
     3	 */
     4	public class StringTree extends BinaryTree {
     5	
     6	  /** Insert an OrderedString into the tree */
     7	  public void insert(OrderedString newData) throws TreeException {
     8	    try {
     9	      super.insert(newData);
    10	    }
    11	    catch (OrderedObjectException e) { }
    12	  }
    13	
    14	  /** Don't allow a non-OrderedString to be inserted */
    15	  public void insert(OrderedObject newData) throws TreeException {
    16	    throw new TreeException("Attempt to insert a non-OrderedString");
    17	  }
    18	
    19	
    20	  /** Look for the given OrderedString */
    21	  public BinaryTree find(OrderedString target) throws TreeException {
    22	    try {
    23	      return super.find(target);
    24	    }
    25	    catch (OrderedObjectException e) { return null; }
    26	  }
    27	
    28	  /** Don't allow searches for non-OrderedStrings */
    29	  public BinaryTree find(OrderedObject target) throws TreeException {
    30	    throw new TreeException("Attempt to search for a non-OrderedString");
    31	  }
    32	}
    
We will now return to discussing the algorithm for inserting new nodes into the tree. The insert method as implemented in lines 46-68 of BinaryTree.java is recursive. There are two base cases that cause the recursion to terminate:

  1. The root of the tree contains no data (the data field is null). In this case, the new data is placed in the root node of the tree. As we shall see later, such an `empty' node will only occur at a suitable point in the tree.

  2. The root of the tree contains the same data (as determined by compareTo) as the data we are inserting. This implementation requires that data items be unique, so in this case we throw a TreeException and the insertion fails.
If neither of these cases occurs, the root node must contain data that is either less than or greater than newData, again as determined by compareTo. The method then makes a recursive call to insert, passing the right or left subtree respectively as the root of the tree to insert into. If the target subtree does not yet exist (the subtree reference is null), a new, empty tree is created and attached to the current root node. Since such a node will contain no data, the recursive call will stop at the first base case above and insert the data at that point.

For example, assume we have just created a new BinaryTree object, resulting in the structure seen in Figure 2:

BinaryTree tree = new BinaryTree();
    
treefigs/tree2.gif
Figure 2.

We now attempt to insert the integer value 19, wrapped inside an OrderedInteger object, into the tree:

tree.insert(new OrderedInteger(19));
    
The insert method will immediately find that the root node of the tree contains no data, and will insert the data value there, giving the new structure shown in Figure 3:

treefigs/tree3.gif
Figure 3.

Next, we attempt to insert the value 10:

tree.insert(new OrderedInteger(10));
    
This time, the root of the tree is occupied, so the method must recursively call insert on either its left or right subtree. The value to be inserted (10) is less than the value in the root (19), so it must be placed in the left subtree. However, that subtree does not yet exist, so it must be created (Figure 4):

treefigs/tree4.gif
Figure 4.

Then, the recursive call to insert will have the newly created left hand subtree as its root node. Since the node is empty, the new value can immediately be inserted (Figure 5):

treefigs/tree5.gif
Figure 5.

Several more insertions might lead to the structure shown in Figure 6:

treefigs/tree6.gif
Figure 6.

The find method is structurally very similar to insert, using the same recursive algorithm to locate the required data, if it exists. Of course, both methods could easily be rewritten in a purely iterative way without any recursive calls (you may want to try doing this). Also, the same basic algorithms could be used equally well to perform inserts and searches on an ordered linked list structure; this case the left and right `subtrees' would be represented by the left and right halves of the list.


Traversing the tree

Once we have some data in our tree, it might be useful to be able to list the data out in some sequential order, perhaps in order to write it to a disk file, or to print out a listing of the database contents. Unlike a list, it is not immediately obvious in what order we should visit the tree nodes to achieve this, as each node has two subtrees as well as the data contained in the node itself. (Note: a sorted list can be considered as a `degenerate' tree, where each node has a right hand subtree only). As it happens, there are three common orderings -- the process of visiting every tree node in some order is often referred to as traversing the tree -- that adapt well to the tree structure: pre-ordering, post-ordering and in-ordering. The names relate to the relative ordering of the node data and subtrees. These three traversal strategies will be illustrated with reference to the tree shown in Figure 7.

treefigs/tree1.gif
Figure 7.

Pre-ordering

In this ordering scheme, the data stored in each node is ordered before the contents of its left and right subtrees. That is, each node is traversed in the order [node data, left subtree data, right subtree data]. The traversal is done recursively on the subtrees. A pre-order traversal of Figure 7 would proceed as follows:

19, 10, 3, 42
    

Post-ordering

In the post-ordering scheme, each node is traversed in the order [left subtree data, right subtree data, node data]:

3, 10, 42, 19
    

In-ordering

Under the in-ordering scheme, each node in the tree is traversed in the order [left subtree data, node data, right subtree data]. Because all of the data in the left hand subtree is less than the root node data, and all the data in the right hand subtree is greater than the root data, this algorithm results in the tree data being printed 'in order':

3, 10, 19, 42
    
The TreeTest class given below includes methods to traverse a tree using each of these orderings.

     1	import java.util.Enumeration;
     2	
     3	class TreeTest {
     4	
     5	  public static void main(String[] args) {
     6	    BinaryTree tree = new BinaryTree();
     7	
     8	    try {
     9	      // Insert A-Z in some random order
    10	      java.util.Vector v = new java.util.Vector();
    11	      for (char c = 'A'; c <= 'Z'; c++) {
    12		v.addElement(new Character(c));
    13	      }
    14	      while (v.size() > 0) {
    15		int r = (int)Math.round(Math.random() * (v.size()-1));
    16		tree.insert(new OrderedString(v.elementAt(r).toString()));
    17		v.removeElementAt(r);
    18	      }
    19	      printPreOrder(tree);
    20	      System.out.println();
    21	    }
    22	    catch (Exception e) {
    23	      System.out.println(e);
    24	    }
    25	  }
    26	
    27	
    28	  public static void printPreOrder(BinaryTree tree) {
    29	    if (tree.data() != null) {
    30	      System.out.print(tree.data()+" ");
    31	    }
    32	    if (tree.left() != null) {
    33	      printPreOrder(tree.left());
    34	    }
    35	    if (tree.right() != null) {
    36	      printPreOrder(tree.right());
    37	    }
    38	  }
    39	
    40	  public static void printPostOrder(BinaryTree tree) {
    41	    if (tree.left() != null) {
    42	      printPostOrder(tree.left());
    43	    }
    44	    if (tree.right() != null) {
    45	      printPostOrder(tree.right());
    46	    }
    47	    if (tree.data() != null) {
    48	      System.out.print(tree.data()+" ");
    49	    }
    50	  }    
    51	
    52	  public static void printInOrder(BinaryTree tree) {
    53	    if (tree.left() != null) {
    54	      printInOrder(tree.left());
    55	    }
    56	    if (tree.data() != null) {
    57	      System.out.print(tree.data()+" ");
    58	    }
    59	    if (tree.right() != null) {
    60	      printInOrder(tree.right());
    61	    }
    62	  }    
    63	}
    
Why would you choose one traversal method over another? Clearly an in-order traversal is appropriate when you want to retrieve the tree data in sorted order. However, consider the case where the tree contents are to be stored in a file, then later reloaded into a new tree structure. If in-order traversal was used to write the file, the data ends up being pre-sorted when the time comes to load it back in again. Consider for a moment what the tree structure will look like if the data to be inserted is already sorted...essentially the tree degrades into a linked list, neatly eliminating any advantage from using the tree! In this situation, you want the data to be unsorted, so a pre- or post-order traversal would be used when writing the file.


Deleting nodes

Deleting nodes from a tree is somewhat more complicated than deleting from a linked list. The problems arise because the node being deleted may have two (or even more) 'children', all of which must be attached to a suitable 'parent' node when their existing parent is removed. The rearrangement of the tree must be done in such a way as to maintain the correct ordering of each node's subtrees. The class below adds a delete method to the basic binary tree, illustrating one of the many ways this can be achieved. The new method makes use of an additional private method which takes a third parameter. This parent argument gives the parent node of the tree parameter. It is initialised to null by the main delete method, since we have no way of knowing whether or not the tree has a parent node.

     1	/**
     2	 * An extended binary tree, able to delete nodes as well (Wow!)
     3	 */
     4	public class DeletingBinaryTree extends IteratingBinaryTree {
     5	
     6	  /** Delete a node matching oldData */
     7	  public boolean delete(OrderedObject oldData) throws TreeException, OrderedObjectException {
     8	    return delete(this, null, oldData);
     9	  }
    10	
    11	  // A far-too-complex subroutine to do the real work!
    12	  private boolean delete(BinaryTree tree, BinaryTree parent, OrderedObject oldData) throws TreeException, OrderedObjectException {
    13	    if (tree.data != null) {
    14	      int a = oldData.compareTo(tree.data);
    15	      if (a < 0) {
    16		return (tree.left == null) ? false : delete(tree.left, tree, oldData);
    17	      }
    18	      else if (a > 0) {
    19		return (tree.right == null) ? false : delete(tree.right, tree, oldData);
    20	      }
    21	      else {
    22		// found it, now delete it
    23		if (tree.left == null && tree.right == null) {
    24		  // Leaf node
    25		  if (parent != null) {
    26		    // If we have a parent we can just snip the node off
    27		    if (parent.left == tree) {
    28		      parent.left = null;
    29		    }
    30		    else {
    31		      parent.right = null;
    32		    }
    33		  }
    34		  else {
    35		    // Otherwise we get left with an empty node
    36		    tree.data = null;
    37		  }
    38		}
    39		else if (tree.left == null) {
    40		  // Replace the node with its right-hand child
    41		  tree.data = tree.right.data;
    42		  tree.left = tree.right.left;
    43		  tree.right = tree.right.right;
    44		}
    45		else if (tree.right == null) {
    46		  // Replace the node with its left-hand child
    47		  tree.data = tree.left.data;
    48		  tree.right = tree.left.right;
    49		  tree.left = tree.left.left;
    50		}
    51		else {
    52		  // Find the largest node on the LHS
    53		  BinaryTree max = tree.left;
    54		  while (max.right != null) {
    55		    max = max.right;
    56		  }
    57		  // Move LHS up to root, attach old RHS to max
    58		  max.right = tree.right;
    59		  tree.data = tree.left.data;
    60		  tree.right = tree.left.right;
    61		  tree.left = tree.left.left;
    62		}
    63		return true;
    64	      }
    65	    }
    66	    else {
    67	      return false;
    68	    }
    69	  }
    70	}
    
The private delete method uses the familiar recursive searching technique to locate the node to be deleted. Not that the parent parameter is updated each time a new recursive call is made. Eventually, the target node will be found, or the search will reach the leaves of the tree and return false.

Once the node has been found, we must disconnect it from the tree structure. This operation is handled as four separate cases, based on the number and location of the node's children.

Case 1: No children

Deleting a leaf node is by far the easiest case to handle, since there are no child nodes to be rearranged. If we know the parent of the target node, the left or right subtree (whichever points to the target) of the parent is simply set to null. If the parent is unknown, the node cannot be disconnected, but we can set its data member to null, turning it into an empty node that may be reused by a subsequent insert operation. Figure 9 shows the result of deleting the node containing value 100 from the tree in Figure 6:

treefigs/tree8.gif
Figure 8.

Case 2: Left subtree only

This case is also relatively trivial to deal with. All of the nodes on the left subtree of the target must be 'less than' the target node; they must also be 'less than' the target node's parent, if it has one. Therefore, we can just replace the target node with its left-hand subtree to both delete the target and maintain the correct sorting relationships in the tree. Figure 9 shows the result of deleting the node containing value 10 from the tree in Figure 6:

treefigs/tree9.gif
Figure 9.

Case 3: Right subtree only

This case exactly analagous to the previous one, except that the target node will be replaced with its right subtree.

Case 4: Left and right subtrees

This is the most complicated situation to deal with, since both subtrees must be reattached somewhere while maintaining the sorting relationship of the tree. The trick is to make a couple of observations about the properties of the two subtrees:

  1. Every node in the right subtree is 'greater than' every node in the left subtree.
  2. The 'largest' node in the left subtree cannot have a right subtree, because any nodes on such a subtree would be larger than their parent.
Therefore, we know that there is at least one place in the left subtree where we could 'attach' another subtree, as long as all the nodes in the subtree are 'greater than' the 'greatest' node on the left subtree. The right subtree of the target node meets this condition, since all of its nodes must be greater than anything on the left subtree. So, the first step in deleting the target node is to disconnect its right subtree, then reconnect the subtree as the right subtree of the largest node in the left subtree. This is much easier to visualise than to explain -- Figure 10 shows the first step in deleting the node containing 19 from the tree of Figure 6:

treefigs/tree10.gif
Figure 10.

The tree at this point is not internally consistent (there are nodes on the left subtree of the target that are definitely 'greater than' 19). This is not really a problem though, since we are about to delete the target node. At this point the problem will look exactly like case 2 above, where the target node has only a left subtree. This, we simply replace the target with its new left subtree, and the deletion is complete:

treefigs/tree11.gif
Figure 11.

The algorithm used by the DeletingTree class contains a subtle bug. It it worthwhile trying to figure out what this bug is, and to develop a solution for it. (Hint: consider what could happen after a 'case 1' deletion has left an empty node in the tree, and the empty node's parent is then deleted).


Using Iterators for tree traversal

The final section of these notes presents an alternative technique for traversing a tree, or in indeed any other data structure. The class below extends the basic binary tree class with the capability to create so-called iterator or enumerator objects that may then be used to traverse the tree in a particular way. An iterator is, as the name implies, an object that iterates over all of the members of some data structure, returning them to the user one at a time in some defined order. The advantage of using an iterator rather than coding the traversal methods yourself (as in the TreeTest program is that you do not need to know anything about the internal structure of the tree, list, etc that you are traversing -- the iterator object will keep track of all these details for you.

The iterators used by the IteratingBinaryTree are based around the Java Enumeration interface, which essentially provides a general framework for building iterator objects. An instance of Enumeration must provide two methods:

  1. boolean hasMoreElements() returns true iff there are elements that have yet to be traversed.
  2. Object nextElement() returns the next object in the traversal. Note that this object is of class Object and must be cast to an appropriate type.
An extended implementation of Enumeration might offer additional methods, eg. to 'rewind' the traversal back to the first element. Many Java classes, such as Vector and Hashtable provide methods to obtain an Enumeration object over their elements. In general an Enumeration will be used in a loop such as:

Enumeration e = someObject.elements();
while (e.hasMoreElements()) {
  someClass next = (someClass)e.nextElement();
  System.out.println(next);
}
    
The IteratingBinaryTree class contains four inner classes that implement the iterators for the tree. The most important of these is the TreeIterator class. This declares a Vector object (Java's built-in linked list class) that will hold the elements of the tree in traversal order, and implements the Enumeration methods that will return these elements on at a time, in the order they occur in the vector. It is up to the subclasses of TreeIterator to fill in the contents of the vector.

Three subclasses of TreeIterator are provided, to perform pre-, post- and in-order traversals of the tree. Each of these performs the traversal in the usual way and places the tree data into the vector in the order that the nodes were traversed. Thus, the user will be able to retrieve the tree data in the same order using the nextElement() method of the iterator. The IteratingBinaryTree class itself hass three new methods to create and return the three kinds of iterator. Note that all of these iterator classes take a copy of the tree contents, so any additions or deletions made to the tree should not affect any active iterators. Is this always true? In particular, is there any way that a deletion (using the algorithm presented above) could affect the contents of a tree iterator? (Hint: is the data really copied, or just aliased?)

     1	import java.util.Enumeration;
     2	import java.util.Vector;
     3	import java.util.NoSuchElementException;
     4	
     5	
     6	/**
     7	 * A simple binary tree class, storing instances of OrderedObject.
     8	 */
     9	public class IteratingBinaryTree extends BinaryTree{
    10	
    11	  // A basic iterator over a vector of objects
    12	  private class TreeIterator implements Enumeration {
    13	    private Vector data;
    14	    private int current;
    15	
    16	    TreeIterator() {
    17	      data = new Vector();
    18	      current = 0;
    19	    }
    20	
    21	    public boolean hasMoreElements() {
    22	      return (current < data.size());
    23	    }
    24	
    25	    public Object nextElement() {
    26	      if (hasMoreElements()) {
    27		return data.elementAt(current++);
    28	      }
    29	      else {
    30		throw new NoSuchElementException();
    31	      }
    32	    }
    33	  }
    34	
    35	  // An iterator containing the tree data in pre-order
    36	  private class PreOrderIterator extends TreeIterator {
    37	
    38	    PreOrderIterator(BinaryTree tree) {
    39	      init(tree);
    40	    }
    41	
    42	    private void init(BinaryTree tree) {
    43	      if (tree.data() != null) {
    44		this.data.addElement(tree.data());
    45	      }
    46	      if (tree.left() != null) {
    47		init(tree.left());
    48	      }
    49	      if (tree.right() != null) {
    50		init(tree.right());
    51	      }
    52	    }
    53	  }
    54	
    55	  // An iterator containing the tree data in post-order
    56	  private class PostOrderIterator extends TreeIterator {
    57	    
    58	    PostOrderIterator(BinaryTree tree) {
    59	      init(tree);
    60	    }
    61	
    62	    private void init(BinaryTree tree) {
    63	      if (tree.left() != null) {
    64		init(tree.left());
    65	      }
    66	      if (tree.right() != null) {
    67		init(tree.right());
    68	      }
    69	      if (tree.data() != null) {
    70		this.data.addElement(tree.data());
    71	      }
    72	    }
    73	  }
    74	
    75	  // An iterator containing the tree data in order
    76	  private class InOrderIterator extends TreeIterator {
    77	
    78	    InOrderIterator(BinaryTree tree) {
    79	      init(tree);
    80	    }
    81	
    82	    private void init(BinaryTree tree) {
    83	      if (tree.left() != null) {
    84		init(tree.left());
    85	      }
    86	      if (tree.data() != null) {
    87		this.data.addElement(tree.data());
    88	      }
    89	      if (tree.right() != null) {
    90		init(tree.right());
    91	      }
    92	    }
    93	  }
    94	
    95	
    96	  /** Return a pre-order iterator for this tree */
    97	  public Enumeration iteratePreOrder() {
    98	    return new PreOrderIterator(this);
    99	  }
   100	
   101	  /** Return a post-order iterator for this tree */
   102	  public Enumeration iteratePostOrder() {
   103	    return new PostOrderIterator(this);
   104	  }
   105	
   106	  /** Return an in-order iterator for this tree */
   107	  public Enumeration iterateInOrder() {
   108	    return new InOrderIterator(this);
   109	  }
   110	}
    
The program TreeTest2 below is a simple demonstration of the iterator classes in use. You shoud modify this to experiment with the pre- and post-order iterators as well.

     1	import java.util.Enumeration;
     2	
     3	class TreeTest2 {
     4	
     5	  public static void main(String[] args) {
     6	    IteratingBinaryTree tree = new IteratingBinaryTree();
     7	
     8	    try {
     9	      // Insert A-Z in some random order
    10	      java.util.Vector v = new java.util.Vector();
    11	      for (char c = 'A'; c <= 'Z'; c++) {
    12		v.addElement(new Character(c));
    13	      }
    14	      while (v.size() > 0) {
    15		int r = (int)Math.round(Math.random() * (v.size()-1));
    16		tree.insert(new OrderedString(v.elementAt(r).toString()));
    17		v.removeElementAt(r);
    18	      }
    19	      Enumeration enum = tree.iterateInOrder();
    20	      while (enum.hasMoreElements()) {
    21		System.out.print(enum.nextElement()+" ");
    22	      }
    23	      System.out.println();
    24	    }
    25	    catch (Exception e) {
    26	      System.out.println(e);
    27	    }
    28	  }
    29	}
    

Written by Scott Mitchell. Updated by Matthew Huntbach

These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.

Last modified: 30 September 1999