CSE143 Sample Final (Part 2) handout #31 1. Binary Trees, 10 points. Write a method purebredOdds that returns the number of purebred odd values in a binary tree of integers. A purebred odd is an odd number all of whose ancestors in the tree are also odd numbers. For example, suppose that a variable t refers to the following tree: +----+ | 15 | +----+ / \ / \ +----+ +----+ | 27 | | 34 | +----+ +----+ / \ \ / \ \ +----+ +----+ +----+ | 29 | | 75 | | 83 | +----+ +----+ +----+ / \ / \ / \ / \ +----+ +----+ +----+ +----+ | 18 | | 33 | | 46 | | 51 | +----+ +----+ +----+ +----+ Then the call t.purebredOdds() should return 5 because this tree has a total of 5 purebred odd values: 15, 27, 29, 75, and 33. The values 83 and 51 are odd numbers, but not purebred odd numbers because they have an even number as an ancestor in the tree (the value 34). Notice that if the overall root is an even number, then the tree will have no purebred odd numbers at all because every other node has the overall root as an ancestor. You are writing a public method for a binary tree class defined as follows: public class IntTreeNode { public int data; // data stored in this node public IntTreeNode left; // reference to left subtree public IntTreeNode right; // reference to right subtree <constructors> } public class IntTree { private IntTreeNode overallRoot; <methods> } You are writing a method that will become part of the IntTree class. You may define private helper methods to solve this problem, but otherwise you may not call any other methods of the class. 2. Comparable class, 20 points. Define a class FoodData that stores information about a food item. Each FoodData object keeps track of the name of the food along with its number of grams of fat, carbohydrate, and protein. For example: FoodData item1 = new FoodData("sausage biscuit", 31.0, 39.0, 11.0); FoodData item2 = new FoodData("strawberry sundae", 6.0, 49.0, 6.0); FoodData item3 = new FoodData("banana", 0.4, 31.1, 1.5); In calling the constructor, the name is followed by fat grams, followed by carbohydrate grams, followed by protein grams. For example, the sausage biscuit above has 31 grams of fat, 39 grams of carbohydrate, and 11 grams of protein. As in the third example, these values can be real numbers. Your constructor should throw an IllegalArgumentException if any of the numeric values passed to it is negative. This class is being designed for programs that will help people who want to use a low-fat diet. For example, it is a bit surprising that the McDonalds sausage biscuit (item1) gets over 58% of its calories from fat while the McDonalds strawberry sundae (item2) gets only 19.7% of its calories from fat. The banana (item3) gets less than 2.7% of its calories from fat. Your class should have the following public methods: getName() returns the name of this food item getCalories() returns total calories for this food item percentFat() returns the percent of calories from fat for this item toString() returns a String representation of this item To compute total calories and percent fat, assume that each gram of fat is 9 calories and that each gram of carbohydrate and protein is 4 calories. For example, the calories for the strawberry sundae (item2 above) are 274: 9 * (fat grams) + 4 * (carb grams) + 4 * (protein grams) = 9 * 6.0 + 4 * 49.0 + 4 * 6.0 = 274.0 Its percent fat is a little over 19.7 because the calories from fat are 54 and the total calories are 274. As usual, percentages should be expressed as real numbers in the range of 0.0 to 100.0. The toString method should include the name of the item followed by a colon followed by the fat, carbohydrate and protein grams, separated by commas, and labeled, as in the following examples for item1, item2, and item3 above: sausage biscuit: 31.0g fat, 39.0g carbohydrates, 11.0g protein strawberry sundae: 6.0g fat, 49.0g carbohydrates, 6.0g protein banana: 0.4g fat, 31.1g carbohydrates, 1.5g protein Your class should also implement the Comparable interface. Items should be ordered first by percent of calories coming from fat (lowest to highest) and then by name (sorted alphabetically). 3. Binary Trees, 20 points. Write a method mirror that converts a binary tree of integers to its mirror image. For example, if a variable called t stores a reference to a binary tree and you make the following call: t.mirror(); then the links of the tree should be rearranged so that after the call, t stores the mirror image of what it stored before the call. Below is a specific example of how a tree would change: before | after +---+ | +---+ | 9 | | | 9 | +---+ | +---+ / \ | / \ / \ | / \ +---+ +---+ | +---+ +---+ | 6 | | 14| | | 14| | 6 | +---+ +---+ | +---+ +---+ / \ \ | / / \ / \ \ | / / \ +---+ +---+ +---+ | +---+ +---+ +---+ | 9 | | 2 | | 11| | | 11| | 2 | | 9 | +---+ +---+ +---+ | +---+ +---+ +---+ / \ | / \ / \ | / \ +---+ +---+ | +---+ +---+ | 4 | | 1 | | | 1 | | 4 | +---+ +---+ | +---+ +---+ After the call is made, the tree stores the structure that you would see if you were to hold the original tree's diagram up to a mirror. More precisely, the overall root (if it exists) remains in the same place in the mirror image and every other node is moved so that it's new path from the overall root is composed of the old path from the overall root with left and right links exchanged. For example, the node that stores 4 in the example above has the path (left, right, left) in the original tree. In the mirror image, it has path (right, left, right). The node that stores 1 has the path (left, right, right) in the original tree. In the mirror image it has path (right, left, left). You are writing a public method for a binary tree class defined as follows: public class IntTreeNode { public int data; // data stored in this node public IntTreeNode left; // reference to left subtree public IntTreeNode right; // reference to right subtree <constructors> } public class IntTree { private IntTreeNode overallRoot; <methods> } You are writing a method that will become part of the IntTree class. You may define private helper methods to solve this problem, but otherwise you may not call any other methods of the class. You may not construct any new nodes, and you may not use any auxiliary data structure to solve this problem (no array, ArrayList, stack, queue, String, etc). You also may not change any data fields of the nodes. You MUST solve this problem by rearranging the links of the tree.