CS230 Lab 11

Lab 11

Trees, Trees, Trees

Task 0: Tree Traversals


Let's make a LinkedBinaryTree. Note that the <code>LinkedBinaryTree` class has 3 different constructors:

  • the no-argument constructor
  • the one-argument (the root element) constructor
  • the three-argument constructor (root, left, right) constructor

 public static void main (String [] args) {
     LinkedBinaryTree<String> t0,t1,t2,t3;
     t0 = new LinkedBinaryTree<String>(); // empty tree
     t1 = new LinkedBinaryTree<String>("john");
     t2 = new LinkedBinaryTree<String>("paul", t0 ,new LinkedBinaryTree<String>("george"));
     t3 = new LinkedBinaryTree<String>("ringo", t1, t0);
     LinkedBinaryTree<String> beatles = new LinkedBinaryTree<String>("elvis",t2,t3);

  1. Draw the beatles tree:

  2. If we visited the nodes of the beatles tree in pre-order, write the nodes as they are visited:

  3. If we visited the nodes of the beatles tree in post-order, write the nodes as they are visited:
  4. If we visited the nodes of the beatles tree in in-order, write the nodes as they are visited:




Set up

From the cs server, download the lab11 folder to your desktop.

Inside this folder, there is a javafoundations subfolder. Within it you will find LinkedBinaryTree.java and BTNode.java. Study the LinkedBinaryTree.java file, which is an implementation of the BinaryTree Interface, and the BTNode.java file. We need these files for our lab work this week.

Task 1: Complete LinkedBinaryTree.java and BTNode.java

Open the files you just downloaded, and fill in the definitions of the methods at the end of the files. In particular, in BTNode.java, write definitions for:

  • public void preorder(ArrayIterator iter);
  • public void postorder(ArrayIterator iter);

In LinkedBinaryTree.java, write definitions for:

  • public String toString();
  • public LinkedBinaryTree getRight();
  • public boolean contains(T target);
  • public boolean isEmpty();
  • public Iterator preorder();
  • public Iterator postorder();

A few hints about toString:

  1. You'll need to create an Iterator to create a String representation of the contents of your tree.
  2. You can choose the path of traversal (right now, we'll use inorder because that is already written. Later, you can use pre- or post- order as well).
  3. Iterators have hasNext() and next(), which come in handy
  4. Invoking System.out.println(beatles) produces this:

Task 2: Create some Trees

Think carefully about constructing some trees that you will use for testing your methods. Be creative!

Make sure to also create the tree used in "Guess My Animal", below. Use it for testing purposes here, in this task.

Task 3: Guess My Animal

Trees are a natural fit to arrange information that is related by simple Yes or No responses. Your task is to write (from scratch) a simple AnimalExpert that asks the user a set of questions, and based on the answers to those questions, reveals an animal at the end. Answering the Yes/No questions effectively guides the user's path from the root of the tree to the node containing the answer (ok, so this is not a complete animal tree). Here is a sample transcript:

I will try to guess the animal you are thinking of...
Is the animal big?
Does it live in a cage?
Does it chirp?
It's a hamster!

Would you like a hint or two?