Level-order Traversal of a forest represented as a binary tree.

COM1201 Spring 1999 Programming Assignment 1

You are required to write a program which performs a level-order traversal of forest represented as a binary tree. Besides printing out the traversal, you must print the contents of the queue each time a node is visited. For the present, the key value in the nodes of the forest will be a single character.

I will provide you with a function which reads a forest from a file in the following format. :

Example from Figure 4.6 on p. 43 of Sedgewick text adjusted to 0-origin
11
A S A M P L E T R E E
2 2 9 7 7 7 7 8 9 9 9
Your main program file should look as follows. You will be supplied with the file forest.h which contains the function load_forest(). 
#include "forest.h"
#define MAX_TREE_NODE 100

FILE *f1;

struct tnode {
        char key;
        tnode *left;
        tnode *right;
        };

typedef struct tnode * tnode_ptr;

tnode_ptr root;

main(int argc, char *argv[])
{
  char c;

  f1 = fopen(argv[1],"r");
        
  root = load_forest();
  preorder_traverse(root);

  fclose(f1);
  exit(0);
}
To complie and run tour code on unix systems do the following:

To Compile: g++ -o traverse traverse.c loadf.o

I assume that your code file is traverse.c and I will supply a file called loadf.o which has the code for loading the forest from a file.

To run: traverse forest.dat

where forest.dat is a data file containing a forest in the format specified above.

Extra Credit: I will give extra credit to anyone who writes their own code to handling the loading of a forest as a binary tree.

Hint: You will need to implement the queue data structure in order to perform level-order traversal of a forest.

Last Updated: April 5, 1999 8:47 pm by

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1101/HW/PROG/LevelOrder.html