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.