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

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

figure 18.26
The PostOrder class
(complete class
except for advance )