This is a java lab

CharTree.java

import java.io.*; import java.util.*; /** * Class invariant: This code for a binary tree satisfies the * binary search tree storage rule. * CSSSKL 143 * @author (your name) * @version (a version number or a date) /** */ public class CharTree { /*Inner class Node, 2 references(pointers), one data element * The only reason this inner class is static is that it is used in * the static methods insertInSubtree , isInSubtree , and * showElementsInSubtree. This class should have more methods. * This is just a sample of possible methods. */ private static class TreeNode { // Declare private data type char // Declare 2 links, rightLink & leftLink of type TreeNode // Parametrized constructor to build a node public TreeNode(char newData, TreeNode newLeftLink, TreeNode newRightLink) { // complete the constructor } } //End of IntTreeNode inner class // The first node of the tree, called root private TreeNode root; // Default constructor to build the CharTree public CharTree( ) { root = null; } // Utility methods for CharTree: public void add(char item) { root = insertInSubtree(item, root); } public boolean contains(char item) { return isInSubtree(item, root); } public void showElements( ) { showElementsInSubtree(root); } /** Returns the root node of a tree that is the tree with root node subTreeRoot, but with a new node added that contains item. */ private static TreeNode insertInSubtree(char item, TreeNode subTreeRoot) { if (subTreeRoot == null) return new TreeNode(item, null, null); else if (item = subTreeRoot.data subTreeRoot.rightLink = insertInSubtree(item, subTreeRoot.rightLink); return subTreeRoot; } } /** Returns true if item is found in the subTree, and false if not found. */ private static boolean isInSubtree(char item, TreeNode subTreeRoot) { // base case: is subTreeRoot null? then return false // else if subTreeRoot.data == item what would you return? // else item = link.data // recursive call //return stub (remove it) return false; } /** Print all tree node's data using inorder traversal. */ private static void showElementsInSubtree(TreeNode subTreeRoot) { if (subTreeRoot != null) { showElementsInSubtree(subTreeRoot.leftLink); System.out.print(subTreeRoot.data + " "); showElementsInSubtree(subTreeRoot.rightLink); } //else do nothing. Empty tree has nothing to display. } public static void main(String[] args) { CharTree tree = new CharTree(); tree.add('c'); tree.add('a'); tree.add('t'); tree.add('s'); showElementsInSubtree(tree.root); System.out.println("Testing contains:"); System.out.println("s is found: " + tree.contains('s')); System.out.println("b is found: " + tree.contains('b')); //Uncomment the remaining methods as you add them to the class. //Remember to have these public methods call a private helper method //to actually implement traversing the tree recursively. //System.out.println(tree.toString()); //inorder prints a c t //System.out.println("Number of nodes in tree: " + tree.countNodes()); //System.out.println("Tree depth: " + tree.getDepth()); //System.out.println("Parent of a: " + tree.getParent('a')); //can be tricky //System.out.println("Parent of s: " + tree.getParent('s')); //System.out.println("Parent of b: " + tree.getParent('b')); //Uncomment if doing the extra credit //removeDriver(); } public static void removeDriver() { CharTree tree = new CharTree(); tree.add('5'); tree.add('3'); tree.add('7'); tree.add('1'); tree.add('2'); tree.add('4'); tree.add('6'); tree.add('8'); tree.showElements(); //Test case 1: remove item not there //System.out.println("remove 9:" + tree.remove('9')); //false //tree.showElements(); //remains unchanged //Test case 2: remove a leaf //System.out.println("remove 4:" + tree.remove('4')); //true //tree.showElements(); // 1 2 3 5 6 7 8 //Test case 3: remove node with 1 child //System.out.println("remove 1:" + tree.remove('1')); //true //tree.showElements(); // 2 3 5 6 7 8 //Test case 4: remove node with 2 children //System.out.println("remove 7:" + tree.remove('7')); //true //tree.showElements(); // 2 3 5 6 8 //Test case 5: remove root //System.out.println("remove 5:" + tree.remove('5')); //true //tree.showElements(); // 2 3 6 8 } } 

MorseTree.java

import java.io.File; import java.io.FileNotFoundException; import java.util.*;; /* * MorseTree.java * CSSSKL 143 Binary Search Tree Lab * Author: Rob Nash * * This class reads in data from a text file ("data.txt") and populates a binary tree with an * ordering constraint. See the lab instructions for more information, but in general, dots go right * and dashes go left when constructing or traversing a Morse code tree. Search for //TODO * in the code to see what code you have to implement. * * Start with the constructor. In your constructor read each line in from the textfile first, * calling add() for each {letter, morseCodeStr} pair. * */ public class MorseTree { //TODO: data member called "root" goes here //TODO: Complete constructor public MorseTree() { //first, open data.txt, add each line to the tree Scanner fin; try { //for each line in the file, // get the letter(char) and the Morse string // call add() with this data // print out the letter and Morse string here for debugging } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } public void add(String morseStr, char letter) { root = insertInSubtree(morseStr, letter, root); } //TODO: recursively complete this function. It's only a few characters different from findInSubtree() private TreeNode insertInSubtree(String morseStr, char letter, TreeNode subtree) { //base case 1 : subtree is null //base case 2 : morseStr is of length 0 //recursive case 1: the first char in morseStr is a '.', so recursively traverse tree //recursive case 2: the first char in the morseStr is a '-', so recurse accordingly return subtree; //always the last line, always return the node you are working on } public Character translate(String morseStr) { return findInSubtree(morseStr, root); } //TODO: recursively complete this function. Very similar to insertInSubtree() private Character findInSubtree(String morseStr, TreeNode subtree) { //base case 1 : subtree is null //base case 2 : morseStr is of length 0 //recursive case 1: the first char in morseStr is a '.', so recursively traverse tree //recursive case 2: the first char in the morseStr is a '-', so re-curse accordingly return null; //remove this } //TODO: Non-recursive function that calls other (recursive) functions public String translateString(String tokens) { String retVal = ""; //build a scanner here using tokens as input //iterate over the tokens calling translate on each token (substring separated by a space) //concat these characters and return them return retVal; } public String toMorseCode(Character c) { . //walk the tree looking for the TreeNode with the char c in it //preorder walk? //inorder walk? //postorder walk? //when you've found the char c, report the path from the root to the node //and build the morse code by adding a "." when you go right, "-" when you go left return new String("You wish."); } public String toString() { return inorderWalk(); } private String inorderWalk() { return new String("Another wish."); } public static void main(String[] args) { MorseTree mt = new MorseTree(); //builds our tree using data from a file //System.out.println(mt.translate("...")); //prints out S //System.out.println(mt.translate("---")); //prints out O //System.out.println(mt.translate(".......-")); //prints out null //System.out.println(mt.translateString("... --- ...")); //SOS //System.out.println(mt.toMorseCode('S')); //find where we are in the tree, remember path to root } // Inner class to create the linked structure private class TreeNode { Object data; // holds a given nodes data TreeNode right; TreeNode left; public TreeNode() { this.data = null; this.right = null; this.left = null; } public void setRight(TreeNode rightNode) { this.right = rightNode; } public void setLeft(TreeNode leftNode) { this.left = leftNode; } } } 

Data.txt

A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. 0 ----- 1 .---- 2 ..--- 3 ...-- 4 ....- 5 ..... 6 -.... 7 --... 8 ---.. 9 ----. 

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). Dash Dot START E M G / YC F VH 0 9 8 7 61 2 3 4 5 1. Warmup with Chartree & CharNode 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'); System.out.println(tree.toString(); System.out.println(tree.countNodes(); System.out.println(tree.getDepth(); //inorder prints act //System.out.println(tree.contains('c')); 1/System.out.println(tree.getParent('a')); // can be tricky 1.1 Method Members private static boolean islnSubtree(char item, TreeNode subTreeRoot) . The private helper method called from the public method contains. Recursively traverse through the tree to find if the parameter item exist in the tree. Follow the comments in the CharTree.java template file to create the correct structure for this method. . For help, check out the method insertInSubtree that has an example of traversing through the tree. override toString() . Also create a private helper method that you will use to recursively traverse through the tree. . For help, check out the method showElementsInSubtree. Instead of printing out each tree node, add it to a string result to return at the end. public int countNodes() o Counts the number of nodes in the tree and returns that value. o Again, create a helper method to traverse through the tree. . You can think of the total number of nodes in a tree as 1 for the root + all nodes in the left sub tree + all nodes in the right sub tree. public int getDepth() Returns the depth, or height of the tree. In other words, the maximum number of levels (or steps) from the root to a leaf. (check the number of nodes from root to leaf and save the max). o Create a helper method to do the recursion. o At any root node, the depth is the maximum number of levels from its right sub tree or left sub tree. public char getParent(char child) o Returns the data value of the parent node for the parameter child. o Use a helper method for the recursion. . Would it be easier to stop when you find the child and then have to move back up the tree, or stop when the subtreeRoot's child is the child we are looking for? 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 donloading 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 o 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. Data Members Declare a private TreeNode called root (which is similar to head in linked lists) Method Members public void 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 void 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 void 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 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). Dash Dot START E M G / YC F VH 0 9 8 7 61 2 3 4 5 1. Warmup with Chartree & CharNode 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'); System.out.println(tree.toString(); System.out.println(tree.countNodes(); System.out.println(tree.getDepth(); //inorder prints act //System.out.println(tree.contains('c')); 1/System.out.println(tree.getParent('a')); // can be tricky 1.1 Method Members private static boolean islnSubtree(char item, TreeNode subTreeRoot) . The private helper method called from the public method contains. Recursively traverse through the tree to find if the parameter item exist in the tree. Follow the comments in the CharTree.java template file to create the correct structure for this method. . For help, check out the method insertInSubtree that has an example of traversing through the tree. override toString() . Also create a private helper method that you will use to recursively traverse through the tree. . For help, check out the method showElementsInSubtree. Instead of printing out each tree node, add it to a string result to return at the end. public int countNodes() o Counts the number of nodes in the tree and returns that value. o Again, create a helper method to traverse through the tree. . You can think of the total number of nodes in a tree as 1 for the root + all nodes in the left sub tree + all nodes in the right sub tree. public int getDepth() Returns the depth, or height of the tree. In other words, the maximum number of levels (or steps) from the root to a leaf. (check the number of nodes from root to leaf and save the max). o Create a helper method to do the recursion. o At any root node, the depth is the maximum number of levels from its right sub tree or left sub tree. public char getParent(char child) o Returns the data value of the parent node for the parameter child. o Use a helper method for the recursion. . Would it be easier to stop when you find the child and then have to move back up the tree, or stop when the subtreeRoot's child is the child we are looking for? 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 donloading 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 o 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. Data Members Declare a private TreeNode called root (which is similar to head in linked lists) Method Members public void 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 void 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 void 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