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 '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'));

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'));

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'));

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'));

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');

System.out.println("Removing the LAST AND FINAL KEY:");

set.remove('t');

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.

THEN:

make a new file called HangmanGame.java. You will program a hangman-style game for two players (see the Wikipedia article Hangman (game) for an overview).

Declare a main method. Declare two TreeSet variables: one for the letters the player guessed correctly, and one for letters the player missed with.

Ask player 1 to input a secret word without spaces. (Optional: after solving the entire milestone, figure out a way to support multi-word phrases.) Print a large number of blank lines to scroll the secret word off the screen.

Enter a loop:

Ask player 2 to guess a letter

NOTE: the Scanner class does not have a method for nextChar(). Use .next() to read a String, and then pull out the first letter.

If the secret word contains the guess letter, add the guess to the correct set. Otherwise add it to the missed set.

Print the state of the game:

Print one part of the body for each missed letter, in this order:

head, torso, left arm, right arm, left leg, right leg.

Print the secret word, only revealing letters that have been guessed

correctly. Use underscores (_) for unknown letters.

Print the set of misses using the printAll method of TreeSet.

Repeat until the user has made 6 wrong guesses (we will play 6 misses == loss), OR the user has guessed every letter in the secret word correctly.

4. If 6 wrong guesses were made, tell the player they lost. Otherwise they won!

Structure should be like:

Remember that at all times, you have TreeSets containing all correct and all wrong guesses. These sets can tell you their count and can check for containment very quickly.

Write a method printBody that takes an integer for the number of wrong guesses and prints out the appropriate number of body parts.

Write a method printSecretWord that takes a String (the secret word) and a set of correct guesses, and prints out the word according to 3.(c).ii above.

(For each letter in the secret word, if that letter is contained in the set, print it out; otherwise print an underscore.)

Write a method printMisses that takes a set of missed guesses, and prints them in a formatted way. (This should only be 2-3 lines.)

Write a boolean method isWinner that takes the secret word and the set of correct guesses and returns true if the set contains every letter of the secret word. Note that this is similar to the logic for printSecretWord; for a bonus challenge, figure out a way to combine the two methods into one, so the method prints the word and returns true if the game has been won.

There are other challenges for you to solve on your own. Be creative and think about the most reasonable course of action. How will you handle lowercase vs. uppercase letters? What will you do if the player guesses a letter he/she already guessed? What if they guess a non-letter character like "@" ?