Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Breadth-First Traversal

Program gif defines the breadthFirstTraversal method of the AbstractTree class. As defined in Section gif, a breadth-first traversal of a tree visits the nodes in the order of their depth in the tree and at each level the nodes are visited from left to right.

   program15584
Program: AbstractTree class breadthFirstTraversal method.

We have already seen in Section gif a non-recursive breadth-first traversal algorithm for N-ary trees. This algorithm makes use of a queue as follows. Initially, the root node of the given tree is enqueued, provided it is not the empty tree. Then, the following steps are repeated until the queue is empty:

  1. Remove the node at the head of the queue and call it head.
  2. Visit the object contained in head.
  3. Enqueue in order each non-empty subtree of head.
Notice that empty trees are never put into the queue. Furthermore, it should be obvious that each node of the tree is enqueued exactly once. Therefore, it is also dequeue exactly once. Consequently, the running time for the breadth-first traversal is tex2html_wrap_inline60208.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.