Java Reference
In-Depth Information
FIGURE 24-4
A binary tree
a
c
b
d
e
f
g
24.13
Traversals that use an iterator. A method such as inorderTraverse is not hard to implement, but
this method only displays the data during the traversal. In addition, the entire traversal takes place
once the method is invoked. To provide the client with more flexibility, we should define the tra-
versals as iterators. In this way, the client can do more than simply display data during a visit and
can control when each visit takes place.
Recall that Java's interface Iterator declares the methods hasNext and next . These methods
enable a client to retrieve the data from the current node in the traversal at any time. That is, the cli-
ent can retrieve a node's data, do something with it, perhaps do something else, and then retrieve
the data in the next node in the iteration.
If we look at BinaryTreeInterface in Segment 24.4, we see that the class BinaryTree must
implement the methods in the interface TreeIteratorInterface . For example, the method get-
InorderIterator can be implemented within BinaryTree as follows:
public Iterator<T> getInorderIterator()
{
return new InorderIterator();
} // end getInorderIterator
As we did in earlier chapters, we define the class InorderIterator as a private inner class of
BinaryTree .
An iterator must be able to pause during a traversal. This suggests that we not use recursion in
its implementation. Chapter 5 showed how to use a stack instead of recursion. That is what we will
do here.
24.14
An iterative version of inorderTraverse . Before we define an iterator, let's consider an iterative
version of the method inorderTraverse . This method will be a little easier to construct than the
iterator, yet it will take similar steps.
Figure 24-5 shows the tree in Figure 24-4 and the result of using a stack to perform its inorder
traversal. We begin by pushing the root, a , onto the stack. We then traverse to the left as far as possi-
ble, pushing each node onto the stack. We then pop the d from the stack and display it. Since d has no
children, we pop the stack again and display b . Now b has a right child, e , which we push onto the
stack. Since e has no children, we pop it from the stack and display it. The process continues until we
have visited all the nodes—that is, until both the stack is empty and the current node is null .
 
Search WWH ::




Custom Search