Java Reference
In-Depth Information
FIGURE 24-5
Using a stack to perform an inorder traversal of a binary tree
Traversal order:
d
b
e
a
f
g
c
a
c
b
d
d
e
f
Stack after
each
push
or
pop
b
b
a
b
e
f
g
a
a
a
a
a
c
c
c
c
c
g
Here is an iterative implementation of
inorderTraverse
:
public void
inorderTraverse()
{
StackInterface<BinaryNodeInterface<T>> nodeStack =
new
LinkedStack<BinaryNodeInterface<T>>();
BinaryNodeInterface<T> currentNode = root;
while
(!nodeStack.isEmpty() || (currentNode !=
null
))
{
// find leftmost node with no left child
while
(currentNode !=
null
)
{
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
// end while
// visit leftmost node, then traverse its right subtree
if
(!nodeStack.isEmpty())
{
BinaryNodeInterface<T> nextNode = nodeStack.pop();
assert
nextNode !=
null
;
// since nodeStack was not empty
// before the pop
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
// end if
}
// end while
}
// end inorderTraverse
Question 5
In the previous method, if you replace each occurrence of
BinaryNodeInterface
with
BinaryNode
, what other changes, if any, must you make?
24.15
The private class
InorderIterator
.
Now let's implement an inorder traversal as an iterator. We
distribute the logic of the previous method
inorderTraverse
among the iterator's constructor and
the methods
hasNext
and
next
. The stack and the variable
currentNode
are data fields in the itera-
tor class. The method
next
advances
currentNode
, adds to the stack as necessary, and eventually
pops the stack to return the data in the node that is next in the iteration. Thus, the implementation of
the private inner class
InorderIterator
appears as given in Listing 24-3.
