Create A Binary Search Tree ADT in Java Assignment Solution
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a program to create a binary search tree ADT in java language.
Requirements and Specifications
Source Code
package edu.uwm.cs351.ps;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import junit.framework.TestCase;
public class Dictionary {
private static class Node {
Name key;
Object data;
Node left, right;
Node(Name k, Object d) { key = k; data = d; }
}
private Node root;
private int size;
private static boolean doReport = true;
private static boolean report(String s) {
if (doReport) System.err.println("Invariant error: " + s);
return false;
}
// This method is useful for checkTree if errors are found.
private static int reportNeg(String s) {
report(s);
return -1;
}
/**
* Check if a subtree is well formed.
* None of the keys may be null and all of the keys must be
* in the given range (lo,hi) exclusive, except that a null bound means
* there is no bound in that direction, and finally all subtrees
* must also be well formed.
* @param r root of the subtree, may be null
* @param lo exclusive lower bound. If null, then no lower bound.
* @param hi exclusive upper bound. If null, then no upper bound.
* @return number of nodes in subtree, if well formed, -1 otherwise.
*/
private static int checkTree(Node r, String lo, String hi) {
if (r == null) {
return 0;
}
if (r.key == null) {
return -1;
}
if (lo != null && r.key.rep.compareTo(lo) <= 0) {
return -1;
}
if (hi != null && r.key.rep.compareTo(hi) >= 0) {
return -1;
}
int lres = checkTree(r.left, lo, r.key.rep);
int rres = checkTree(r.right, r.key.rep, hi);
if (lres == -1 || rres == -1) {
return -1;
}
return 1 + lres + rres;
}
private boolean wellFormed() {
// NB: If you correct check for things in range (and no duplicates)
// then cycles will be automatically detected (they will be duplicates).
int checkSize = checkTree(root, null, null);
if (checkSize == -1) {
return false;
}
return size == checkSize;
}
/**
* Create an empty dictionary.
*/
public Dictionary() {
size = 0;
root = null;
assert wellFormed() : "invariant broken in constructor";
}
private Object[] get(Node currNode, Name n) {
if (currNode == null) {
return null;
}
String currName = currNode.key.rep;
int diff = currName.compareTo(n.rep);
if (diff > 0) {
return get(currNode.left, n);
}
else if (diff < 0) {
return get(currNode.right, n);
}
else {
return new Object[]{currNode.data};
}
}
/**
* Return the definition of a name in this dictionary
* @param n name to lookup, may not be null
* @return definition for the name
* @throws ExecutionException if there is no definition, or if the name is null
*/
public Object get(Name n) throws ExecutionException {
assert wellFormed() : "invariant broken at start of get()";
if (n == null) {
throw new ExecutionException();
}
Object[] result = get(root, n);
if (result != null) {
return result[0];
}
throw new ExecutionException("undefined");
}
/**
* Return whether the parameter is a name in the dictionary
* @param n name to look up, may be null
* @return whether n is a name in the dictionary
*/
public boolean known(Name n) {
assert wellFormed() : "invariant broken at start of known()";
if (n == null) {
return false;
}
return get(root, n) != null;
}
/**
* Return the number of names defined in the dictionary.
* @return number of names in dictionary.
*/
public int size() {
assert wellFormed() : "invariant broken at start of size()";
return size;
}
private void put(Node currNode, Name n, Object x) {
String currName = currNode.key.rep;
int diff = currName.compareTo(n.rep);
if (diff > 0) {
if (currNode.left == null) {
currNode.left = new Node(n, x);
size++;
}
else {
put(currNode.left, n, x);
}
}
else if (diff < 0) {
if (currNode.right == null) {
currNode.right = new Node(n, x);
size++;
}
else {
put(currNode.right, n, x);
}
}
else {
currNode.data = x;
}
}
/**
* Define a name in the dictionary.
* If the name already has a definition, the old definition is replaced
* with the new definition.
* @param n name to defined (must not be null)
* @param x (new) definition of the name (may be null)
* @exception ExecutionException if the name is null
*/
public void put(Name n, Object x) {
assert wellFormed() : "invariant broken at start of put()";
if (n == null) {
throw new ExecutionException();
}
if (root == null) {
root = new Node(n, x);
size = 1;
return;
}
put(root, n, x);
assert wellFormed() : "invariant broken at end of put()";
}
private void copy(Node currNode) {
if (currNode == null) {
return;
}
put(currNode.key, currNode.data);
copy(currNode.left);
copy(currNode.right);
}
/**
* Copy all the definitions from the argument into this dictionary
* replacing previous definitions (if any).
* @param dict1 dictionary whose definition we copy (must not be null)
* NB: Behavior if the argument is null is not defined.
*/
public void copy(Dictionary dict1) {
assert wellFormed() : "invariant broken at start of copy()";
if (dict1 == null) {
return;
}
copy(dict1.root);
assert wellFormed() : "invariant broken at start of copy()";
}
private void values(Node currNode, Collection collection) {
if (currNode == null) {
return;
}
values(currNode.left, collection);
collection.add(currNode.data);
values(currNode.right, collection);
}
/**
* Return a collection with a copy of all the definitions
* in the dictionary in sorted order.
* @return a collection which has a copy of all definitions of names in the
* dictionary, in order of the names that were defined.
*/
public Collection values() {
assert wellFormed() : "invariant broken at start of values()";
Collection result = new ArrayList<>();
values(root, result);
return result;
}
private void toString(Node currNode, StringBuilder stringBuilder) {
if (currNode == null) {
return;
}
toString(currNode.left, stringBuilder);
if (stringBuilder.length() > 0) {
stringBuilder.append(" ");
}
stringBuilder.append(currNode.key).append(" ").append(currNode.data);
toString(currNode.right, stringBuilder);
}
/**
* Return a string of the form << name1 value1 name2 value2 ... namek valuek >>
* where the names are in order and everything is separated by single spaces.
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
toString(root, sb);
if (sb.length() == 0) {
return "<< >>";
}
sb.insert(0, "<< ");
sb.append(" >>");
return sb.toString();
}
public static class TestInvariant extends TestCase {
protected Dictionary self;
private Node[] n;
private Name n0 = new Name("N");
protected Name n(int i) {
return new Name("N" + (1000+i));
}
@Override
protected void setUp() {
self = new Dictionary();
self.root = null;
self.size = 0;
n = new Node[15];
for (int i=0; i < 15; ++i) {
n[i] = new Node(n(i*10),i);
}
n[0].key = null;
n[6].left = n[2]; n[6].right = n[10];
n[2].left = n[1]; n[2].right = n[5];
n[5].left = n[3];
n[3].right = n[4];
n[10].left = n[9]; n[10].right = n[12];
n[9].left = n[7];
n[7].right = n[8];
n[12].left = n[11]; n[12].right = n[13];
doReport = false;
}
public void testA() {
assertEquals(0,checkTree(null,null,null));
assertEquals(-1,checkTree(n[0],null,null));
assertEquals(1,checkTree(n[1],null,null));
assertEquals(0,checkTree(null,"bar","foo"));
}
public void testB() {
assertEquals(1,checkTree(n[1],n(9).rep,n(11).rep));
assertEquals(1,checkTree(n[1],n(0).rep,null));
assertEquals(1,checkTree(n[1],null,n(20).rep));
assertEquals(-1,checkTree(n[1],n(9).rep,n(10).rep));
assertEquals(-1,checkTree(n[1],n(10).rep,n(11).rep));
assertEquals(-1,checkTree(n[1],n(10).rep,null));
assertEquals(-1,checkTree(n[1],null,n(10).rep));
}
public void testC() {
assertEquals(13,checkTree(n[6],null,null));
assertEquals(13,checkTree(n[6],n(0).rep,n(140).rep));
assertEquals(-1,checkTree(n[6],n(15).rep,null));
assertEquals(-1,checkTree(n[6],null,n(125).rep));
}
public void testD() {
self.root = null;
self.size = 0;
doReport = true;
assertTrue(self.wellFormed());
}
public void testE() {
self.root = n[1];
self.size = 0;
assertFalse(self.wellFormed());
self.size = 2;
assertFalse(self.wellFormed());
self.size = -1;
assertFalse(self.wellFormed());
self.size = 1;
doReport = true;
assertTrue(self.wellFormed());
}
public void testF() {
self.root = n[0];
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
doReport = true;
assertTrue(self.wellFormed());
}
public void testG() {
self.root = n[14];
self.size = 2;
n[14].right = n[1];
assertFalse(self.wellFormed());
n[14].right = null;
n[14].left = n[1];
doReport = true;
assertTrue(self.wellFormed());
}
public void testH() {
self.root = n[1];
self.size = 2;
n[1].left = n[14];
assertFalse(self.wellFormed());
n[1].left = null;
n[1].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
public void testI() {
self.root = n[3]; // n[3]'s right is n[4]
self.size = 3;
n[4].left = n[0];
assertFalse(self.wellFormed());
self.size = 0;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 3;
assertFalse(self.wellFormed());
n[4].left = null;
n[4].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
public void testJ() {
self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]
self.size = 4;
n[4].right = n[14];
assertFalse(self.wellFormed());
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 4;
assertFalse(self.wellFormed());
n[4].right = null;
assertFalse(self.wellFormed());
self.size = 3;
doReport = true;
assertTrue(self.wellFormed());
}
public void testK() {
self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]
self.size = 4;
n[4].left = n[0];
assertFalse(self.wellFormed());
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 4;
assertFalse(self.wellFormed());
n[0].key = n(35);
doReport = true;
assertTrue(self.wellFormed());
}
// The following tests concern the tree
// (((10)20(((30(40))50)60((70(80))90)))100((110)120(130)))
public void testL() {
self.root = n[6]; // whole tree
self.size = 13;
doReport = true;
assertTrue(self.wellFormed());
}
public void testM() {
self.root = n[6];
self.size = 14;
n[1].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(10);
assertFalse(self.wellFormed());
n[1].left = n[1];
assertFalse(self.wellFormed());
n[1].left = n[0];
n[0].key = n(05);
doReport = true;
assertTrue(self.wellFormed());
}
public void testN() {
self.root = n[6];
self.size = 14;
n[1].right = n[14];
assertFalse(self.wellFormed());
n[1].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(20);
assertFalse(self.wellFormed());
n[1].right = n[2];
assertFalse(self.wellFormed());
n[1].right = n[0];
n[0].key = n(15);
doReport = true;
assertTrue(self.wellFormed());
}
public void testO() {
self.root = n[6];
self.size = 14;
n[3].left = n[1];
assertFalse(self.wellFormed());
n[3].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(20);
assertFalse(self.wellFormed());
n[3].left = n[2];
assertFalse(self.wellFormed());
n[3].left = n[0];
n[0].key = n(25);
doReport = true;
assertTrue(self.wellFormed());
}
public void testP() {
self.root = n[6];
self.size = 14;
n[4].left = n[1];
assertFalse(self.wellFormed());
n[4].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(30);
assertFalse(self.wellFormed());
n[4].left = n[3];
assertFalse(self.wellFormed());
n[4].left = n[0];
n[0].key = n(35);
doReport = true;
assertTrue(self.wellFormed());
}
public void testQ() {
self.root = n[6];
self.size = 14;
n[4].right = n[14];
assertFalse(self.wellFormed());
n[4].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(50);
assertFalse(self.wellFormed());
n[4].right = n[5];
assertFalse(self.wellFormed());
n[4].right = n[0];
n[0].key = n(45);
doReport = true;
assertTrue(self.wellFormed());
}
public void testR() {
self.root = n[6];
self.size = 14;
n[5].right = n[14];
assertFalse(self.wellFormed());
n[5].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(60);
assertFalse(self.wellFormed());
n[5].right = n[6];
assertFalse(self.wellFormed());
n[5].right = n[0];
n[0].key = n(55);
doReport = true;
assertTrue(self.wellFormed());
}
public void testS() {
self.root = n[6];
self.size = 14;
n[7].left = n[1];
assertFalse(self.wellFormed());
n[7].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(60);
assertFalse(self.wellFormed());
n[7].left = n[6];
assertFalse(self.wellFormed());
n[7].left = n[0];
n[0].key = n(65);
doReport = true;
assertTrue(self.wellFormed());
}
public void testT() {
self.root = n[6];
self.size = 14;
n[8].left = n[1];
assertFalse(self.wellFormed());
n[8].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(70);
assertFalse(self.wellFormed());
n[8].left = n[7];
assertFalse(self.wellFormed());
n[8].left = n[0];
n[0].key = n(75);
doReport = true;
assertTrue(self.wellFormed());
}
public void testU() {
self.root = n[6];
self.size = 14;
n[8].right = n[14];
assertFalse(self.wellFormed());
n[8].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(90);
assertFalse(self.wellFormed());
n[8].right = n[9];
assertFalse(self.wellFormed());
n[8].right = n[0];
n[0].key = n(85);
doReport = true;
assertTrue(self.wellFormed());
}
public void testV() {
self.root = n[6];
self.size = 14;
n[9].right = n[14];
assertFalse(self.wellFormed());
n[9].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(100);
assertFalse(self.wellFormed());
n[9].right = n[10];
assertFalse(self.wellFormed());
n[9].right = n[0];
n[0].key = n(95);
doReport = true;
assertTrue(self.wellFormed());
}
public void testW() {
self.root = n[6];
self.size = 14;
n[11].left = n[1];
assertFalse(self.wellFormed());
n[11].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(100);
assertFalse(self.wellFormed());
n[11].left = n[10];
assertFalse(self.wellFormed());
n[11].left = n[0];
n[0].key = n(105);
doReport = true;
assertTrue(self.wellFormed());
}
public void testX() {
self.root = n[6];
self.size = 14;
n[11].right = n[14];
assertFalse(self.wellFormed());
n[11].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(120);
assertFalse(self.wellFormed());
n[11].right = n[12];
assertFalse(self.wellFormed());
n[11].right = n[0];
n[0].key = n(115);
doReport = true;
assertTrue(self.wellFormed());
}
public void testY() {
self.root = n[6];
self.size = 14;
n[13].left = n[1];
assertFalse(self.wellFormed());
n[13].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(120);
assertFalse(self.wellFormed());
n[13].left = n[12];
assertFalse(self.wellFormed());
n[13].left = n[0];
n[0].key = n(125);
doReport = true;
assertTrue(self.wellFormed());
}
public void testZ() {
self.root = n[6];
self.size = 14;
n[13].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(130);
assertFalse(self.wellFormed());
n[13].right = n[13];
assertFalse(self.wellFormed());
n[13].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
}
}
Similar Samples
Explore our expertise in programming homework assistance at ProgrammingHomeworkHelp.com. Browse through our sample solutions showcasing our commitment to quality and proficiency in diverse programming languages and topics. See how we can help you tackle your programming challenges effectively.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java