Assignment 4

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Attach the source code to your email. Send me only the source code (.java files); do not include the .class or any other files. Do not zip or otherwise bundle the .java files.

Requirements

As stated on the assignment handout, you must:

• Create a binary tree data structure.
• Write a method or constructor that builds a tree based on the contents of some set. (This tree has certain features--contents of the original set are in the leaves of the tree, each internal node contains the sum of its two child nodes, etc.)
• Write a display method that prints out the contents of the tree (as described, so that you can discern the tree structure).
• Write a find method that, given a search string, returns the value in the corresponding leaf node.

Suggestions

Assignment 4 talks about revising Assignment 3, but they really are not very related, except conceptually. To avoid confusion, I'd start from scratch. Just write the following two classes.

TreeNode

In order to build a tree, you'll need some nodes. Have a look at the Node class on p. 408 - 410 of the book for ideas. Ideally, you should practice writing generic and reusable code like this. However, for this assignment, your nodes only need to hold ints or Integers.

Later, we're going to need a way to compare nodes, so they should implement the Comparable interface.

Here's a skeleton of the essential features of this class:

public class TreeNode implements Comparable<TreeNode> {
  //instance members  (could be public or protected, if you're lazy)
  private Integer data;
  private TreeNode left;
  private TreeNode right;

  //constructors
  public TreeNode(Integer data);
  public TreeNode(Integer data, TreeNode left, TreeNode right);

  //methods
  //if above variables are private, include a get and set for each.
  public boolean isLeaf();   //handy, but not required
  public int compareTo(TreeNode node);  //see java.lang.Comparable in API

  //a toString() and equals() method is good practice, but not used here
}

BinaryTree

For the binary tree, you don't need to follow what the book is doing. The only instance variable you need is a pointer to the root of the tree. Then I recommend the following methods:

A Constructor. This should take a set of numbers as its only parameter. This could be an array of ints, or a java.util.Collection of Integers, or something else. This should then build the tree so that the leaves contain the contents of this set. (This part is most similar to Assignment 3).

I'd recommend you use a java.util.PriorityQueue. Take each element of the set, wrap it in a node with no children, and add it to the queue. Then, while the queue has more than one element, take out the two smallest nodes. Add their contents together, and use this as the contents of a third "sum" or "root" node. Set this third node's children to be the two smallest nodes. Now add the third node back into the queue.

When you're done looping, only one node will remain in the PriorityQueue, but it will be contain all the other nodes as children. Remove this last node from the queue, and set this.root to point to it.

(In order to use this technique, your nodes must implement Comparable. I'll talk about this in lab.)

display. This public method doesn't need to take any parameters. However, you will probably need a private, recursive helper method that takes a node and prints its left subtree, its contents, and its right subtree. (You do not need to designate internal nodes that have the same value as a leaf with a ' character, as in the assignment example. This note is just clarifying how the parentheses format shows the structure of the tree.)

find. There is a typo on the assignment. It should read "the code for the leaves {5, 2, 3, 1, 4} are {"RR", "LRR", "LL", "LRL", "RL"}, respectively."

So this method will take a string of Ls and Rs that give directions through the tree to particular leaf node. (It is an error if the given string contains other letters, or if it does not end at a leaf node.) It will then return the value in this leaf node (or throw an exception if there was an error).

You do not need to add special labeling to your nodes, as you already know whether a subtree is on the left or the right--you call either getLeft() or getRight(). So (error checking aside), you need only loop through the search string. Start a "current" node pointer at the root of the tree. If the next character in the string is 'L', move current to point to current.getLeft(); if the next character in the string is a 'R', move current to point to current.getRight() When you get to the leaf node, return the contents of that node (current).

main. Finally, you'll need a main method to test the others. Build a tree, display it, and try a few different search strings on it. (Remember to test error conditions too.)

So, one possible code skeleton for BinaryTree would be:

public class BinaryTree {

  //the only instance variable
  private TreeNode root;

  //constructor
  public BinaryTree(int[] set) {
    /*
      --load a PriorityQueue<TreeNode> with one node
        for each element of set
        (that is, each node contains an element of set)
      --then go through the queue, creating internal nodes
         and putting them back in the queue
      --when the queue has only one node left:
        this.root = queue.poll();
    */
  }

  //methods

  public void display() {
    System.out.println(this.display(this.root));
  }

  private String display(TreeNode node) {
    //(including proper formatting) build a string that contains:
    //node's left subtree
    //node's contents
    //node's right subtree
  }


  public int find(String searchCode) throws IllegalArgumentException {
    //start at this.root and follow the directions in searchCode
    //return the contents of the designated leaf node
  }


  public static void main(String[] args) {
    //test the other methods here.  For example:
    int[] testSet = {5, 2, 3, 1, 4};
    BinaryTree tree = new BinaryTree(testSet);
    //display the tree
    //try some different find strings
      //try some legitimate directions.  But also test:
      //--a search string that has other letters in it
      //--a search string that's too long (passes a leaf node)
      //--a search string that's too short (doesn't reach a leaf)
    //you may also want to try testing a tree with a different input set
  }

}

In Assignment 5, we'll add another method to this BinaryTree class.

Grading:

Out of 100 points:

10 - Compiles

30 - Constructor (or other method) that builds a binary tree.

• Takes only one parameter (the set to base the tree on) (10 points)
• The leaf nodes contain all the elements of the original set (10 points)
• Each inner (non-leaf) node contains the sum of its two children (10 points)

30 - Display

• Shows all the elements in the tree (only once each) (10 points)
• Gives an in-order traversal print-out of the tree (10 points)
• Follows the specified format: "(left-tree data right-tree)", where left-tree and right-tree are expanded into their components, and leaf nodes are in [brackets]. (10 points)

25 - Find

• Returns the data in a leaf node when given a correct search string (10 points)
• Throws an exception when the search string contains invalid characters (5 points)
• Throws an exception when the search string is too short (ends on an inner node) (5 points)
• Throws an exception when the search string is too long (passes a leaf node) (5 points)

5 - Main

You have some sort of tests of these methods in the main method of your primary (BinaryTree) class.