CS 261 Lab I - Binary Tree Properties

Due Wed Apr 02 at 9:00am

Overview

In this lab you will practice writing methods for Binary Trees in order to explore a few additional concepts for this data structure. You will be working with the 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. Partner assignments for this lab can be found on Moodle

Remember to review the pair programming guidelines

Objectives

To learn about further "properties" of tree data structures
To practice implementing methods for with binary trees

Necessary Files

You will need to download the copy of the BinaryTreeLab.zip file. This file contains a copy of the BinaryTree<E> class that we implemented in class (possibly with a few tweaks). You will need to import this class into Eclipse.

Assignment 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!
- You will need to create new constuctors for your AnalyzableBinaryTree. You should include equivalent versions of each of the constructors in the parent class (there are 4). These constructors can just call their parent's version of the constructor using super().
- Remember that as a subclass, you have inherited all of your parent's instance variables (and inner classes)--you do not need to make your own copies of them!
Your AnalyzableBinaryTree will include the following new methods (these are listed in suggested order of completion):
1. public AnalyzableBinaryTree<E> attachLeft(E data)
  This method attaches the given data to the left of the tree's root. It then returns a new AnalyzableBinaryTree representing the subtree that was created by this attachment (e.g., the subtree that is now to the left of the root). If the root's left branch is already occupied, this method show throw an IllegalStateException (be sure and pass the Exception a message about what went wrong!).
  - Note that the BinaryTree class contains a protected constructor that creates a new BinaryTree out of a given node. You can use your extended version of this method to create the tree to return. See the getLeftSubtree() method as an example.
  - This method (and the one below) is intended to help you construct Binary Trees for testing by letting you easily add a new Node to the root of the tree. Rather than needing to call the constructor with nested subtrees, you can just attach nodes to the root--and then get the subtree that you created through that attachment to attach another node to! For example:
    AnalyzableBinaryTree<Integer> tree = new AnalyzableBinaryTree<Integer>(4); AnalyzableBinaryTree<Integer> left = tree.attachLeft(3); AnalyzableBinaryTree<Integer> right = tree.attachRight(2); AnalyzableBinaryTree<Integer> leftLeft = left.attachRight(1); ....
    This creates a tree with 4 at the root, 3 and 2 as children, and 1 as a child of 3. Alternatively, because each method returns a new tree, it is also possible to chain together attachment cals:
    AnalyzableBinaryTree<Integer> tree = new AnalyzableBinaryTree<Integer>(2); tree.attachLeft(6).attachLeft(1)
    which creates a tree with the nodes 2 - 6 - 1 going down the left side.
  - Using these methods are not required for your testing (below), but might be useful!
2. public 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. public int size()
  This method should compute and return the number of Nodes in the tree. Use recursion!
4. public int getHeight()
  This method should compute and return the height of the tree (the length of the path from the root to the furthest away leaf)--the height of a tree with just a root node is 1. This method is a lot like calculating the size. Think about the "base case" of your recursion, and how you can build off of that.
  - Remember to determine whether the left subtree or right subtree is taller!
5. boolean isFull()
  This method should return whether or not the tree is full (that is, whether or not every node is either a leaf or has exactly two children: See page 302 of the text for details. Again, recursion should make this pretty straight forward.
  - HINT: You might get good mileage out of a helper method that counts the number of children a node has, so you can determine if a node has 0, 1 or 2 kids.
6. boolean isPerfect()
  This method should return whether or not the tree is perfect. A perfect tree is a full tree in which all of the leaves are on the bottom level (and thus every node not on the bottom level has 2 children). This means that a perfect tree of height h has exactly 2^h-1 nodes. If you use this fact 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 siblings/cousins:
  - This method is a little more complex to write. You can solve it recursively, but you might also consider doing a breadth-first traversal (using a queue). Start by enqueuing the root. Then you can count nodes by dequeuing 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 now no one to the right of you!). If you have counted every node (determined by the size of the tree), then you have a complete tree.
    - You can use the Queue class that we implemented in lecture, or you can just use a LinkedList, with the addLast() method acting as push and the removeFirst() method acting as pop.
Remember that your methods should have the above signatures: use them as launchers with private recursive helper methods!
If you get stuck, be sure to ask for help!

Testing your Class

You should create and submit a Tester that demonstrates that your methods work. This is a good plan anyway, but it'll help us to see what you've done.

Remember to test more than one tree! You can construct these trees using the nested constructors like we used in class, or by using your attachLeft() and attachRight() methods---or both!
A good note for testing boolean "isSomething" methods: be sure and test it with an input that you expect to return true AND an input that you expect to return false. So test "isFull" with both a full BinaryTree and a not-full BinaryTree.
Test with trees with a height greater than 2 or 3--this will make sure there are no "one time recursing works" flukes. Remember: the goal is to try and break your own code!
Be sure and test edge cases as well: what happens when you call these methods on an empty tree? A tree with a single node? A degenerate tree? A tree with a lot (> 10) nodes?

Extensions

There are plenty of extra analytical functionality you might add. Informative methods can be worth up to 3 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 true when two trees have equal data in the same structure.

Submitting

Make sure your names are in a class comment at the top of both your AnalyzableBinaryTree and your Tester, and upload them to the LabI submission folder on vhedwig. 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.

After you have submitted your solution, log onto Moodle and submit the Lab I Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded out of 21 points:

[2pt] You have extended the BinaryTree class with appropriate constructors and instance variables
[3pt] Working attachLeft() and attachRight() methods (which throw appropriate exceptions)
[2pt] Working size() method
[2pt] Working getHeight() method
[2pt] Working isFull() method
[3pt] Working isPerfect() method
[3pt] Working isComplete() method
[3pt] A Tester that demonstrates the functionality of all your methods
[1pt] You have completed your lab partner evaluation