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

1 /**
2 * Set the current position to the first item, according
3 * to the level-order traversal scheme.
4 */
5 public void first( )
6 {
7 q.makeEmpty( );
8 if( t.getRoot( ) != null )
9 {
10 q.enqueue( t.getRoot( ) );
11 advance( );
12 }
13 }
14
15 /**
16 * Advance the current position to the next node in the tree,
17 * according to the level-order traversal scheme.
18 * @throws NoSuchElementException if iteration has
19 * been exhausted prior to the call.
20 */
21 public void advance( )
22 {
23 if( q.isEmpty( ) )
24 {
25 if( current == null )
26 throw new NoSuchElementException( );
27 current = null;
28 return;
29 }
30
31 current = q.dequeue( );
32
33 if( current.getLeft( ) != null )
34 q.enqueue( current.getLeft( ) );
35 if( current.getRight( ) != null )
36 q.enqueue( current.getRight( ) );
37 }

figure 18.32
The first and advance
routines for the
LevelOrder iterator
class

key concepts

ancestor and descendant If there is a path from node u to node v, then u is an
ancestor of v and v is a descendant of u . (653)
binary tree A tree in which no node can have more than two children. A conve-
nient definition is recursive. (658)