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

figure 18.25
Stack states during
postorder traversal

a

b c

d e

d 0
b 2
a 1

d 1
b 2
a 1

d 2
b 2
a 1

b 0
a 1

b 1
a 1

b 2
a 1

a 0 a 1

d b

e 0
c 1
a 2

e 1
c 1
a 2

e 2
c 1
a 2

c 0
a 2

c 1
a 2
e

c 2
a 2

a 2

c a

time, and d is pushed back onto the stack. No other push is performed because
d has no left child. Thus d is popped for the second time and is pushed back,
but as it has no right child, nothing else is pushed. Therefore the next pop
yields d for the third time, and d is marked as a visited node. The next node
popped is b , and as this pop is b 's third, it is marked visited.
Then a is popped for the second time, and it is pushed back onto the stack
along with its right child, c . Next, c is popped for the first time, so it is pushed
back, along with its left child, e . Now e is popped, pushed, popped, pushed,
and finally popped for the third time (typical for leaf nodes). Thus e is marked
as a visited node. Next, c is popped for the second time and is pushed back
onto the stack. However, it has no right child, so it is immediately popped for
the third time and marked as visited. Finally, a is popped for the third time and
marked as visited. At this point, the stack is empty and the postorder traversal
terminates.

The PostOrder class is implemented directly from the algorithm described
previously and is shown, minus the advance method, in Figure 18.26. The
StNode nested class represents the objects placed on the stack. It contains a ref-
erence to a node and an integer that stores the number of times the item has
been popped from the stack. An StNode object is always initialized to reflect
the fact that it has not yet been popped from the stack. (We use a nonstandard
Stack class from Chapter 16.)
The PostOrder class is derived from TreeIterator and adds an internal
stack to the inherited data members. The PostOrder class is initialized by ini-
tializing the TreeIterator data members and then pushing the root onto the

An StNode stores a
reference to a node
and a count that
tells how many
times it has already
been popped.