Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 47
We shall esentially perform a preorder traversal of the
binary tree. The preorder traversal will need to be suspended
whenever we find a node to visit because this node
contains the element to be returned by next()
.
To find the next element in preorder, we will need to resume the traversal
beginning at the current node.
This resumption is best done by implementing
the preorder traversal nonrecursively.
The constructor method for the enumerator must position us at
the first node visited by a preorder traversal.
This node is the root of the tree.
The method next()
needs to simulate
the portion of a preorder traversal from the visit of the last node
to the visit of the next node. If the last node that was visited
has a non null right subtree, this subtree should be saved on a stack
so that it can be processed after we process the left subtree of the
last node that was visited. Following this saving of the right subtree
on a stack, we can determine the next node in preorder. This next node
is the root of the left subtree of the last node that was visited, unless
this left subtree is empty. When this left subtree is empty, the
next node to visit is the node at the top of the stack. When the stack
is empty, there is no next node.
The code is given below.
public class LinkedBinaryTreeWithPreorderIterator extends LinkedBinaryTree
{
/** create and return an enumerator */
public Iterator iterator()
{return new PreorderIterator();}
/** preorder enumerator */
private class PreorderIterator implements Iterator
{
// data members
private BinaryTreeNode nextNode; // next node in preorder
private ArrayStack stack = new ArrayStack(10);
// constructor
/** set nextNode to first node in preorder */
public PreorderIterator()
{nextNode = root;}
// methods
/** @return true iff tree has more elements */
public boolean hasNext()
{
return nextNode != null;
}
/** @return next element in preorder
* @throws NoSuchElementException
* when there is no next element */
public Object next()
{
if (nextNode != null)
{
// save next preorder element
Object obj = nextNode.element;
// put right subtree on the stack if not null
if (nextNode.rightChild != null)
// right subtree will be examined later
stack.push(nextNode.rightChild);
// set nextNode to next node in preorder
if (nextNode.leftChild != null)
// root of left subtree is the next node in preorder
nextNode = nextNode.leftChild;
else
{// get next preorder node from the stack
try
{
nextNode = (BinaryTreeNode) stack.pop();
}
catch (Exception e)
{// no node to back up to
nextNode = null;
}
}
return obj;
}
else throw new NoSuchElementException("No next element");
}
/** unsupported method */
public void remove()
{
throw new UnsupportedOperationException
("remove not supported");
}
}
}
The complexity of each iterator method (exclusive of the time
needed to double the stack size when needed) is readily seen to be
O(1)
.
If a linked stack is used in place of an array stack, then the
complexity of each method (including all steps) is
O(1)
.
The stack space is
O(h)
.