Programming Assignment:
Binary Search Trees
Objectives
The purpose of this exercise is to learn about how to implement trees,
how to design and implement a tree iterator, and how to perform level
order traversal of trees. Another purpose is to practice recursion.
Work on this exercise by yourself.
Check-out Instructions
Your work for this assignment should be done in the
BinarySearchTree
project inside Eclipse. Check out this project from your
personal
SVN repository for this course.
Your personal SVN repository URL is:
http://svn.csse.rose-hulman.edu/repos/csse230-201420-username
where
username
is your Rose-Hulman username. Recall that your SVN password may be
different than
your Rose-Hulman network password. Your SVN password should be unchanged from previous terms. If this is your first term with an SVN account at Rose-Hulman, then you should have received an email from root with your password.
If you are unable to remember or find your SVN password, please let
your instructor know and he/she will run a script to reset it
to a new random string of characters or to a string that you specify.
Be sure to commit your work often as you make progress on these programs. This will help you recover from mistakes, power failures, and freak accidents.
What will be graded is what is in your repository, so do not forget to
commit.
See the Using Subclipse instructions at the end of
this page for more information on using your SVN repository.
Milestone One
For milestone one, please add the following functionality to the
BinarySearchTree project, as found on svn.
- Implement basic BinarySearchTree and BinaryNode
classes.
- Implement the following methods. You can test each using the following unit testcases. They assume that you
have not implemented the insert() method.
- A boolean isEmpty() method, which returns true if the tree is
empty and false otherwise.
- A recursive int height() method which
returns the height of the tree. If the tree is empty, return -1.
- A recursive String toString() method which
returns a String containing the elements of the tree.
- A recursive int size() method which
returns the number of elements in the tree.
Milestone Two
For milestone two, please add the following functionality to your
BinarySearchTree project.
- A ArrayList<Object> toArrayList() method which returns
an ArrayList of the elements in-order.
- A Object[] toArray() method which returns
an array of the elements in-order.
(toArrayList() can help do this!)
- (Optional warmup: an iterator that calls
the toArrayList() method and iterates over the list. This iterator should be returned when you call the
public Iterator arrayListIterator() method. This is NOT a lazy iterator.)
-
A lazy iterator that performs pre-order traversal. This
iterator should be returned when you call the public Iterator
preOrderIterator() method.
- A lazy iterator that performs in-order traversal. This
iterator should be returned when you call the public Iterator
iterator() method.
- Both iterators have to throw a NoSuchElementException if
the iteration has no more elements.
- Make your BinarySearchTree class iterable
Milestone Three
For this milestone, please add the following functionality to your
BinarySearchTree project.
- You are not permitted to maintain pointers to parents in the
fields of your BinaryNode or BinarySearchTree classes.
- Ensure that your toString() method of the BinarySearchTree class returns the
elements of the tree inorder and according to the same specs as
for the Java TreeSet class.
- [5 pts] Ensure that your BinaryNode class as well as the two
iterators are inner classes and that your code takes advantage of the
access rights that come with inner classes.
- Modify your iterators so that the next() methods throw a
ConcurrentModificationException if the tree gets modified after
you create the iterator and before you are done with it.
- [5 pts] Ensure that you use parameterized generics whenever
possible. Call your type parameter T. Ensure that your BinarySearchTree class is properly
parameterized to accept only Comparables. Furthermore ensure that
BinarySearchTree implements the parameterized "Iterable<T>" interface. Note that
the toArray() method from above must still return an array of type
Object[], not T[]. This is according to the Java spec. Read
this for some hints, especially if you are
maintaining NULL_NODEs in your code.
- A recursive boolean
insert(T o) method. Assume that you are inserting into a Binary Search Tree,
and make sure you insert it in a place so that it continues to be a Binary
Search Tree. Throw an
IllegalArgumentException if you pass it a null pointer. It has
to return true if the tree was modified and false otherwise. The recursion
takes place in the BinaryNode class.
- [15 pts] Review your code and ensure that it is well written. Look
for places where you can simplify through code reuse and other
methods. Among others, none of the methods in the BinarySearchTree
class proper should be recursive. Recursion should only take place in
the BinaryNode class proper.
- [5 pts] Add JavaDoc comments.
- Add a boolean remove(T element) method which returns true if the
element was successfully removed.
Throw an
IllegalArgumentException if the element to remove is null.
When removing a node with two children,
replace its value with the largest element in its left subtree. Ensure that the
recursion takes place in the BinaryNode class. Please notice that the recursive
remove method in the BinaryNode class will have BinaryNode as a return type. You
may not modify the BinaryNode class so that it maintains pointers to the parent
node. Please ensure that your code is concise and well written. Furthermore
ensure that your remove method in the BinaryTree/Node class is
thread-safe when it comes to the return type. In other words, you cannot have
some global variable which captures whether an element was successfully removed.
We recommend that you add to the remove method of the BinaryNode class an
additional, mutable parameter. (This is also a good way to implement insert so
it returns a boolean.)
- Implement the void remove() method in both of the lazy iterators.
Have a look at the documentation of the remove method as found in the Java
Collections API. Ensure that you throw the proper exceptions.
- Add T get(T e) method. It returns
the object e passed to it, if it occurs in the tree and null otherwise.
Notice that this is a method that could be used to find elements in a tree. In
real life, it would be more complex.
Here are the unit test cases that we
will use for scoring your software.
Turn-in Instructions
Turn in your work by committing it to your SVN repository. We
recommend committing often, whenever you have made some progress
toward a solution to one of the problems. Your last commit
date will determine the status of your submission as on-time, early,
or late (See the Late Days policy in the course syllabus).