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

1 // PreOrder class; maintains "current position"
2 //
3 // CONSTRUCTION: with tree to which iterator is bound
4 //
5 // ******************PUBLIC OPERATIONS**********************
6 // boolean isValid( ) --> True if at valid position in tree
7 // AnyType retrieve( ) --> Return item in current position
8 // void first( ) --> Set current position to first
9 // void advance( ) --> Advance (prefix)
10 // ******************ERRORS*********************************
11 // Exceptions thrown for illegal access or advance
12
13 class PreOrder<AnyType> extends TreeIterator<AnyType>
14 {
15 /**
16 * Construct the iterator. The current position is set to null.
17 */
18 public PreOrder( BinaryTree<AnyType> theTree )
19 {
20 super( theTree );
21 s = new ArrayStack<BinaryNode<AnyType>>( );
22 s.push( t.getRoot( ) );
23 }
24
25 /**
26 * Set the current position to the first item, according
27 * to the preorder traversal scheme.
28 */
29 public void first( )
30 {
31 s.makeEmpty( );
32 if( t.getRoot( ) != null )
33 {
34 s.push( t.getRoot( ) );
35 advance( );
36 }
37 }
38
39 public void advance( )
40 { /* Figure 18.30 */ }
41
42 private Stack<BinaryNode<AnyType>> s; // Stack of BinaryNode objects
43 }

figure 18.29
The PreOrder class
skeleton and all
members except
advance

At line 42, we added a stack of tree nodes to the TreeIterator data fields.
The constructor and first methods are similar to those already presented. As
illustrated by Figure 18.30, advance is simpler: We no longer need a for loop.
As soon as a node is popped at line 17, it becomes the current node. We then
push the right child and the left child, if they exist.

Popping only once
allows some
simplification.