Program #6 Binary Search Trees Total points: 100 Objectives Write and use a linked implementation of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Program #6 Binary Search Trees Total points: 100 Objectives Write and use a linked implementation of a binary search tree. Problem Description In this assignment, you will practice solving a problem using a binary search tree. You will implement a Java application that could be used in a restaurant. You are asked to implement four classes: Menultem, BSTNode, BST and Driver. Each of these classes is described below. Classes The method names, parameters and return types must match the specification exactly. You may add other methods if you wish. Menultem Class The Menultem class represents one item ordered from a menu. The Menultem has three instance variables: name (of type String), qty (of type int) and price (of type double). Implement the following methods for the Menultem class: Menultem (String, int, double): A constructor to initialize all instance variables. A value for each instance variable will be passed as a parameter to the constructor. The parameters must be in the order (name, qty and price). The instance variable name will be used as the search key and as the instance variable that will determine the order in which the items are stored in the binary search tree. Getters for all instance variables. Setter methods for each instance variable. equals(): Implement the equals() method for your Menultem where two Menultems are considered equal when they have the same search key (name). Other instance variables must be ignored. Use the standard signature for the equals() method. Note that, the equality of String attributes should be case insensitive. For example, "MATH", "math" and "Math" match each other. In order to compare strings in Java use the String's equalsignoreCase() method. For example, the following code should print true: String strl = "Hello"; String str2 = "hello"; System.out.println (strl.equals Ignore Case (str2)); toString(): a method that returns a nicely formatted string description of the item. All items should be separated by tabs (use "\t") and the entire Menultem should be displayed on one line with no labels. In addition to name, price and qty, calculate the total value of the Menultem (price* qty) and add it to the end of the string. BST Rice $1.50 3 $4.50 Use the Number Format or Decimal Format class to display prices with exactly two digits following the decimal place. Implement the Comparable interface and the compareTo() method for Menultem. compareTo() returns a negative number when the invoking object's search key (name) is less than the parameter's search key BSTNode Class Create a BSTNode class. You must create your own BSTNode class and you may not use any node classes from the Java library. The BSTNode instance variables consist of data and two links, left and right. The data instance variable must be of type Menultem. O when the two search keys (names) are equal a positive number when the invoking object's search key (name) is greater than the parameter's search key For example, "ant".compareTo("bat") will return a negative number. Note that the comparison of String attributes should be case insensitive. For example, "MATH", "math" and "Math" match each other. Base the comparison only on the search key. All other instance variables must be ignored. The instance variables must be private. BSTNode(data: Menultem, left: BSTNode, right: BSTNode): Implement a constructor with parameters data, left and right, in that order. Implement getters and setters for all instance variables. Your BST class must be separate from your BSTNode class. You may implement a generic BSTNode class if you like. The Menuitems data must be stored in a recursive binary search tree data structure. This means the data is stored in order according to the binary search tree principles. You must create your own binary search tree class (separate from the BSTNode class) and implement the recursive methods you need. You must create your own BST class and you may not use any tree classes from the Java library. Be sure to implement encapsulation by having a clean separation between the node and binary search tree classes. Do this by making the instance variables private in both classes and by putting methods that manipulate more than one node in the BST class. Use a linked implementation. The BST class will have one private instance variable, root, which will hold a reference to the topmost node in the tree. Implement a no-arguments constructor that instantiates an empty binary search tree. The BST class methods must include these recursive methods: o void insert(Menultem mi): a method that takes one input parameter, a Menultem, and adds it to the binary search tree in the proper spot, preserving the binary search tree property. If the Menultem is already in the tree, insert() will not add a new item to the tree but rather will increment the qty of the existing item by the new qty. If the Menultem is not already in the tree, the method inserts the Menultem in its correct position void preorder() - traverses the tree in pre-order (based on the search key) and prints the contents of each Node o void postorder() - traverses the tree in post-order (based on the search key) and prints the contents of each Node o void inorder() - traverses the tree in post-order (based on the search key) and prints the contents of each Node o size(): a method that returns the number of nodes in the tree oint depth(): returns the height (depth) of the tree. Note: An empty tree has a height of -1. A tree with one node has height of 0. o getTotal Qty(): an integer method that sums and returns the quantities of all Menultems in the tree o Menultem search(String name) - traverses the tree and returns a reference to a Menultem with a search key (name) that matches the parameter. Returns null if not found. o o getTotal Before Tax(): a method that calculates and returns the total value of all items in the tree. Remember to multiply the price by the quantity to get the total for each item. getTax(): a method with one parameter, taxRate (a double). getTax() calculates and returns a double representing the tax to be paid on the order. Not recursive. getTip(): a method with one parameter, percentage (a double). getTip() calculates and returns a double representing the tip to be paid on the order's total before tax. Not recursive. o otoString(): a method that returns a string representation of all the Menultems in the tree. The items will be displayed in alphabetical order. The String includes the following: a restaurant name and some header lines details of all the Menultems, one per line the total of all the items in the tree before tax and tip been added the amount of tax to be added (use 8% when calling getTax()) Item the amount of tip to be added (use 20% when calling getTip()) the total after tax and tip have been added Sample of String returned from toString(): Downtown Cafe Injera Rice Sambusa Sushi Total: Tax: Tip: Price $2.50 $1.50 $5.80 $8.25 $46.70 $3.74 $9.34 Qty Total 1 N3WH 4 2 $2.50 $4.50 $23.20 $16.50 Grand total: $59.78 You are required to use the approach outlined in class with a public method with no arguments (one argument in the case of insert(), search(), getTax() and getTip()) and a private helper method. You may not directly access the root of the tree from the driver. You may not* implement a public getRoot() method. With the exception of inorder(), preorder() and postorder(), the BST class should not contain any print statements. All printing occurs in the Driver. Driver Use the Driver class to demonstrate that the BST class and its methods work properly. Create one or two BST trees. Add 8 to 15 Menultems to the trees. Change the order of insertion to test different tree topologies. Do not add the items in alphabetical order or your tree will degenerate to a linked list. Call all the BST methods and display the results. Be sure to test the case where the Menultem is already in the tree (insert() causes the existing item's quantity to be changed). Print both orders in a nicely formatted output. Other Use NumberFormat or DecimalFormat to display money with a dollar sign, commas and exactly two digits after the decimal place (e.g., $1,234.56). With the exception of inorder(), preorder() and postorder(), do not print from any class except the Driver. All instance variables must be private. Additional Requirements Provide a UML class diagram for the BST class. Provide a UML structure diagram. Provide an invariant for the BST class. You are not required to provide any other comments for this program although you may find that adding comments helps you to understand the problem. Implement the classes as described above. Use good coding style throughout (see slide deck 01-D Objects and Chapter 1 of your text) including o correct private/public access modifiers o consistent indenting o meaningful variable names o normal capitalization conventions o other aspects of easy-to-read code You are free to adopt and adapt code from the textbook and class slides. However, document the source of any borrowed code. Program #6 Binary Search Trees Total points: 100 Objectives Write and use a linked implementation of a binary search tree. Problem Description In this assignment, you will practice solving a problem using a binary search tree. You will implement a Java application that could be used in a restaurant. You are asked to implement four classes: Menultem, BSTNode, BST and Driver. Each of these classes is described below. Classes The method names, parameters and return types must match the specification exactly. You may add other methods if you wish. Menultem Class The Menultem class represents one item ordered from a menu. The Menultem has three instance variables: name (of type String), qty (of type int) and price (of type double). Implement the following methods for the Menultem class: Menultem (String, int, double): A constructor to initialize all instance variables. A value for each instance variable will be passed as a parameter to the constructor. The parameters must be in the order (name, qty and price). The instance variable name will be used as the search key and as the instance variable that will determine the order in which the items are stored in the binary search tree. Getters for all instance variables. Setter methods for each instance variable. equals(): Implement the equals() method for your Menultem where two Menultems are considered equal when they have the same search key (name). Other instance variables must be ignored. Use the standard signature for the equals() method. Note that, the equality of String attributes should be case insensitive. For example, "MATH", "math" and "Math" match each other. In order to compare strings in Java use the String's equalsignoreCase() method. For example, the following code should print true: String strl = "Hello"; String str2 = "hello"; System.out.println (strl.equals Ignore Case (str2)); toString(): a method that returns a nicely formatted string description of the item. All items should be separated by tabs (use "\t") and the entire Menultem should be displayed on one line with no labels. In addition to name, price and qty, calculate the total value of the Menultem (price* qty) and add it to the end of the string. BST Rice $1.50 3 $4.50 Use the Number Format or Decimal Format class to display prices with exactly two digits following the decimal place. Implement the Comparable interface and the compareTo() method for Menultem. compareTo() returns a negative number when the invoking object's search key (name) is less than the parameter's search key BSTNode Class Create a BSTNode class. You must create your own BSTNode class and you may not use any node classes from the Java library. The BSTNode instance variables consist of data and two links, left and right. The data instance variable must be of type Menultem. O when the two search keys (names) are equal a positive number when the invoking object's search key (name) is greater than the parameter's search key For example, "ant".compareTo("bat") will return a negative number. Note that the comparison of String attributes should be case insensitive. For example, "MATH", "math" and "Math" match each other. Base the comparison only on the search key. All other instance variables must be ignored. The instance variables must be private. BSTNode(data: Menultem, left: BSTNode, right: BSTNode): Implement a constructor with parameters data, left and right, in that order. Implement getters and setters for all instance variables. Your BST class must be separate from your BSTNode class. You may implement a generic BSTNode class if you like. The Menuitems data must be stored in a recursive binary search tree data structure. This means the data is stored in order according to the binary search tree principles. You must create your own binary search tree class (separate from the BSTNode class) and implement the recursive methods you need. You must create your own BST class and you may not use any tree classes from the Java library. Be sure to implement encapsulation by having a clean separation between the node and binary search tree classes. Do this by making the instance variables private in both classes and by putting methods that manipulate more than one node in the BST class. Use a linked implementation. The BST class will have one private instance variable, root, which will hold a reference to the topmost node in the tree. Implement a no-arguments constructor that instantiates an empty binary search tree. The BST class methods must include these recursive methods: o void insert(Menultem mi): a method that takes one input parameter, a Menultem, and adds it to the binary search tree in the proper spot, preserving the binary search tree property. If the Menultem is already in the tree, insert() will not add a new item to the tree but rather will increment the qty of the existing item by the new qty. If the Menultem is not already in the tree, the method inserts the Menultem in its correct position void preorder() - traverses the tree in pre-order (based on the search key) and prints the contents of each Node o void postorder() - traverses the tree in post-order (based on the search key) and prints the contents of each Node o void inorder() - traverses the tree in post-order (based on the search key) and prints the contents of each Node o size(): a method that returns the number of nodes in the tree oint depth(): returns the height (depth) of the tree. Note: An empty tree has a height of -1. A tree with one node has height of 0. o getTotal Qty(): an integer method that sums and returns the quantities of all Menultems in the tree o Menultem search(String name) - traverses the tree and returns a reference to a Menultem with a search key (name) that matches the parameter. Returns null if not found. o o getTotal Before Tax(): a method that calculates and returns the total value of all items in the tree. Remember to multiply the price by the quantity to get the total for each item. getTax(): a method with one parameter, taxRate (a double). getTax() calculates and returns a double representing the tax to be paid on the order. Not recursive. getTip(): a method with one parameter, percentage (a double). getTip() calculates and returns a double representing the tip to be paid on the order's total before tax. Not recursive. o otoString(): a method that returns a string representation of all the Menultems in the tree. The items will be displayed in alphabetical order. The String includes the following: a restaurant name and some header lines details of all the Menultems, one per line the total of all the items in the tree before tax and tip been added the amount of tax to be added (use 8% when calling getTax()) Item the amount of tip to be added (use 20% when calling getTip()) the total after tax and tip have been added Sample of String returned from toString(): Downtown Cafe Injera Rice Sambusa Sushi Total: Tax: Tip: Price $2.50 $1.50 $5.80 $8.25 $46.70 $3.74 $9.34 Qty Total 1 N3WH 4 2 $2.50 $4.50 $23.20 $16.50 Grand total: $59.78 You are required to use the approach outlined in class with a public method with no arguments (one argument in the case of insert(), search(), getTax() and getTip()) and a private helper method. You may not directly access the root of the tree from the driver. You may not* implement a public getRoot() method. With the exception of inorder(), preorder() and postorder(), the BST class should not contain any print statements. All printing occurs in the Driver. Driver Use the Driver class to demonstrate that the BST class and its methods work properly. Create one or two BST trees. Add 8 to 15 Menultems to the trees. Change the order of insertion to test different tree topologies. Do not add the items in alphabetical order or your tree will degenerate to a linked list. Call all the BST methods and display the results. Be sure to test the case where the Menultem is already in the tree (insert() causes the existing item's quantity to be changed). Print both orders in a nicely formatted output. Other Use NumberFormat or DecimalFormat to display money with a dollar sign, commas and exactly two digits after the decimal place (e.g., $1,234.56). With the exception of inorder(), preorder() and postorder(), do not print from any class except the Driver. All instance variables must be private. Additional Requirements Provide a UML class diagram for the BST class. Provide a UML structure diagram. Provide an invariant for the BST class. You are not required to provide any other comments for this program although you may find that adding comments helps you to understand the problem. Implement the classes as described above. Use good coding style throughout (see slide deck 01-D Objects and Chapter 1 of your text) including o correct private/public access modifiers o consistent indenting o meaningful variable names o normal capitalization conventions o other aspects of easy-to-read code You are free to adopt and adapt code from the textbook and class slides. However, document the source of any borrowed code.
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
for the equality test for M and N. The question concerns how to represent multisets of strings within ML. For each of the given data representations (a), (b) and (c) describe how you would implement...
-
123 Compare the purely graphical properties of these two notations, and the ways in which the graphical properties of each display correspond to the information structure being defined. Describe...
-
The tasks must you complete as part of building the subledger applications while implementing Oracle Accounting Hub Cloud? Explain.
-
Enter the following column headings across the top of a sheet of paper: Enter the transaction/adjustment letter in the first column and show the effect, if any, of the transaction entry or adjusting...
-
What would be your response to my feedback? The Big Mac index helps support the position that in the long run exchange rate prices should match the price of the same basket of goods in a different...
-
Snail Creek Kennel, Inc., earns service revenue by caring for the pets of customers. Snail Creeks main expense is the salary paid to an employee. Requirement 1. Write the accounting equation for the...
-
On November 1, 2007, Columbo Company adopted a stock option plan that granted options to key executives to purchase 30,000 shares of the companys $10 par value common stock. The options were granted...
-
A project involves an investment in a fixed asset of 5,000 and an annual payment surplus of 2,000 for three years. (The first payment comes one year after the investment.) The investment is...
-
After viewing the TedTalk Video: The Psychology of Culture and reading Chapter 2 respond to the following question: 1 page 6 https://youtu.be/rgdRzyCO5Zo Q2: Describe some of the factors one must...
-
iii) Briefly explain the phrase "echo-location". iv) Using the image to help your explanation, discuss how an ultrasound machine uses the principles of echo- location to examine internal body...
-
What is chemical shift in mri and why it changes with different magnetic field strengths? please give a clear and brief explanation in your own wording
-
ht Data for Hermann Corporation are shown below: Selling price Variable expenses Contribution margin Per Unit Percent of Sales $ 60 39 100% 65 $ 21 35% Fixed expenses are $72,000 per month and the...
-
Project D has an initial required investment of $950,000. The project will result in operating cash inflows of $200,000 per year for Years 1-3, $100,000 per year for Years 4-9, and have no cash flows...
-
John Dover had just completed an intensive course, "Statistical Thinking for Continuous Improvement," that was offered to all employees of a large health maintenance organization (HMO). There was no...
-
Georgeland Cycles makes and sells two models of electric bicycles. The Commuter (a folding model) sells for $2,511.00 and the Tour-X (a fat-tire trail model) sells for $4,511.00. Unit variable costs...
-
A test car is driven a fixed distance of n miles along a straight highway. (Here n Z+.) The car travels at one mile per hour for the first mile, two miles per hour for the second mile, four miles...
-
Write an O(n)-time non recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.
-
Professor Mason suggests that we modify ANY-SEGMENTS-INTERSECT so that instead of returning upon finding an intersection, it prints the segments that intersect and continues on to the next iteration...
-
Let Ax b be a system of m difference constraints in n unknowns. Show that the Bellman-Ford algorithm, when run on the corresponding constraint graph, maximizes n 1=1 x i subject to Ax b and x i 0...
-
Find the area under the standard normal curve to the right of a. z = 0.47 b. z = 2.91 c. z = 2.04 d. z = 1.09
-
Find the area under the standard normal curve that lies outside the interval between a. z = 0.38 and z = 1.02 b. z = 1.42 and z = 1.78 c. z = 0.01 and z = 2.67 d. z = 2.45 and z = 0.34
-
Find the area under the standard normal curve that lies outside the interval between a. z = 1.11 and z = 3.21 b. z = 1.93 and z = 0.59 c. z = 0.46 and z = 1.75 d. z = 2.73 and z = 1.39
Study smarter with the SolutionInn App