COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Programming Assignment 4 -- Level-order Traversal of a Binary Tree

Due Date: Friday, December 11 (at the start of the lab session)

Objectives

• To gain experience in programming with linked tree structures.
• To learn about the method of level-order traversal of a tree.
• To gain experience in using a pre-written class in the implementation of another class.

Assignment

Revise the implementation of a binary search tree provided in

\\Bach\Sys\Public\CSC210\P4

In a level-order traversal, the nodes of a tree are visited level by level: the root is visited first, then the immediate children of the root, then the grandchildren of the root, and so on.

Copy the files 'treesrch.cpp' and 'bintree.h' from the '...\CSC210\P4' directory to a working directory in your home directory tree, and create a new project file 'treesrch' which will read any additional include files it needs from '...\CSC210\P4'.

Revise the 'main()' function in 'treesrch.cpp' so that it calls a new traversal function which you will provide, 'levelordertrav()', instead of 'inordertrav()'. In the same file, revise the 'printNode()' function so that it will correctly print the contents of a given node assuming it is being called as part of a level-order traversal of the tree. In particular, instead of printing a number of vertical bar characters to represent the level of the current node, it should print the contents of the current node on the same line as the previous node if the current and previous nodes are on the same level of the tree, or on a new line if the traversal has just descended to the next level of the tree. The first item printed on a new line should be indented by a few spaces (so we can tell whether a new level has just started or whether the previous level has run onto the next line), and subsequent items on the same line should be separated by a few spaces.

In the file 'bintree.h', add a function 'levelordertrav()' to the 'BinTree' class which implements a level-order traversal. (You may replace or comment out 'indordertrav()', since it will no longer be needed.)

Hints

1. Use a queue.
2. Level-order traversal is not recursive.
3. You will need to find (choose) some method of keeping track of the level of each node in the tree so that the 'printNode()' function will know when to start a new line. You could:
   • Enqueue instances of a class of your own devising which includes both a pointer to the node to be visited and an integer indicating its level.
   • Add a field to 'Btnode' which contains the level of the current node. You would then need to write an auxiliary function which traverses the list prior to performing the level-order traversal, storing the level of each node in its level field.

Grading

Ensure that your name is included in the header of the final version of each of your header files (both 'treesrch.cpp' and 'bintree.h') and submit an electronic copy of them for grading by e-mailing them to mohrj@augustana.ab.ca. Hand in a hardcopy listing of the changed portions of your class implementation as well.

Your implementation will be graded according to the following weighted criteria: