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/ XXXXXXXXXX/download?
download_frd=1) , MorseTree.java, (https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?
download_frd=1) data.txt (https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/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 co
esponding dots and dashes (“…”
and “…---…”, respectively).
1. Warmup with CharTree & CharNode
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/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 inne
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/ XXXXXXXXXX/download
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download
Data Members
Declare a private TreeNode called root (which is similar to head in linked lists)
Method Members
public MorseTree() {
Constructo
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 la
public String toString()
Look at this function inside MorseTree.java
Completing this step is optional for this la
[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 fo
emoving any other node, you will want access to the parent of the item you are removing since you will
e 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/ XXXXXXXXXX/download
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/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.