CS 261 Lab I - Binary Tree Properties

Due Wed Apr 03 at 9:00am

Overview

In this lab you will practice working with Binary Trees in order to solidify your understanding of this data structure. You will be working with a node-based version of a BinaryTree that we discussed in class, but you will be extending this class to add new functionality that describes the structure of the tree.

This lab will be completed in pairs. Review the pair programming guidelines!

Objectives

To practice with binary trees
To practice using recursion (you could use iteration, but I doubt you'd want to!)

Necessary Files

You will need to download the copy of the BinaryTreeLab.zip file. This file contains a version of the BinaryTree class similar to the one we discussed in class. You will need to import this class into Eclipse.

Details

This lab is pretty straight-forward, but you should still be sure to read the whole assignment carefully!
You will be creating a new class AnalyzableBinaryTree (yes it is a long name, but it describes what you're doing!) that extends the existing BinaryTree class. Remember to make your new class generic!
- Note that you will want to create new constructors for your AnalyzableBinaryTree. These constructors can just call their parent's version of the constructor using super().
Your new BinaryTree should include the following new methods (these are listed in suggested order of completion):
1. AnalyzableBinaryTree<E> attachLeft(E data)
  The first thing you'll want to do is create a way to add data to a tree. This method should attempt to add a new Node with the given data to the the left branch of the tree. If the left branch of the tree is already occupied, your method should throw an IllegalStateException. You should then return a new AnalyzableBinaryTree that represents the subtree rooted by the Node you just added!
  - Note that returning the new tree will make it easy to chain together attachment calls. Thus code such as tree.attachLeft(2).attachLeft(6).attachLeft(1) will create a tree with the nodes 2 - 6 - 1 going down the left side.
2. AnalyzableBinaryTree<E> attachRight(E data)
  This method will work exactly the same as the previous, except that you will be attaching the new data to the right branch, rather than the left. Again, if throw an IllegalStateException if the right branch is already occupied!
3. int size()
  This method should computer and return the number of Nodes in the tree. Use recursion!
  - HINT: You will likely get good mileage out of a helper method that counts the number of children a node has!
4. int getHeight()
  This method should compute and return the height of the tree (the distance from the root to the furthest away leaf). This method is a lot like calculating the size.
5. boolean isFull()
  This method should return whether or not the tree is full (that is, whether or not ever node is either a leaf or has exactly two children; see pg302 of the text for an example). Again, recursion should make this pretty straight forward.
6. boolean isPerfect()
  This method should return whether or not the tree is perfect. A perfect tree is a full tree of height n that has exactly 2ⁿ-1 children (again, see page 302 of the text for an example). This is a tre where everyone not on the bottom level has two children, and every node on the bottom level is a leaf. If you use the "count" definition and your previous methods, this method should be easy to write.
7. boolean isComplete()
  This method should return whether or not the tree is complete. A complete tree is one in which all levels except the last are completely filled (i.e., perfect), and any nodes missing are to the right of their cousins (once again, see page 302 of the text).
  - This method is one of the more complex to write. You can solve it recursively, but you might also consider doing a breadth-first traversal. You can do this using a Queue (yes! The old data structures return!). Start by enqueuing the root. Then you can count nodes by dequeue one node, counting it, and enqueuing its children (left then right). Stop as soon as you dequeue a null node--this means you should have finished counting every node in the tree (because there is no one to the right of you!). If you have (and you can compare to the size of the tree), then you have a complete tree.
    - There are built-in Java classes for implementing a Queue (e.g., see the java.util.Deque interface. But you can also just use an ArrayList and enqueue using add() (which adds to the tail) and dequeue using remove(0) (which removes from the head).
8. boolean isBinarySearchTree()
  Finally, write a method that returns whether or not this tree is organized as a Binary Search Tree. Remember that in a binary search tree, each non-null left child is less than the parent, and each non-null right node is greater than the parent (these are strict inequalities, since we can't have duplicate nodes!).
  - This method can be written recursively: check that your children's roots are okay, and then recurse to make sure that your children are also BSTs!
  - This method only makes sense if the class of the tree's data implements the Comparable interface (and so can be ordered). Use the instanceof operator to test that this is the case, and if not throw a ClassCastException.
Remember that your methods should have the above signatures: use them as launchers with recursive helper methods if needed!
If you get stuck, be sure to ask for help!

Submitting

Submit all of your classes to the LabI submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

Remember to fill out your lab partner evaluation!

Extensions

There are plenty of extra analytical functionality you might add. Informative methods can be worth up to 5 extra credit points. Some examples:

An isDegenerate() method that reports whether or not each node has either 0 or 1 children (and thus the tree is really just a linked list).
An isBalanced() method that reports whether or not the height of the two subtrees of any node differens by at most 1 level.
As a bonus, try overriding the .equals() method so that it returns whether or not two trees have the same data in the same structure. Again, this method only makes sense if the node's data type is Compareable, so be sure to check that!

Grading

This assignment will be graded based on approximately the following criteria:

You have created extended the BinaryTree class with new constructors [5%]
Working attachLeft() and attachRight() methods [10%]
Working size() method [10%]
Working getHeight() method [10%]
Working isFull() method [10%]
Working isPerfect() method [10%]
Working isComplete() method, using a Queue [15%]
Working isBinarySeachTree() method [15%]
Your code is well documented and follows the edicts of good style [10%]
You completed your lab partner evaluation [5%]