Trees - Data Structures and Problem Solving Using Java - page 674

stack. This process is illustrated in the constructor at lines 30 to 35. Then
first is implemented by clearing the stack, pushing the root, and calling
advance .
Figure 18.27 implements advance . It follows the outline almost verbatim.
Line 8 tests for an empty stack. If the stack is empty, we have completed the

The advance rou-
tine is complicated.
Its code follows the
earlier description
almost verbatim.

1 /**
2 * Advance the current position to the next node in the tree,
3 * according to the postorder traversal scheme.
4 * @throws NoSuchElementException if the current position is null.
5 */
6 public void advance( )
7 {
8 if( s.isEmpty( ) )
9 {
10 if( current == null )
11 throw new NoSuchElementException( );
12 current = null;
13 return;
14 }
15
16 StNode<AnyType> cnode;
17
18 for( ; ; )
19 {
20 cnode = s.topAndPop( );
21
22 if( ++cnode.timesPopped == 3 )
23 {
24 current = cnode.node;
25 return;
26 }
27
28 s.push( cnode );
29 if( cnode.timesPopped == 1 )
30 {
31 if( cnode.node.getLeft( ) != null )
32 s.push( new StNode<AnyType>( cnode.node.getLeft( ) ) );
33 }
34 else // cnode.timesPopped == 2
35 {
36 if( cnode.node.getRight( ) != null )
37 s.push( new StNode<AnyType>( cnode.node.getRight( ) ) );
38 }
39 }
40 }

figure 18.27
The advance routine for the PostOrder iterator class