Setup
Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.
Goals and Outcomes
By the end of this lab, you will…
- have more experience working with trees and recursion
- understand the concept of serialization
- have implemented a basic tree exploration algorithm
- have implemented the backend of a simple AI for a N-Questions game
Tree Terminology
- A leaf is a node that doesn’t have any children. An internal node is any node in a binary tree that is not a leaf. In the following example, leaf nodes are circled in purple on the left and internal nodes are circled in purple on the right.
- In a full binary tree (not the same as complete trees), all nodes have either zero or two children. For example, both of these are full binary trees:
- Neither of these binary trees are full, because the highlighted nodes only have one child each:
FullStringTree
In this lab, we will finish a FullStringTree class which represents a full tree with String data.
In order to work effectively with data structures, it is convenient to be able to load and save the data itself. The process of storing the data (for example, in a file) so that we can re-construct the data structure later is called serialization. The actual reconstruction is called deserialization.
To serialize a data structure, we need to define a file format which both methods conform to. To define a file format, we need to define an order to save/load the nodes in. There are many ways to explore (also called traverse) the nodes of a tree, but we’ll work with one called pre-order:
Pre-Order Traversal
- Visit the root
- Until there are no nodes unvisited:
- Repeatedly visit the left node until you reach a leaf
- Return to the previous level and visit the right node
Serialization
Consider the following example:
Following the blue arrows, we see that the nodes are explored in the order: 17, 41, 3, 4, 8, 66, 32. The corresponding file would look like:
I: 17
I: 41
L: 3
L: 4
I: 8
L: 66
L: 32
That is, we have one line per element in the tree, where each line is prefixed with either “I: ” (if it’s an internal node) or “L: ” (if it’s a leaf node).
We’ll start with implementing the deserialization algorithm; to put it another way, we’ll write the constructor of the class first. (Think about why these are the same problem!)
We’ve phrased the algorithm iteratively (with loops); however, since trees are naturally recursive structures, it’s significantly cleaner recursively. Almost everything we will implement today must be recursive to get credit.
public FullStringTree(Scanner in)
Sets this tree to the one represented by the contents of in where in is a Scanner that passes in a serializated FullStringTree.
You must implement this constructor recursively using a public/private pair like we did in lecture.
Task 0.
Implement the FullStringTree constructor recursively in FullStringTree.java. Implement and use deserialize() as the private recursive helper method!
You will find both of these methods very helpful when writing the recursive method.
Calling .next() on a Scanner object will by default provide the portion of the String until the next whitespace. The cursor will then be moved to the spot after the next whitespace.
Calling .nextLine() on a Scanner object will by default provide the portion of the String until the next newline character. The cursor will then be moved to the next line.
You will find Slides 40-45 of the BST Lecture very helpful!
public List<String> explore()
Returns a new List containing the data this tree contains.
- You must implement this method recursively.
- The List must be ordered as described above.
- If a piece of data is stored in an internal node, it should be prefixed by “I: ”.
- If a piece of data is stored in a leaf node, it should be prefixed by “L: ”
Task 1. Implement the FullStringTree explore method recursively in FullStringTree.java
public void serialize(PrintStream output)
Serializes a FullStringTree and writes through the PrintStream output.
This method calls the explore method you wrote previously and then outputs the serialized tree through the PrintStream.
Task 2. Implement serialization by writing the serialize method in FullStringTree.
The serialized FullStringTree must output using the PrintStream passed in as an argument to the serialize method. Make sure you call the println method on the PrintStream instance passed in and not using System.out.println().
N-Questions
N-Questions is a guessing game in which the objective is to ask yes/no questions to determine an object. In our version, the human begins a round by choosing some object, and the computer attempts to guess that object by asking a series of yes/no questions until it thinks it knows the answer. Then, the computer makes a guess; if its guess is correct, the computer wins, and otherwise you win.
Internally, the computer will use a binary tree (often called a decision tree) to keep track of the questions and answers. Questions and answers will both be represented as strings, and the resulting tree will always be full. This (convieniently…) matches up with the FullStringTree that we’ve written previously.
To finish off the N-Questions game, we will need to write a play method which is called by the client to run a single instance of the N-Questions game. We’ve written the boring part of this for you in a method called makeFinalGuess in the QuestionTree class which is a subclass of FullStringTree.
public void play()
Calls the play function on the base case.
Runs N-questions using a FullStringTree. At each stage, if the answer to the question at the node is yes, move left, otherwise move right.
Task 3. Implement the play method recursively. Make sure you follow the public/private pattern we’ve used for recursion and call the helper methods we provided in order to get user input and to make the final guess. Try the game!