COS 126 Prefix Code Assignment Hints

Part 0: preparation

Do the assigned readings and exercises on binary trees.

Copy the files from /u/cs126/files/prefix to an empty directory.

Part 1: building the tree

This is, perhaps, the hardest part of the assignment. We recommend first reviewing the Sedgewick readings, especially Program 5.20.

First, write a helper function NEWnode() that takes as input a character, and two links. It should dynamically allocate memory (using malloc()) for a new node and initialize it appropriately. Finally, it should return a pointer to that node.

Next, write a function maketree() to read in the preorder traversal (from standard input) and create the corresponding binary tree. Hint: think recursively. We recommend using getchar() to read in a single character at a time.

To test out maketree(), write a function preorder() that prints out the preorder traversal of the tree. If all goes well, you should recover the original preorder traversal from the original input.

Helpful hint: the following compiler warning message

passing arg 1 of `NEWnode' with different width due to prototype

will occur if you pass a variable of type char to a function. In C, such variables are automatically converted to be of type int. When it is received in the funtion, it is converted back to be of type char. Therefore, it is safe to disregard this warning once you understand why it occurred.

Part 2: length

First, modify your preorder() function to only print out the external nodes.

Then modify it again to keep track of the current depth in the tree. Try to do it without using a global variable if you can.

Part 3: decoding

As a warmup, write a function that reads in the compressed message of 0's and 1's one character at a time. Count and print out the number of characters (0's and 1's) read in. We recommend using getchar() to read in a single character at a time. Check this function carefully because a mistake here will cause major problems when it comes time to write uncompress().

Next, using the algorithm given in the assignment, write a function decode() to decode one character from the original message. This involves reading in one or more of the compressed message bits.

Now, write the function uncompress() that decodes the entire message by repeatedly calling the function decode()

Kevin Wayne