Java Reference
In-Depth Information
24.16
Preorder, postorder, and level-order traversals.
Figure 24-6 shows the result of using a stack to
perform a preorder traversal and a postorder traversal of the tree in Figure 24-4. A level-order tra-
versal has logic similar to that of a preorder traversal, but we use a queue instead of a stack.
FIGURE 24-6
Using a stack to traverse a binary tree in (a) preorder;
(b) postorder
(a)
Traversal order:
a
b
d
e
c
f
g
a
b
c
d
Stack after
each
push
or
pop
b
e
e
e
d
e
f
c
c
c
c
f
g
a
c
g
(b)
d
e
b
f
a
Traversal order:
g
c
g
d
e
b
f
c
f
c
f
c
Stack after
each
push
or
pop
b
b
b
b
c
c
a
a
a
a
a
a
a
a
a
a
a
Figure 24-7 shows the result of using a queue to perform a level-order traversal of the same tree.
We leave the implementation of the necessary iterator classes for you as an exercise.
FIGURE 24-7
Using a queue to traverse a binary tree in level order
Queue (front to
back) after each
enqueue
or
dequeue
a
Traversal
order
c
b
a
a
d
e
f
b
b
c
g
b
c
c
d
de
de
e
f
d
e
f
f
f
g
g
