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

1 // LevelOrder class; maintains "current position"
2 // according to a level-order traversal
3 //
4 // CONSTRUCTION: with tree to which iterator is bound
5 //
6 // ******************PUBLIC OPERATIONS**********************
7 // boolean isValid( ) --> True if at valid position in tree
8 // AnyType retrieve( ) --> Return item in current position
9 // void first( ) --> Set current position to first
10 // void advance( ) --> Advance (prefix)
11 // ******************ERRORS*********************************
12 // Exceptions thrown for illegal access or advance
13
14 class LevelOrder<AnyType> extends TreeIterator<AnyType>
15 {
16 /**
17 * Construct the iterator.
18 */
19 public LevelOrder( BinaryTree<AnyType> theTree )
20 {
21 super( theTree );
22 q = new ArrayQueue<BinaryNode<AnyType>>( );
23 q.enqueue( t.getRoot( ) );
24 }
25
26 public void first( )
27 { /* Figure 18.32 */ }
28
29 public void advance( )
30 { /* Figure 18.32 */ }
31
32 private Queue<BinaryNode<AnyType>> q; // Queue of BinaryNode objects
33 }

figure 18.31
The LevelOrder
iterator class skeleton

summary

In this chapter we discussed the tree and, in particular, the binary tree. We
demonstrated the use of trees to implement file systems on many computers
and also some other applications, such as expression trees and coding, that we
more fully explored in Part Three. Algorithms that work on trees make heavy
use of recursion. We examined three recursive traversal algorithms—preorder,
postorder, and inorder—and showed how they can be implemented nonrecur-
sively. We also examined the level-order traversal, which forms the basis for
an important searching technique known as breadth-first search. In Chapter 19
we examine another fundamental type of tree—the binary search tree .