CS 12, Fall 2008
Assignment 4

This assignment includes some review questions that are meant to help you prepare for the final exam, and a C program to practice implementing binary trees. The program presents some challenging problems, but you can find clues in the text, and we insist you pursue those clues rather than ask us to show you exactly how to solve the problems this time.

Due Wednesday, December 3, 9:00pm

  1. Type answers to the following review questions and exercise from the Standish text into a plain text file named hw4.txt. Label your answers to match the problem numbers, so we can easily identify the problems you are answering.
    1. Page 219 - 6.3 Review Questions 1 and 2
    2. Page 341 - 9.2 Review Questions 1, 2, 3 and 4
    3. Page 364 - 9.6 Exercise 1 (not review question 1)
    4. Page 468 - 11.4 Review Questions 1, 2 and 5
    5. Page 488 - 11.6 Review Question 1
    6. Page 547 - 13.4 Review Questions 1 and 2
    Be sure to type your name and the date at the beginning of the file.
  2. Complete translate.c to create and use an expression tree to translate prefix expressions to infix and postfix forms. Begin with this skeleton program You must implement the following four functions (but it is okay to add utility functions too):
    1. Node *createTree(char *prefixString) - is the text's 9.6 Exercise 3 on page 364. You must use the Node type already defined in the program skeleton - each node consists of a character symbol (operator or 1-character operand) and links to left and right subtrees. Assume the input string is a proper prefix expression, and it does not contain any spaces.
    2. void printInfix(Node *tree) - is the text's 9.6 Exercise 4 on page 364. See those instructions. Print the infix expression to stdout without any spaces - match the infix expressions in this correct output.
    3. printPostfix(Node *tree) - is much easier than the infix function. Print the postfix expression to stdout without any spaces, to match the correct output.
    4. void freeTree(Node *tree) - is for freeing the memory used by all nodes in the expression tree. Be sure to free each one. (Hint: use a post-order traversal; this one is relatively easy too).
    Copies of the program skeleton, our executable solution, and the output are in ~mikec/cs12/hw4/ at CSIL.
  3. Test everything at CSIL. Then turn in both required files at once from your engineering account as follows:
    turnin hw4@cs12 hw4.txt translate.c
    Late projects may not be accepted.
Updated 11/14/08 by C. Michael Costanzo