Java Reference
In-Depth Information
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
)
Search WWH ::
Custom Search