More tests are needed.
import static org.junit.Assert.*;
import java.util.ArrayList;
import org.junit.Before;
import org.junit.Test;
public class JUnitTraversalsTests {
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(5,"mango");
eightNodesTree.put(8,"pear");
}
@Test
public void TestEmptyTraversals() {
assertEquals(new ArrayList<KVPair<Integer,String>>(), emptyTree.inOrderPairs());
}
@Test
public void TestEightNodeInOrder() {
ArrayList<KVPair<Integer,String>> expected = new ArrayList<KVPair<Integer,String>>();
expected.add(new KVPair<Integer,String>(1,"strawberry"));
expected.add(new KVPair<Integer,String>(3, "kiwi"));
expected.add(new KVPair<Integer,String>(4, "apple"));
expected.add(new KVPair<Integer,String>(5, "mango"));
expected.add(new KVPair<Integer,String>(6, "banana"));
expected.add(new KVPair<Integer,String>(7, "lemon"));
expected.add(new KVPair<Integer,String>(8, "pear"));
expected.add(new KVPair<Integer,String>(10,"lime"));
assertEquals(expected,eightNodesTree.inOrderPairs());
}
}
Starting code for binary search tree:
import java.util.ArrayList;
/**
* 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.
**/
public class BinarySearchTree<K extends Comparable<K>, V> {
private BSTNode root = null;
private int size = 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 size;
}
/**
* 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);
size++;
} else {
root.put(key, value);
}
}
/**
* 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) {
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) {
return null;
}
/**
* Clears all elements from a given tree. The resulting tree is empty.
*/
public void clear() {
}
public void inOrder() {
if (root != null) {
root.nodeInOrder();
}
}
public void preOrder() {
if (root != null) {
root.nodePreOrder();
}
}
public ArrayList<KVPair<K,V>> inOrderPairs() {
ArrayList<KVPair<K,V>> result = new ArrayList<KVPair<K,V>>();
if (root != null) {
root.nodeInOrderPairs(result);
}
return result;
}
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 void nodeInOrderPairs(ArrayList<KVPair<K, V>> result) {
if (this.left != null) {
left.nodeInOrderPairs(result);
}
result.add(new KVPair<K,V>(this.key, this.value));
if (this.right != null) {
right.nodeInOrderPairs(result);
}
}
public void nodeInOrder() {
if (this.left != null)
left.nodeInOrder();
System.out.println(this.key + " " + this.value);
if (this.right != null)
right.nodeInOrder();
}
public void nodePreOrder() {
System.out.println(this.key + " " + this.value);
if (this.left != null)
left.nodePreOrder();
if (this.right != null)
right.nodePreOrder();
}
public void put(K key, V value) {
if (key.compareTo(this.key) <= 0) {
if (left == null) {
left = new BSTNode(key, value);
size++;
} else {
left.put(key, value);
}
} else {
if (right == null) {
right = new BSTNode(key, value);
size++;
} else {
right.put(key, value);
}
}
}
}
}
KVPair class
public class KVPair<K extends Comparable<K>,V> {
private K key;
private V value;
public KVPair(K key, V value) {
this.key = key;
this. value = value;
}
public String toString() {
return "" + key + " " + value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public boolean equals(Object o) {
if (!(o instanceof KVPair)) {
return false;
}
KVPair<K,V> other = (KVPair<K,V>) o;
return (key.equals(other.key) && value.equals(other.value));
}
}