Lab 10 Due Wednesday by 11:59pm Points 3 Submitting a file upload Available Mar 10 at 12am - Mar 19 at 11:59pm 10 days Start Assignment CSSSKL 143 Lab: Binary Search Tree and Morse Tree Submit *.java...

1 answer below »
In java language


Lab 10 Due Wednesday by 11:59pm Points 3 Submitting a file upload Available Mar 10 at 12am - Mar 19 at 11:59pm 10 days Start Assignment CSSSKL 143 Lab: Binary Search Tree and Morse Tree Submit *.java files with comments on the lab solutions for all the segments Files for this lab: CharTree.java (https://canvas.uw.edu/courses/1541396/files/85904301/download? download_frd=1) , MorseTree.java, (https://canvas.uw.edu/courses/1541396/files/85904302/download? download_frd=1) data.txt (https://canvas.uw.edu/courses/1541396/files/85904304/download? download_frd=1) Summary In this lab, we will build a k-nary tree (where k == 2) that also maintains an ordering property. Samuel Morse’s code is pictured below, where the rule is: “dashes go left” and “dots go right”. Once we’ve built and populated our Binary Search Tree so it looks like the tree below, we will be able to traverse the tree and use it to translate a given Character (‘S’) or String (“SOS”) into corresponding dots and dashes (“…” and “…---…”, respectively). 1. Warmup with CharTree & CharNode https://canvas.uw.edu/courses/1541396/files/85904301/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904301/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904302/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904302/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904304/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904304/download?download_frd=1 Build a small Binary Search tree that stores characters in its nodes. It should observe the class invariant that for any given node, all nodes in the left subtree are less than that node (alphabetically) and all nodes in the right subtree are greater than that node. Implement all incomplete methods in CharTree.java and use the driver provided to print out your tree of characters in order. public static void main(String[] args) {         CharTree tree = new CharTree();   tree.add('c');   tree.add('a');   tree.add('t');   tree.add('b');   tree.add('s');   tree.add('v');   showElementsInSubtree(tree.root);         System.out.println();   System.out.println(tree.isInSubtree('t', tree.root));   System.out.println(tree.isInSubtree('z', tree.root));   } 2. Introduction to the Morse Tree In this section, we’ll build our TreeNode inner class that will be used by our MorseTree outer class. Once we’ve made our TreeNode, we’ll complete some methods in MorseTree that will make use of these TreeNodes to build a data structure analog of the tree pictured above. Let’s start by downloading the skeleton file (MorseTree.java) and read the comments in their entirety. They will draw your attention to specific sections in the code you must complete, starting with the TreeNode class below 2.1 TreeNode Inner Class In this section, we’ll build an internal class using generics that can store one data item and two TreeNodereferences (one for the left child, one for the right). Start by uncommenting the private inner class called TreeNode, at the end of MorseTree.java. Data & Method Members Declare a “Object data;” item to hold a given node’s data Declare two TreeNode references called left and right Declare one constructor that takes three parameters and populates the data members for this structure. 2.2 The MorseTree (Enclosing) Class In this section, we’ll build our MorseTree class by declaring only one private data item (a TreeNode) and multiple public (and private) methods. A common pattern here will be as follows: Clients of our code will call some public method (say, add(int data)) and our public method will redirect to a private method (insertIntoSubtree(data, root)). We’ll follow this pattern in the methods we implement below. See the Tree code in your Savitch text for additional code samples and guidance. https://canvas.uw.edu/courses/1541396/files/85904302/download https://canvas.uw.edu/courses/1541396/files/85904302/download Data Members Declare a private TreeNode called root (which is similar to head in linked lists) Method Members public MorseTree() { //Constructor Use this to load data from a file (“data.txt”) and populate your Binary Tree Each line in the file is a pair, as in “S …”, which is the letter followed by the morse code equivalent Call the add() function below for each pair read from the file. private TreeNode insertInSubtree(String morseStr, Character letter, TreeNode subtree) Note that the public add() function has been provided for you Walk the tree while morseStr.length() > 0 , removing the leading character from the morse string and… Create a new TreeNode if your subtree is null. Recursively move down the tree, going right if a “.” and left if a “-“. public Character findInSubtree(String morseStr, TreeNode subtree) Note that the outer (wrapper) function translate() has been provided for you. Walk the tree while the morseStr.length() is greater than 0, removing the leading character from the morse string and… Recursively move down the tree, going right if we encounter a “.” and left otherwise. public void toMorseCode() Look at this function inside MorseTree.java Completing this step is optional for this lab public String toString() Look at this function inside MorseTree.java Completing this step is optional for this lab [Extra Credit] Implement a remove() method for CharTree (1pt) For extra credit, implement a remove() method that removes a particular node from CharTree. Below the main method in CharTree, you can see the utility method for remove and the private method to implement this functionality. Within the main method, you will also see some test code that you can use to test your remove() functionality. The remove() method can be complex because the way you remove a node will be different depending on the node. Removing the root node will be a special case, but for removing any other node, you will want access to the parent of the item you are removing since you will be setting the parent to have a new child. These are the possible cases: Removing a node that doesn't exist. (You don't need to remove anything.) Removing a leaf node (a node that doesn't have any children) https://canvas.uw.edu/courses/1541396/files/85904302/download https://canvas.uw.edu/courses/1541396/files/85904302/download Removing a node with 1 child. Removing a node with 2 children. Removing the root node. Start in this order of this list, and try to get as many cases as possible! This functionality can be tough, so an attempt and an explanation for how you might want to cover each case will count for extra credit as well. Drawing pictures of the tree will be useful when trying to figure this out.
Answered 3 days AfterMar 13, 2022

Answer To: Lab 10 Due Wednesday by 11:59pm Points 3 Submitting a file upload Available Mar 10 at 12am - Mar 19...

Shubham answered on Mar 17 2022
99 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here