COS 126 Prefix Code Assignment Hints

Part 0: preparation

Do the assigned readings and exercises on binary trees, especially Sedgewick 5.6-5.7.

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. Note that '\n' can be an character in the binary tree. You will know you're done building the tree when every internal node (i.e., node that stores '*' has two non-NULL children).

To test out maketree(), write a function preorder() that prints out the preorder traversal of the tree. Also, write main() so that it calls maketree() and then preorder(). 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 function, 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 print out only the external nodes (nodes containing a character other than '*').

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 babydecode() that reads in a single bit of the compressed message. We recommend using getchar() to read in a single character at a time. Make your function return 1 if it read in a 0 or 1, 0 if it read in another character like '\n', and EOF if there is no more input (in which case getchar() will return EOF). It is probably easiest to use iteration rather than recursion here. Modify main() so that it repeatedly calls babydecode(), and keeps track of the total number of bits read in. Be sure to thoroughly debug babydecode() before continuing: a mistake here will cause major problems later on.

Next, using the algorithm given in the assignment, replace babydecode() with the function decode() to decode one character from the original message. This involves reading in one or more of the compressed message bits. We recommend making decode() return the number of bits read in, or EOF if you've run out of input bits.

Modify main() so that it decodes the entire message by repeatedly calling decode(). (The assignment calls this function uncompress(), but it's probably easier not to create an extra function.)

Kevin Wayne