COMP 139 - Lab 6 - Trees and Recursion

Learning Outcomes and Introduction

In this lab assignment you will create your own binary search tree class. In the process you will practice what you've learned about:

• binary search trees
• recursion
• balanced and unbalanced trees
• non-linear collections
• linked data structures
• generics

Make sure you test your code as you progress through the assignment. There is no "main program" required for this lab, so effective testing will be essential to ensure that your code is correct.

Task 1: Tree Node

Create an implementation of the examples.TreeNode interface.

The second type parameter to this interface is somewhat unusual. It is set up this way to allow you to restrict the types of nodes that your implementation can link to. Most likely, you only want your node class to link to other nodes of the same class! You can enforce this by implementing the interface like this:

			class MyNode<E> implements TreeNode<E, MyNode<E>> { }
		

As an extra side-effect, the getLeft(), getRight(), and getParent() methods will return your class instead of the interface. This will make working with your nodes in Task 3 a little simpler, since you'll have direct access to any extra properties you add even when using these getters.

Task 2: Unbalanced Tree

Create an unbalanced binary search tree class that is an implementation of the examples.BinaryTree interface.

The type parameter for this interface looks a little daunting, but it's just making sure that any content you add to the tree can be sorted. A non-generic implementation of this interface that held Strings would look like:

			class MyTree extends BinaryTree<String> { }
		

A generic implementation of this interface that can hold any Comparable object type would look like:

			class MyTree<E extends Comparable<? super E>> implements BinaryTree<E> { }
		

Task 3: AVL Tree bonus

1. Change your binary tree class to implement the examples.BalancedBTree interface instead of examples.BinaryTree.

   BalancedBTree does not add any new methods…

   Javadoc interface file

2. Modify your TreeNode and BinaryTree implementations to perform the self-balancing behaviour of an AVL tree.

Submission

Completing all tasks in this lab should result in at least two Java files within a single package named like LastnameFirstname_lab6. A main method class is not required. Compress the package directory into a ZIP archive and upload it to the D2L assignment.

The marks for this lab are heavily weighted towards good coding practice and style. Pay attention to your code formatting, make sure you have documented all public members using JavaDoc, and make sure you are using constants, arrays, loops, and methods effectively.

NOTE: This assignment is to be done individually. You can help one another with problems and questions, but in the end everyone must do their own work.