public class Node<T extends Comparable<T>> { private T data; private Node<T> lef
ID: 3824653 • Letter: P
Question
public class Node<T extends Comparable<T>> {
private T data;
private Node<T> left;
private Node<T> right;
public Node(){
data = null;
left = null;
right = null;
}
public Node(T t){
data = t;
left = null;
right = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public void addNode(Node<T> newNode){
}
@Override
public String toString(){
}
}
Code: Binary Search Tree
---------------------------------------------------------------------------------------------
Activity 1: Add
First, download the files Node.java and BinarySearchTree.java from Resources > Lab Files > Lab 13. Here you will find the basics for a binary tree. Look over both classes and make sure that you understand what is provided, specifically why for the generic we have <T extends Comparable<T>> (ask the TA if you are not sure). You will need to complete the addNode method for the Node class. If you need a reminder of how add works in a Binary Search Tree, please review the lecture notes or ask a TA. Remember that T is of type Comparable, think about what this allows us to use. Next complete the add method in the BinarySearchTree class, think about what happens when the root is null.
Activity 2: Print
Next complete the toString method in both classes. The string should return the in-order traversal of the tree (subtree for the node class). Use the main method of the BinarySearchTree class to test your add method by creating at least 5 Node objects and one tree. The String or Integer classes are good for testing. Remember that when a BinarySearchTree is traversed in-order the output should be in sorted order, use this to test your code.
Activity 3: Find
Next write the find method in the BinarySearchTree class. Find is very similar to add except that you are simply looking for the node and not adding it (technically you are looking for the data that is passed in).
Activity 4: Remove
As we know from class there are two different ways to remove a node in a Binary Search Tree (assuming it has two children). We can either remove (1) the largest value in the left subtree, or (2) the smallest value in the right subtree. You will need to implement two methods, one called removeRight which will replace the node being removed with the correct value from the right subtree and removeLeft which will replace the node being removed with the correct value from the left subtree. Remember that there are other cases that need to be handled. For example, when the node has no children or when it has only one child. For the remove method we first need to find the node containing the data and then remove, of course how we remove it depends on how many children it has. Hint 1: A while loop can help to find the value needed to replace the node being removed. Be sure to keep track of two nodes while looping. Hint 2: We don't really need to replace the node, only the data contained in it. Hint 3: There is a corner case that you need to keep in mind, for example, what happens when the first node in the right subtree doesn't have a left child (also think about a similar case for the left subtree).
Activity 5: Sort
From before we know that an in-order traversal of a Binary Search Tree will visit the nodes in sorted order. We are going to use this to our advantage to sort an ArrayList. For this we will have two methods, the sort method that takes in an ArrayList of values to sort and returns a new ArrayList with the sorted values. The second, inOrderSort, will take in an ArrayList and a Node and will traverse the subtree of the given node, in-order, adding elements to the ArrayList. This second method is almost identical to the toStirng method that you wrote earlier except that instead of creating a String of the data you will add the data to the ArrayList. In the sort method you will need to add all the elements to a BinarySearchTree, create a new empty ArrayList and pass both of these to the inOrderSort method.
Because both of these methods are static the generic used in both should be different from the one in the class. The <E extends Comparable<E>> is needed to allow the static method to handle generics, otherwise the method header is the same as other methods.
Finally test your sort method in the main method. After your sort method is working correctly in your tests analyse the code and try to figure out the complexity class. In addition, time the method with various size inputs (just write a for loop and use the Random class to populate the ArrayList). To time the method use the technique that we used in the Algorithms lab. Are the times that you record consistent with your prediction of the order class? Compare this with the other times you have for other sort methods from the Algorithms lab.
Explanation / Answer
Activity 1: addNode method :
public void add(T t) {
root = add(root, t);
}
private Node<T> add(Node<T> p, T toInsert) {
if (p == null)
return new Node<T>(toInsert);
if (compare(toInsert, p.getData()) == 0)
return p;
if (compare(toInsert, p.getData()) < 0)
p.setLeft(add(p.getLeft(), toInsert));
else
p.setRight(add(p.getRight(), toInsert));
return p;
}
private int compare(T t, T data) {
if (comparator == null)
return t.compareTo(data);
else
return comparator.compare(t, data);
}
Activity 2 : Print in both classes ,first Node followed by BST class:
@Override
public String toString(){
return data.toString();
}
BST.java
@Override
public String toString() {
String inOrder = inorderTraversal(root);
return inOrder;
}
private String inorderTraversal(Node r) {
StringBuffer temp = new StringBuffer();
if (r != null) {
inorderTraversal(r.getLeft());
temp.append(r + " ");
inorderTraversal(r.getRight());
}
return temp.toString();
}
Activity 3 : find method :
public boolean find(T data) {
return find(root, data);
}
private boolean find(Node<T> p, T data) {
if (p == null)
return false;
else if (compare(data, p.getData()) == 0)
return true;
else if (compare(data, p.getData()) < 0)
return find(p.getLeft(), data);
else
return find(p.getRight(), data);
}
Activity 4 : Remove :
public void removeRight(T t) {
root = removeRight(root, t);
}
private Node<T> removeRight(Node<T> p, T t){
if(p == null) throw new RuntimeException("Cannot Remove");
else
if(compare((T) p.getRight(), t) > 0){
p.setRight(removeRight(p.getRight(), t));
}
else{
p.setData(retrieveData(p.getLeft()));
p.setLeft(removeRight(p.getLeft(), p.getData()));
}
return p;
}
private T retrieveData(Node<T> p)
{
while (p.getRight() != null) p = p.getRight();
return p.getData() ;
}
public void removeLeft(T t) {
root = removeLeft(root, t);
}
private Node<T> removeLeft(Node<T> p, T t){
if(p == null) throw new RuntimeException("Cannot Remove");
else
if(compare((T) p.getLeft(), t) > 0){
p.setLeft(removeLeft(p.getRight(), t));
}
else{
p.setData(retrieveData(p.getRight()));
p.setRight(removeLeft(p.getRight(), p.getData()));
}
return p;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.