Lab: Decision Trees

Solutions

• AnimalExpert.java

Set up

Download the lab12 folder to your desktop. Compile your files, examine the contents of the TreeDriver class and run it to see what it produces.

Take a minute to arrange the classes within the javafoundations, on the project window of BlueJ in a meaningful way, to help you identify the relationships among those classes.

Task 0: The BinaryTree Interface

Study the BinaryTree Interface given in the downloaded javafoundations.

Today we will use the LinkedBinaryTree implementation of this Interface. Here are the available constructors for a LinkedBinaryTree object:

1. public LinkedBinaryTree () //creates an empty Binary Tree
2. public LinkedBinaryTree (T element) // creates a Binary Tree of only one element at its root
3. public LinkedBinaryTree (T element, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) //Creates a binary tree with the specified element at its root and two subtrees.

Task 1: Create some BinaryTrees

Edit the provided Driver program, named TreeDriver, to construct a few LinkedBinaryTree instances using the constructor(s) and methods available in the BinaryTree Interface. Three sample trees are provided here. A couple of trees with only one element each, and a third tree which build on top of the first two. Observe how a tree is build from the leaves up!

Think carefully how to go about constructing trees with more elements! Think about the way to build a tree of half a dozen elements, and even more. We recommend that you first draw your trees on a piece of paper, and then you write the lines of code to construct them. At the end, make sure that you print the trees you constructed, and verify that the constructed trees match the ones you drew.

Task 2: Guess My Animal

Task2A: Construct the Decision Tree

Now look at the Animal Tree below, and make a plan on how to construct it. On your notebook sketch the code for that.

Decision trees are a natural fit to arrange information that is related by simple YES or NO responses. Your task is to write a simple "expert system". AnimalExpert asks the user a set of questions. Based on a already-built Animal Tree, and guided by the user's answers to those questions, the expert reveals an animal at the end.

In terms of code, answering the Yes/No questions effectively guides the user's path from the root of the tree to the leaf node containing the answer (ok, so this is not an animal expert system that knows all the animals, but nobody is perfect ;).

Add a class, named AnimalExpert, to the lab12Project. In there create the BinaryTree as shown in the screenshot above.

Task2B: Query the Decision Tree

Add a method, guessMyAnimal(), to traverse the tree, based on the user's answers, until an Animal has been revealed.

Here is a sample transcript:

Task2C: Play the "Guess My Animal" Game

Arrange so that the question and answer process form the task above can be repeated more times, according to the user's wish.

Here is a screenshot of the behavior of my program:

Good job!