CSci 2101: Binary Search Tree

JUnit Test code for Binary Search Tree

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));
		
	}
}
			      

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.