Lab: 20 Questions

Beware! The seed of TreeMonster.java has sprouted!

Background: The Code

Download treelab.zip.  Inside you'll find:


Exercise 0:  randomTree and TreeDisplay

In TreeLab.java, the randomTree method has been provided to help you test your code. Go ahead and run the following code. For example, the following code constructs a random binary tree consisting of 10 nodes. Each node contains a random integer from 1 to 3.

TreeNode<Integer> myTree = TreeLab.randomTree(10, 3);

The TreeDisplay<E> class has been provided to help you view the contents of a tree. For example, the following code pops up an empty window that can be used for showing the contents of a binary tree of Integer values.

TreeDisplay<Integer> display = new TreeDisplay<Integer>();

To view the contents of the tree we created earlier in this window, run the following code.

display.showTree(myTree);


Go ahead and do the following:

1.  Test that you can view a randomly generated tree using the randomTree method and TreeDisplay class.

2.  After displaying a tree, assign another randomly tree to the same tree variable. Does the tree in the window change?

myTree = TreeLab.randomTree(10, 3);

3.    Call the showTree method again to tell the display to show the tree you just generated. Does the tree in the window change?


Exercise 1:  replace

In TreeLab.java, complete the replace method, which should replace all occurrences of oldVal with newVal in the given tree, and return the number of values that were replaced. This method should work for various data types, including strings, so be sure to use the proper test for equality. Do not create any new nodes.

For example, the lefthand picture below contains seven 1s. Replacing the value 1 in this tree with the value 4 will return 7 and will modify the tree to appear as shown in the righthand picture.

          

Exercise 2:  countNodesAtDepth

Complete the countNodesAtDepth method, which should return the number of nodes at the given depth in the given tree. The root node has a depth of 0. In the following tree, there are 2 nodes at depth 1 (2 and 4), 3 nodes at depth 2 (10, 3, and 10), 1 node at depth 4 (8), and 0 nodes at depth 6.

Exercise 3:  onlyHas

Complete the onlyHas method, which returns true if and only if every value in the tree matches the given value. This method should work for various data types, including strings, so be sure to use the proper test for equality. For example, onlyHas(t, 1) should return true for the tree below, since every node contains the value 1.

          

Likewise, onlyHas(t, 4) should return false for the tree below, since some nodes do not contain the value 4.

You may choose what onlyHas should do if given an empty tree.


Exercise 4:  build

Complete the build method, which takes in a number of levels and a value, and returns a complete binary tree with that many levels. For example, build(4, "CS") returns the following binary tree. Assume that the number of levels is non-negative.

Exercise 5:  save

Java's PrintWriter class can be used to print strings to a text file, one line at a time. For example,

PrintWriter out = new PrintWriter(new FileWriter("somefile.txt"));
out.println("some");
out.println("text");
out.close();

Complete the save method, which takes in a PrintWriter and a tree. Use the PrintWriter's println method to print the contents of the tree. Each node's value is printed before its left children, which are printed before that node's right children. The format is illustrated by the following examples. Notice that a dollar sign ($) is printed whenever a null value is reached.

The saveToFile method has been provided to help you test your save method. The saveToFile method takes in a  tree and a file name (such as "somefile.txt"). It creates a PrintWriter and passes it to the save method you wrote. Be sure to look inside the text files you save to, so you can be sure your code works.


Exercise 6:  load

Java's Scanner class can be used to read strings from a text file, one line at a time. For example,

Scanner in = new Scanner(new File("somefile.txt"));
String firstLine = in.nextLine();
String secondLine = in.nextLine();
in.close();

Complete the load method, which takes in a Scanner. Use the Scanner's nextLine method to read from a text file. The text in that file represents a tree, stored in the same format we used for the save method. The load method returns the tree described in the file. For example, suppose the following text is coming up in the Scanner (i.e. the first string returned by nextLine will be "1", the next string returned by nextLine will be "$", etc).

1
$
2
$
$

In this case, the load method should return a tree whose root value is 1, whose left is null, and whose right is a leaf with the value 2. You should assume there are always at least enough lines in the file to build and return a tree.

Hint: Write nextLine exactly once in your method.

The loadFromFile method has been provided to help you test your load method. The loadFromFile method takes in the file name to read from. It creates a Scanner and passes it to the load method you wrote.


Exercise 7:  twentyQuestions

In this exercise, you'll be programming the computer to play a game of 20 Questions. The user will think of a person or thing, and then they will call the twentyQuestions method, which will direct the computer to attempt to guess what the user is thinking of by asking a series of yes/no questions. (Traditionally, the computer would be limited to 20 questions, but we will ignore that limit for this exercise.) In order for the computer to ask semi-intelligent questions, it must have some knowledge of the world. In this exercise, that knowledge will take the form of a decision tree.

Our decision tree will contain one or more strings, and every node will have zero or two children. The strings in the leaves are the people and things that the computer knows about. The strings in the other nodes are descriptions the computer can use to identify which person or thing you are thinking of. All of the people/things in the left subtree of a question correspond to an answer of yes, while the people/things in the right subtree correspond to an answer of no. Consider the following decision tree:

This tree has 3 people/things: Margaret, Dave, and a fish. And it has 2 descriptions: human and tall. All of the humans appear to the left of "human", and all of the non-humans appear to the right. Likewise, all of the tall humans appear to the left of both "human" and "tall".

The following transcript shows the result of a call to twentyQuestions using the decision tree shown above. The bold text was printed to the console by the twentyQuestions method, and the italicized answers were typed into the console by the user.

Is it human? yes
Is it tall? no
Is it Dave? yes
I win!

On the other hand, if the computer's final guess is incorrect, the computer will ask for the correct answer and a characteristic to distinguish that correct answer from the computer's incorrect answer, and will modify the decision tree to reflect this new knowledge. This is illustrated in the transcript below for a different call to twentyQuestions, using the same decision tree:

Is it human? no
Is it a fish? no
I give up. Who/what is it?  It is a piano
What distinguishes a piano from a fish?
a piano is something you can tune

After this call to twentyQuestions, the decision tree will now appear as follows:

Go ahead and complete the twentyQuestions method. The printed text must be formatted exactly as shown in the sample transcripts above. When new knowledge must be added to the tree, your code should create only two new nodes.

Your code cannot change which node is considered to be the root of the decision tree, but you can change the value in that node. Your code must work even if there is only one node in the tree.

The static variable userInput has been initialized to refer to a Scanner for reading user input from the console. The following line of code will allow the user to enter a line of text and store the result in s:

String s = userInput.nextLine();

The testTwentyQuestions method has been provided to help you test your twentyQuestions method. By default, the testTwentyQuestions method uses the knowledge.txt file provided, but you are welcome to change this.

When your code works, keep playing it again and again, because it's just so much fun!!!


Additional Credit

Here are some methods you may complete for additional credit. To earn credit, you must also write code to test any methods you write (with a comprehensive set of test cases).


public static <E> void reflect(TreeNode<E> t)

Modifies the given tree so that it is reflected horizontally (without creating any new nodes). For example, reflect would modify the lefthand tree below to look like the righthand tree.

          

public static <E> List<E> leafList(TreeNode<E> t)

Returns a list of all values in the leaves of the given tree. Your code must run in linear time. For the following tree, leafList returns the list [9, 3, 7], in that order.

public static <E> TreeNode<E> condense(TreeNode<E> t)

Removes all nodes that have exactly one child. This method modifies the given tree and returns the resulting tree. For example, if the lefthand tree below is passed to condense, then the modified tree returned should match the righthand tree below.

          

public static Integer evaluate(TreeNode<String> expression)

Returns the value of the mathematical expression represented by the given tree. For example, given the following tree, evaluate will return 14.

public static TreeNode<String> parse(String s)

Given a string describing a mathematical expression (e.g. "2+3*4"), returns a tree representing that expression, like the one shown above.