This is a solution from the group that worked in the lab. Removing an element is not implemented at this point. The testing code is unchanged.
Binary serach tree code:
/**
* Binary search tree stores values indexed by keys. Keys must be Comparable and
* are organized based on their natural ordering (i.e. the ordering given by
* their compareTo). Values can be of any object type. This tree implementation
* is not balanced, i.e. it may behave as a linked list in the worst case. Keys
* may be repeated. Somewhat modeled after Map<K,V> classes in the Java
* Collections Framework
*
* Author: Elena Machkasova For UMM CSci 2101 class (version for Summer 2011).
**/
public class BinarySearchTree<K extends Comparable<K>, V> {
private BSTNode root = null;
private int count = 0;
/**
* @return true if the tree is empty, false otherwise
**/
public boolean isEmpty() {
return root == null;
}
/**
* @return the number of elements in the tree
**/
public int size() {
return count;
}
/**
* Adds a given value indexed with a given key to the tree according to the
* binary search structure
*
* @param key
* - the key of the given element
* @param value
* - the value of the given element
*/
public void put(K key, V value) {
BSTNode parentnode = root;
BSTNode toAdd = new BSTNode(key,value);
if(isEmpty()){
root = toAdd;
count++;
}else{
recursive(parentnode, toAdd);
count++;
}
}
private void recursive(BSTNode parentNode, BSTNode addedNode){
if(addedNode.key.compareTo(parentNode.key)<0){
if(parentNode.left == null){
//return parentNode;
parentNode.left = addedNode;
}
else{
recursive(parentNode.left,addedNode);
}
}
else {
if(parentNode.right == null){
//return parentNode;
parentNode.right = addedNode;
}
else{
recursive(parentNode.right,addedNode);
}
}
}
/**
* returns a value associated with the given key in this binary search tree.
* If multiple values are associated with this key, any one may be returned.
* If there is no element associated with this key, null is returned.
*
* @param key
* - the key to search for.
* @return - a value to which the specified key is mapped, or null if this
* tree contains no mapping for the key
* @throws NullPointerException if the key is null
*/
public V get(K key) {
BSTNode current = root;
if(isEmpty()){
return null;
}
BSTNode aNode = recursiveGet(current, key);
if(aNode==null){
return null;
}
return aNode.value;
}
private BSTNode recursiveGet(BSTNode theNode, K key){
if(theNode.key.compareTo(key)==0){
return theNode;
}
if(theNode.key.compareTo(key)>0){
if(theNode.left==null){
return null;
}
return recursiveGet(theNode.left, key);
}else {
if(theNode.right==null){
return null;
}
return recursiveGet(theNode.right, key);
}
}
/**
* Removes an element with the given key. The resulting tree is a binary
* search tree. If there is no such key, the tree is unchanged. If there are
* multiple values associated with this key, only one is removed. Returns
* the value associated with this key or null if there is no such value.
*
* @param key
* - the key
* @return - a value to which the specified key is mapped, or null if this
* tree contains no mapping for the key
* @throws NullPointerException if the key is null
*/
public V remove(K key) {
count--; //change later =]
return null;
}
/**
* Clears all elements from a given tree.
* The resulting tree is empty.
*/
public void clear() {
root = null;
count = 0;
}
private class BSTNode {
public K key;
public V value;
public BSTNode left = null;
public BSTNode right = null;
// null key will generate a null pointer exception when
// a method (such as compareTo) is called on it.
// This is fine, according to the JCF specification.
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
}
}
}