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

1 // InOrder class; maintains "current position"
2 // according to an inorder traversal
3 //
4 // CONSTRUCTION: with tree to which iterator is bound
5 //
6 // ******************PUBLIC OPERATIONS**********************
7 // Same as TreeIterator
8 // ******************ERRORS*********************************
9 // Exceptions thrown for illegal access or advance
10
11 class InOrder<AnyType> extends PostOrder<AnyType>
12 {
13 public InOrder( BinaryTree<AnyType> theTree )
14 { super( theTree ); }
15
16 /**
17 * Advance the current position to the next node in the tree,
18 * according to the inorder traversal scheme.
19 * @throws NoSuchElementException if iteration has
20 * been exhausted prior to the call.
21 */
22 public void advance( )
23 {
24 if( s.isEmpty( ) )
25 {
26 if( current == null )
27 throw new NoSuchElementException( );
28 current = null;
29 return;
30 }
31
32 StNode<AnyType> cnode;
33 for( ; ; )
34 {
35 cnode = s.topAndPop( );
36
37 if( ++cnode.timesPopped == 2 )
38 {
39 current = cnode.node;
40 if( cnode.node.getRight( ) != null )
41 s.push( new StNode<AnyType>( cnode.node.getRight( ) ) );
42 return;
43 }
44 // First time through
45 s.push( cnode );
46 if( cnode.node.getLeft( ) != null )
47 s.push( new StNode<AnyType>( cnode.node.getLeft( ) ) );
48 }
49 }
50 }
figure 18.28
The complete InOrder iterator class