Eric Roberts Handout #47CS106B May 17, 2009Section #7—TreesFor problems 1, 2, and 3, assume that nodeT is defined as follows:struct nodeT { string key; nodeT *left, *right;};1. Tracing the binary tree insertion algorithmDiagram the tree that results if you insert the strings "one", "two", "three", "four","five", "six", "seven", "eight", "nine", and "ten" into an empty tree in that order.Once you have finished, answer the following questions about your diagram:1a. What is the height of the resulting tree?1b. Which nodes are leaves?1c. Which nodes, if any, are out of balance?1d. Which key comparisons would be made to find the string "seven" in the tree?2. Calculating the height of a binary tree (Chapter 13, exercise 6, page 485)Write a functionint Height(nodeT *tree);that takes a binary search tree and returns its height.3. Checking whether a tree is balanced (Chapter 13, exercise 7, page 485)Write a functionbool IsBalanced(nodeT *tree);that determines whether a given tree is balanced according to the definition in the sectionon “Balanced trees.” To solve this problem, all you really need to do is translate thedefinition of a balanced tree more or less directly into code. If you do so, however, theresulting implementation is likely to be quite inefficient because it has to make severalpasses over the tree. The real challenge in this problem is to implement the IsBalancedfunction so that it determines the result without looking at any node more than once.4. Changing the interpreter into a compiler (Chapter 14, exercise 6, page 522)Although the interpreter program that appears in this chapter is considerably easier toimplement than a complete compiler, it is possible to get a sense of how a compiler worksby defining one for a simplified computer system called a stack machine. A stackmachine performs operations on an internal stack, which is maintained by the hardware,in much the same fashion as the calculator described in Chapter 4. For the purposes ofthis problem, you should assume that the stack machine can execute the operations shownin Figure 1 at the top of the next page.Write a functionvoid Compile(ifstream & in, ofstream & out);– 2 –Figure 1. Stack machine instructionsLOAD #n Pushes the constant n on the stack.LOAD var Pushes the value of the variable var on the stack.STORE var Stores the top stack value in var without actually popping it.DISPLAY Pops the stack and displays the result.ADDSUBMULDIVThese instructions pop the top two values from the stack and apply theindicated operation, pushing the final result back on the stack. The topvalue is the right operand, the next one down is the left.that reads expressions from in and writes to out a sequence of instructions for the stack-machine that have the same effect as evaluating each of the expressions in the input fileand displaying their result. For example, if the file opened as in containsx = 7y = 52 * x + 3 * ycalling Compile(in, out) should write the following code to out:LOAD #7STORE xDISPLAYLOAD #5STORE yDISPLAYLOAD #2LOAD xMULLOAD #3LOAD yMULADDDISPLAY5. Constant folding (Chapter 14, exercise 7, page 523)After it parses an expression, a commercial compiler typically looks for ways to simplifythat expression so that it can be computed more efficiently. This process is calledoptimization. One common technique used in the optimization process is constantfolding, which consists of identifying subexpressions that are composed entirely ofconstants and replacing them with their value. For example, if a compiler encounteredthe expressiondays = 24 * 60 * 60 * secthere would be no point in generating code to perform the first two multiplications whenthe program was executed. The value of the subexpression 24 * 60 * 60 is constant andmight as well be replaced by its value (86400) before the compiler actually starts togenerate code.Write a function FoldConstants(exp) that takes an expressionT and returns a newexpressionT in which any subexpressions that are entirely composed of constants arereplaced by a new constant node containing the computed
View Full Document
Unlocking...