Recursion and BST In this assignment, you will implement a set data structure us
ID: 3852322 • Letter: R
Question
Recursion and BST
In this assignment, you will implement a set data structure using a binary search tree of characters.
Add a Java class called TreeSet to the project.
As an internal class, create a new class inside TreeSet called Node.
Implement the Node class with the following member data and methods:
A member variable of type char for the Node's key.
Three member variables of type Node for the left, right, and parent links.
Mutator methods for all four member variables, e.g., setParent,setLeft, setRight, and setData.
Implement the TreeSet class with the following member data and methods:
A member variable for the Root of the tree.
A member variable to track the Count of the number of data items in the tree.
Private methods that will act as “helpers”:
findKey(char key, Node n): recursively locates and returns the Node which contains the specified key in the tree below and including n. Returns null if no such node exists.
findMaximum(Node n): recursively finds and returns the Node with the largest key in the tree below and including n.
printInorder(Node n): recursively prints the Node called n and its children using an in- order traversal
Public Methods for:
add(char key): adds the key to the set.
You will need to add another private method addAt(char key, Node n) for this method, which recursively adds the key to the correct position below the node n.
remove(char key): removes the key from the set. You may add a helper method removeNode as in lecture if you so desire.
clear(): clears the set so it is empty.
find(char key): returns true if the set contains the given key.
getCount(): returns the number of keys in the tree.
getHeight(): returns the height of the tree, calculated recursively.
You will need another private method getHeight(Node n) for this method, which recursively(MUST BE RECURSIVE) calculates the height of the sub-tree starting at n.
printAll(): prints all the keys in the tree using an in-order traversal. Calls the recursive private helper method printInOrder starting at the tree's Root.
With the TreeSet class coded, create a new class in your project called TreeSetTest.
public class TreeSetTest {
public static void main(String[] args) {
TreeSet set = new TreeSet();
System.out.println("Empty tree count: " + set.getCount() +
"; height: " + set.getHeight());
System.out.println("Empty tree contains: ");
set.printAll();
System.out.println();
System.out.println("Add "doesitwork" to the set:");
System.out.println("Add 'd': " + set.add('d'));
System.out.println("Add 'o': " + set.add('o'));
System.out.println("Add 'e': " + set.add('e'));
System.out.println("Add 's': " + set.add('s'));
System.out.println("Add 'i': " + set.add('i'));
System.out.println("Add 't': " + set.add('t'));
System.out.println("Add 'w': " + set.add('w'));
System.out.println("Add 'o': " + set.add('o'));
System.out.println("Add 'r': " + set.add('r'));
System.out.println("Add 'k': " + set.add('k'));
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println("Tree structure:");
set.printTreeStructure();
System.out.println();
System.out.println("Test the contains method:");
System.out.println("Contains 'd? " + set.contains('d'));
System.out.println("Contains 't'? " + set.contains('t'));
System.out.println("Contains 'a'? " + set.contains('a'));
System.out.println("Contains 'x'? " + set.contains('x'));
System.out.println("Contains '@'? " + set.contains('@'));
System.out.println("Contains '5'? " + set.contains('5'));
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Test the remove method.");
System.out.println("Remove key with no children:");
System.out.println("Remove 'n': " + set.remove('n')); //may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (left) child:");
System.out.println("Remove 'e': " + set.remove('e'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (right) child:");
System.out.println("Remove 'o': " + set.remove('o'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with two children:");
System.out.println("Remove 'g': " + set.remove('g'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove root key:");
System.out.println("Remove 'l': " + set.remove('l'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
set.printTreeStructure();
System.out.println("Remove all remaining keys");
set.remove('b');
set.remove('a');
set.remove('c');
set.remove('s');
set.remove('h');
//may need to change the keys
System.out.println("Removing the LAST AND FINAL KEY:");
set.remove('t'); //may need to change the key
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
}
}
//RUN ^^^ this tester code, must execute properly.
Explanation / Answer
/**
*
* @author Sam
*/
public class TreeSet {
private Node findKey(char key, Node n) {
if (n == null)
return null;
else if (n.data == key)
return n;
else if (n.data < key)
return findKey(key, n.right);
else
return findKey(key, n.left);
}
private Node findMaximum(Node n) {
if (n == null)
return null;
else if (n.right == null)
return n;
else
return findMaximum(n.right);
}
private void printInorder(Node n){
if (n == null)
return;
printInorder(n.left);
System.out.println(n.data);
printInorder(n.right);
}
private boolean addAt(char key, Node n) {
if (n == null)
return false;
if (n.data == key)
return false;
if (key < n.data)
if (n.left == null) {
n.left = new Node();
n.left.setData(key);
n.left.setParent(n);
n.left.setRight(null);
n.left.setLeft(null);
return true;
}
else
return addAt(key, n.left);
else
if (n.right == null) {
n.right = new Node();
n.right.setData(key);
n.right.setParent(n);
n.right.setRight(null);
n.right.setLeft(null);
return true;
}
else
return addAt(key, n.right);
}
private boolean removeNode(char key, Node n){
if (n == null)
return false;
Node temp, parent;
if (n.data == key) {
temp = findMaximum(n.left);
parent = n.parent;
if (temp == null) {
parent.right = n.right;
parent.right.parent = parent;
}
else{
temp.parent.right = temp.left;
if (temp.left != null) {
temp.left.parent = temp.parent;
}
temp.left = n.left;
temp.right = n.right;
if (temp.left != null)
temp.left.parent = temp;
if (temp.right != null)
temp.right.parent = temp;
}
return true;
}
else if (key < n.data)
return removeNode(key, n.left);
else
return removeNode(key, n.right);
}
private int getHeight(Node n) {
if (n == null)
return 0;
else
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
class Node {
char data;
Node left;
Node right;
Node parent;
public void setData(char data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public void setParent(Node parent) {
this.parent = parent;
}
}
Node root;
int count;
public String add(char key) {
if (root == null) {
root = new Node();
root.setData(key);
root.setLeft(null);
root.setRight(null);
root.setParent(null);
count ++;
return "success";
}
else
if (addAt(key, root)) {
count ++;
return "Success";
}
else
return "failed";
}
public int getCount() {
return count;
}
public int getHeight() {
return getHeight(root);
}
public void printAll() {
printInorder(root);
}
public String remove(char key) {
if (key == root.data) {
Node temp = findMaximum(root.left);
if (temp != null) {
temp.parent.right = temp.left;
if (temp.left!=null)
temp.left.parent = temp.parent;
temp.left = root.left;
if (temp.left != null)
temp.right.parent = temp;
if (temp.right != null)
temp.left.parent = temp;
root = temp;
}
else
root = root.right;
count --;
return "success";
}
if (removeNode(key, root))
return "failed";
else {
count --;
return "success";
}
}
public void clear() {
count = 0;
root = null;
}
public String contains(char key) {
if (findKey(key, root)!= null)
return "Found";
else
return "notFound";
}
public static void main(String[] args) {
TreeSet set = new TreeSet();
System.out.println("Empty tree count: " + set.getCount() +
"; height: " + set.getHeight());
System.out.println("Empty tree contains: ");
set.printAll();
System.out.println();
System.out.println("Add "doesitwork" to the set:");
System.out.println("Add 'd': " + set.add('d'));
System.out.println("Add 'o': " + set.add('o'));
System.out.println("Add 'e': " + set.add('e'));
System.out.println("Add 's': " + set.add('s'));
System.out.println("Add 'i': " + set.add('i'));
System.out.println("Add 't': " + set.add('t'));
System.out.println("Add 'w': " + set.add('w'));
System.out.println("Add 'o': " + set.add('o'));
System.out.println("Add 'r': " + set.add('r'));
System.out.println("Add 'k': " + set.add('k'));
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println("Tree structure:");
//set.printTreeStructure();
System.out.println();
System.out.println("Test the contains method:");
System.out.println("Contains 'd? " + set.contains('d'));
System.out.println("Contains 't'? " + set.contains('t'));
System.out.println("Contains 'a'? " + set.contains('a'));
System.out.println("Contains 'x'? " + set.contains('x'));
System.out.println("Contains '@'? " + set.contains('@'));
System.out.println("Contains '5'? " + set.contains('5'));
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Test the remove method.");
System.out.println("Remove key with no children:");
System.out.println("Remove 'n': " + set.remove('n')); //may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (left) child:");
System.out.println("Remove 'e': " + set.remove('e'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (right) child:");
System.out.println("Remove 'o': " + set.remove('o'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with two children:");
System.out.println("Remove 'g': " + set.remove('g'));//may need to change the key
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove root key:");
System.out.println("Remove 'l': " + set.remove('l'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
//set.printTreeStructure();
System.out.println("Remove all remaining keys");
set.remove('b');
set.remove('a');
set.remove('c');
set.remove('s');
set.remove('h');
//may need to change the keys
System.out.println("Removing the LAST AND FINAL KEY:");
set.remove('t'); //may need to change the key
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.