Recursion and BST In this assignment, you will implement a set data structure us
ID: 3852341 • Letter: R
Question
Recursion and BST
In this assignment, you will implement a set data structure using a binary search tree of characters. You will use your set in a hangman-style game.
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 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 'k'? " + set.contains('k'));
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 'w': " + set.remove('w'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (left) child:");
System.out.println("Remove 'o': " + set.remove('o'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (right) child:");
System.out.println("Remove 'i': " + set.remove('i'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with two children:");
System.out.println("Remove 's': " + set.remove('s'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove root key:");
System.out.println("Remove 'd': " + set.remove('d'));
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('t');
set.remove('e');
System.out.println("Removing the LAST AND FINAL KEY:");
set.remove('k');
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
Here is the code for the question. It was test with your test program. Since 'o' appears twice in test program, it is added just once since the tree is a set. But there is one minor bug in test program. The test program should remove 'r' after it prints "Remove all remaining keys". Only 't' and 'e' are removed there. So I have modified the Test program for that as well.
Please post a comment if there any issues, I shall respond. Please rate the answer if you are happy with it. Thank you very much.
TreeSet
public class TreeSet {
class Node{
char key;
Node left, right, parent;
Node(char k)
{
key = k;
}
public void setKey(char key) {
this.key = key;
}
public void setLeft(Node left) {
this.left = left;
if(left != null)
left.setParent(this);
}
public void setRight(Node right) {
this.right = right;
if(right != null)
right.setParent(this);
}
public void setParent(Node parent) {
this.parent = parent;
}
}
private Node root;
int count;
private Node findKey(char key, Node n)
{
if(n == null)
return null;
if(n.key == key) //compare with n's key
return n;
Node found = findKey(key, n.left); //search for key in left subtree
if(found == null)
found = findKey(key, n.right); //if key was not found in left , search right
return found;
}
private Node findMaximum(Node n)
{
if(n == null)
return null;
//maximum will be the right most node of a bst, if no right , then this node itself
//is maximum
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.print(" " + n.key);
printInorder(n.right);
}
private boolean addAt(char key, Node n)
{
if(n == null || n.key == key) //don't add duplicates
return false;
if(key < n.key)
{
if(n.left == null)
{
n.setLeft(new Node(key));
}
else
return addAt(key, n.left);
}
else
{
if(n.right == null)
{
n.setRight(new Node(key));
}
else
return addAt(key, n.right);
}
return true;
}
public boolean add(char key)
{
if(root == null)
{
root = new Node(key);
count = 1;
}
else
{
if(addAt(key, root))
{
count++;
}
else
return false;
}
return true;
}
//removes a given node from tree
private boolean remove(Node n)
{
if(n == null)
return false;
else
{
if(n.left == null && n.right == null) //n does not have any children
{
if(n.parent == null) //removing the root
root = null;
else
{
if(n.parent.left == n) //is n the left child of parent
n.parent.setLeft(null);
else
n.parent.setRight(null);
}
}
else if(n.left == null && n.right != null) //only has right child
{
if(n.parent == null) //removing the root
{
root = n.right;
root.parent = null;
}
else
{
if(n.parent.left == n) //is n the left child of parent
n.parent.setLeft(n.right);
else
n.parent.setRight(n.right);
}
}
else if(n.left != null && n.right == null) //only has left child
{
if(n.parent == null) //removing the root
{
root = n.left;
root.parent = null;
}
else
{
if(n.parent.left == n) //is n the left child of parent
n.parent.setLeft(n.left);
else
n.parent.setRight(n.left);
}
}
else // has both left and right child
{
Node max = findMaximum(n.left);
n.setKey(max.key);
return remove(max);
}
}
return true;
}
public boolean remove(char key)
{
Node n = findKey(key, root);
if(n == null)
return false;
else
{
count--;
return remove(n);
}
}
public void clear()
{
root = null;
count = 0;
}
public int getCount()
{
return count;
}
private int getHeight(Node n)
{
//if there is no node or node is leaf, height is 0
if(n == null || (n.left == null && n.right == null))
return 0;
int leftHeight = getHeight(n.left), rightHeight = getHeight(n.right);
int nHeight = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
return nHeight;
}
public int getHeight()
{
return getHeight(root);
}
public void printAll()
{
printInorder(root);
System.out.println();
}
private void printTreeStructure(String indent, Node n)
{
if(n == null)
return;
System.out.println( indent + "|---"+ n.key);
printTreeStructure(indent+" ", n.left);
printTreeStructure(indent+" ", n.right);
}
public void printTreeStructure() {
printTreeStructure("", root);
}
public boolean contains(char key)
{
Node n = findKey(key, root);
return n != null;
}
}
TreeSetTest.java
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 'k'? " + set.contains('k'));
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 'w': " + set.remove('w'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (left) child:");
System.out.println("Remove 'o': " + set.remove('o'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with one (right) child:");
System.out.println("Remove 'i': " + set.remove('i'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove key with two children:");
System.out.println("Remove 's': " + set.remove('s'));
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
System.out.println("Remove root key:");
System.out.println("Remove 'd': " + set.remove('d'));
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('t');
set.remove('e');
set.remove('r');
System.out.println("Removing the LAST AND FINAL KEY:");
set.remove('k');
System.out.println("Tree count: " + set.getCount() + "; height: " +
set.getHeight());
System.out.println("Tree contains: ");
set.printAll();
System.out.println();
}
}
output
Empty tree count: 0; height: 0
Empty tree contains:
Add "doesitwork" to the set:
Add 'd’: true
Add 'o': true
Add 'e': true
Add 's': true
Add 'i': true
Add 't': true
Add 'w': true
Add 'o': false
Add 'r': true
Add 'k': true
Tree count: 9; height: 4
Tree contains:
d e i k o r s t w
Tree structure:
|---d
|---o
|---e
|---i
|---k
|---s
|---r
|---t
|---w
Test the contains method:
Contains 'd? true
Contains 't'? true
Contains 'k'? true
Contains 'x'? false
Contains '@'? false
Contains '5'? false
Tree count: 9; height: 4
Tree contains:
d e i k o r s t w
Test the remove method.
Remove key with no children:
Remove 'w': true
Tree contains:
d e i k o r s t
Remove key with one (left) child:
Remove 'o': true
Tree contains:
d e i k r s t
Remove key with one (right) child:
Remove 'i': true
Tree contains:
d e k r s t
Remove key with two children:
Remove 's': true
Tree contains:
d e k r t
Remove root key:
Remove 'd': true
Tree contains:
e k r t
Tree count: 4; height: 2
|---k
|---e
|---r
|---t
Remove all remaining keys
Removing the LAST AND FINAL KEY:
Tree count: 0; height: 0
Tree contains:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.