This is a solution from the group that worked in Sci 2185. Removing an element is not finished at this point.
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
public class TestBST {
private BinarySearchTree<Integer,String> emptyTree = new BinarySearchTree<Integer,String>();
private BinarySearchTree<Integer,String> eightNodesTree= new BinarySearchTree<Integer,String>();
@Before
public void setUp() {
eightNodesTree.put(4,"apple");
eightNodesTree.put(6,"banana");
eightNodesTree.put(1,"strawberry");
eightNodesTree.put(3,"kiwi");
eightNodesTree.put(7,"lemon");
eightNodesTree.put(10,"lime");
eightNodesTree.put(6,"mango");
eightNodesTree.put(8,"pear");
}
@Test
public void TestEmpty() {
assertTrue(emptyTree.isEmpty());
assertEquals(0,emptyTree.size());
}
@Test
public void TestNonEmpty() {
emptyTree.put(4,"apple");
assertFalse(emptyTree.isEmpty());
assertEquals(1,emptyTree.size());
}
@Test
public void TestPutGetRoot() {
emptyTree.put(4,"apple");
assertEquals("apple",emptyTree.get(4));
}
@Test
public void TestGetFromEmpty() {
assertNull(emptyTree.get(4));
}
@Test
public void TestGet() {
assertEquals("strawberry",eightNodesTree.get(1));
assertEquals("lemon",eightNodesTree.get(7));
}
@Test
public void TestGetNotThere() {
assertNull(eightNodesTree.get(5));
}
@Test (expected=NullPointerException.class)
public void TestNullKey() {
assertNull(eightNodesTree.get(null));
}
@Test
public void TestSize() {
assertEquals(8,eightNodesTree.size());
}
@Test
public void TestClear() {
eightNodesTree.clear();
assertTrue(eightNodesTree.isEmpty());
assertEquals(0,eightNodesTree.size());
assertNull(eightNodesTree.get(4));
}
// to-do: tests for remove, tree traversals
@Test
public void TestRemove() {
assertEquals("pear", eightNodesTree.remove(8));
assertEquals(7,eightNodesTree.size());
}
@Test
public void TestInOrder() {
List<Pair<Integer,Integer>> thelist = new ArrayList<Pair<Integer,Integer>>();
thelist.add(new Pair<Integer,Integer>(1,1));
thelist.add(new Pair<Integer,Integer>(2,2));
thelist.add(new Pair<Integer,Integer>(3,3));
thelist.add(new Pair<Integer,Integer>(4,4));
assertEquals(thelist,fourNodesTree.inOrder());
}
@Test
public void TestEmptyInOrder() {
List<Pair<Integer,Integer>> thelist = new ArrayList<Pair<Integer,Integer>>();
assertEquals(thelist,emptyTree.inOrder());
}
}
Starting code for binary serach tree:
/**
* 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) {
if (root == null){
root= new BSTNode(key,value);
}
else{
moveDown(root, new BSTNode(key, value));
}
count++;
}
private void moveDown(BSTNode current, BSTNode element){
if (current.key.compareTo(element.key) <= 0) {
// go right
if (current.right != null) {
moveDown(current.right, element);
}
else {
current.right = element;
}
}
else {
// go left
if (current.left != null) {
moveDown(current.left, element);
}
else {
current.left = element;
}
}
}
/**
* 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) {
if (key == null){
throw new NullPointerException();
}
BSTNode current = root;
while (current != null){
if (current.key.compareTo(key) == 0) {
return current.value;
}
else if (current.key.compareTo(key) < 0) {
// go right
current = current.right;
}
else {
// go left
current = current.left;
}
}
return null;
}
/**
* 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) {
if (key == null){
throw new NullPointerException();
}
BSTNode current = root;
while (current != null){
if (current.key.compareTo(key) == 0) {
return removeNode(current);
}
else if (current.left.key.compareTo(key) == 0){
return removeNode(current.left);
}
else if(current.right.key.compareTo(key) == 0) {
return removeNode(current.right);
}
else if (current.key.compareTo(key) < 0) {
// go right
current = current.right;
}
else {
// go left
current = current.left;
}
}
return null;
}
// method assumes not removing root
private V removeNode(BSTNode parent, boolean left) {
BSTNode nodeToRemove = left ? parent.left : parent.right;
V item = nodeToRemove.value;
if (nodeToRemove.right != null) {
if (left) {
parent.left = nodeToRemove.right;
}
else {
parent.right = nodeToRemove.right;
}
// working here - go to bottom right
}
else {
if (left) {
parent.left = nodeToRemove.left;
}
else {
parent.right = nodeToRemove.left;
}
// working here - go to bottom left
}
return item;
}
/**
* 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;
}
}
public ArrayList<Pair<K,V>> inOrder() {
ArrayList<Pair<K,V>> arrList= new ArrayList<Pair<K,V>>();
inOrderIt(root, arrList);
return arrList;
}
private void inOrderIt(BSTNode node, ArrayList<Pair<K,V>> aList){
if (node == null) return;
inOrderIt(node.left, aList);
aList.add(new Pair<K,V>(node.key, node.value));
inOrderIt(node.right, aList);
}
}