Word Sorting with a Binary Tree

CSC 7000-002 Algorithms & Programming
Fall 1999, Mendel 115
Dr. David Matuszek

The idea of this assignment is to read in words and sort them alphabetically. The purpose of this assignment is to introduce recursion and recursively defined data structures.

Your program is to:

1. Get input and output file names from the command line.
2. Get words, one at a time, from the input file. (You should be good at this by now!)
3. Insert the words, one at a time, into a binary tree.
4. Do an inorder traversal of the tree (described below), and for each node you visit, write out a line containing the word and the number of times it occurred.

The result should be an alphabetized list of words, with each output line containing one word along with the number of times it occurred.

You need to keep a pointer (initially NULL) to a binary tree, which you might define as follows:

typedef struct node node;
typedef node *binary_tree;
struct node {
  char *word;
  int count;
  binary_tree left;
  binary_tree right;
};

Here's how you insert words, given a word and a (possibly NULL) a "binary tree" pointer:

1. If the pointer is NULL, create a new node, fill in its fields (the word, count=1, NULL, NULL), and set the pointer to point to this node.
2. If the pointer isn't NULL, compare the word in the node to which it points (use strcmp()).
   If the new word is
   1. less than the word in the node, insert the new word in the left subtree.
   2. equal to the word in the node, add one to the count in the node.
   3. greater than the word in the node, insert the new word in the right subtree.

Here's how you do an inorder traversal of a binary tree:

• If the binary tree is NULL, do nothing, otherwise
  1. Do an inorder traversal of the left subtree.
  2. "Visit" the root.
  3. Do an inorder traversal of the right subtree.

In this assignment, when you "visit" a node, print out the node contents: the word and its count.

You will be graded more strictly than in the past on (1) following directions, (2) good style, (3) good comments, and (4) appropriate use of functions. In addition, your program will be examined for any obvious memory leaks.