Question
I need to finish a Binary Search Tree class in java.(Just need to finish some methods inside.) The name of the class is BinarySearchTree.java .
I need to finish a Binary Search Tree class in java.(Just need to finish some methods inside.) The name of the class is BinarySearchTree.java.
I also have a BSTNode.java which creates the node in the BST.
Finally, I have a JUnit test file PublicBinarySearchTreeTest.java for you to test your code.
* My changes must NOT break the semantics of the methods.
* I may NOT change the signatures of the public methods, or add or remove public methods to the interface.
I WILL upvote if your codes pass the JUnit tests I provided. Thanks for your help.
Here is BinarySearchTree.java:
package structures;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class BinarySearchTree
protected BSTNode
public boolean isEmpty() {
return root == null;
}
public int size() {
return subtreeSize(root);
}
protected int subtreeSize(BSTNode
if (node == null) {
return 0;
} else {
return 1 + subtreeSize(node.getLeft())
+ subtreeSize(node.getRight());
}
}
/**
* @return true if and only if the element is stored in the tree
* @throws NullPointerException if element is null
*/
public boolean contains(T t) {
// TODO
return false;
}
public boolean remove(T t) {
if (t == null) {
throw new NullPointerException();
}
boolean result = contains(t);
if (result) {
root = removeFromSubtree(root, t);
}
return result;
}
private BSTNode
// node must not be null
int result = t.compareTo(node.getData());
if (result < 0) {
node.setLeft(removeFromSubtree(node.getLeft(), t));
if (node.getLeft() != null) {
node.getLeft().setParent(node);
}
return node;
} else if (result > 0) {
node.setRight(removeFromSubtree(node.getRight(), t));
if (node.getRight() != null){
node.getRight().setParent(node);
}
return node;
} else { // result == 0
if (node.getLeft() == null) {
return node.getRight();
} else if (node.getRight() == null) {
return node.getLeft();
} else { // neither child is null
T predecessorValue = getHighestValue(node.getLeft());
node.setLeft(removeRightmost(node.getLeft()));
if (node.getLeft() != null) {
node.getLeft().setParent(node);
}
node.setData(predecessorValue);
return node;
}
}
}
private T getHighestValue(BSTNode
// node must not be null
if (node.getRight() == null) {
return node.getData();
} else {
return getHighestValue(node.getRight());
}
}
private BSTNode
// node must not be null
if (node.getRight() == null) {
return node.getLeft();
} else {
node.setRight(removeRightmost(node.getRight()));
if (node.getRight() != null){
node.getRight().setParent(node);
}
return node;
}
}
/**
* @return the element in the tree which .equals() the argument, or null if no such element exists
* @throws NullPointerException if element is null
*/
public T get(T t) {
// TODO
return null;
}
public void add(T t) {
if (t == null) {
throw new NullPointerException();
}
root = addToSubtree(root, new BSTNode
}
protected BSTNode
if (node == null) {
return toAdd;
}
int result = toAdd.getData().compareTo(node.getData());
if (result <= 0) {
node.setLeft(addToSubtree(node.getLeft(), toAdd));
if (node.getLeft() != null) {
node.getLeft().setParent(node);
}
} else {
node.setRight(addToSubtree(node.getRight(), toAdd));
if (node.getRight() != null){
node.getRight().setParent(node);
}
}
return node;
}
/**
* @return the least value stored in this tree, or null if the tree is empty
*/
public T getMinimum() {
// TODO
return null;
}
/**
* @return the greatest value stored in this tree, or null if the tree is empty
*/
public T getMaximum() {
// TODO
return null;
}
/**
* @return the height(levels) of the tree, or -1 if the tree is empty
*/
public int height() {
// TODO
return -2;
}
/**
* Returns an Iterator that performs a preorder traversal of the tree.
* The Iterator's behavior is not defined in the case that the tree is
* modified before the iteration is finished.
* @return an Iterator over the elements in preorder
*/
public Iterator
// TODO
return null;
}
public Iterator
Queue
inorderTraverse(queue, root);
return queue.iterator();
}
private void inorderTraverse(Queue
if (node != null) {
inorderTraverse(queue, node.getLeft());
queue.add(node.getData());
inorderTraverse(queue, node.getRight());
}
}
/**
* Returns an Iterator that performs a postorder traversal of the tree.
* The Iterator's behavior is not defined in the case that the tree is
* modified before the iteration is finished.
* @return an Iterator over the elements in preorder
*/
public Iterator
// TODO
return null;
}
/**
* Returns true if and only if this tree and the other tree have the same
* structure, and equivalent values at each node. Uses equals() to check
* for node value equivalence.
* @return true if and only if the trees are structure- and value-equivalent
* @throws NullPointerException if other is null
*/
public boolean equals(BSTInterface
// TODO
return false;
}
/**
* Returns true if and only if this tree and the other tree store the same
* values, regardless of structure. Uses equals() to check
* for stored value equivalence.
* @return true if and only if the trees are value-equivalent
* @throws NullPointerException if other is null
*/
public boolean sameValues(BSTInterface
// TODO
return false;
}
/**
* Returns true if and only if the tree is completely balanced. A balanced
* tree is either a full tree, or a tree that would be full if all leaves in
* the highest level were removed.
* An empty tree is considered balanced.
* @return true if and only if the tree is balanced
*/
public boolean isBalanced() {
// TODO
return false;
}
/**
* Modifies the tree such that it is completely balanced.
* The modified tree must still obey the BST rule, and must contain the same
* values it did before it was balanced.
*/
public void balance() {
// TODO
}
public BSTNode
// DO NOT MODIFY
return root;
}
Here is BSTNode.java:
package structures;
public class BSTNode
private T data;
private BSTNode
private BSTNode
private BSTNode
public static final boolean RED = true;
public static final boolean BLACK = false;
private boolean color;
public BSTNode(T data, BSTNode
this.data = data;
this.left = left;
this.right = right;
parent = null;
}
public BSTNode(T data, BSTNode
this.data = data;
this.left = left;
this.right = right;
this.color = color;
parent = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public boolean getColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public BSTNode
return left;
}
public void setLeft(BSTNode
this.left = left;
}
public BSTNode
return right;
}
public void setRight(BSTNode
this.right = right;
}
public BSTNode
return parent;
}
public void setParent(BSTNode
this.parent = p;
}
public void printSubtree(int spaces) {
if (right != null) {
right.printSubtree(spaces + 5);
}
for (int i = 0; i < spaces; i++) {
System.out.print(" ");
}
System.out.print(data);
System.out.print('-');
System.out.println(color);
if (left != null) {
left.printSubtree(spaces + 5);
}
}
}
Here is PublicBinarySearchTreeTest.java:
package structures;
import static org.junit.Assert.*;
import java.util.Iterator;
import java.util.concurrent.TimeUnit;
import org.junit.Rule;
import org.junit.Test;
import org.junit.Before;
import org.junit.rules.Timeout;
public class PublicBinarySearchTreeTest {
private BSTInterface
private BSTInterface
private static final String FOO = "foo";
@Rule
public Timeout timeout = new Timeout(1L, TimeUnit.SECONDS);
@Before
public void before() {
emptyTree = new BinarySearchTree
oneNodeTree = new BinarySearchTree
oneNodeTree.add(FOO);
}
@Test
public void testEmpty() {
assertTrue(emptyTree.isEmpty());
}
@Test
public void testNotEmpty() {
assertFalse(oneNodeTree.isEmpty());
}
@Test
public void testSize() {
assertEquals(0, emptyTree.size());
assertEquals(1, oneNodeTree.size());
}
@Test
public void testContains() {
assertTrue(oneNodeTree.contains(FOO));
}
@Test
public void testRemove() {
assertFalse(emptyTree.remove(0));
}
@Test
public void testGet() {
assertEquals(FOO, oneNodeTree.get(FOO));
}
@Test
public void testAdd() {
emptyTree.add(1);
assertFalse(emptyTree.isEmpty());
assertEquals(1, emptyTree.size());
}
@Test
public void testGetMinimum() {
assertEquals(null, emptyTree.getMinimum());
}
@Test
public void testGetMaximum() {
assertEquals(FOO, oneNodeTree.getMaximum());
}
@Test
public void testHeight() {
assertEquals(-1, emptyTree.height());
assertEquals(0, oneNodeTree.height());
}
@Test
public void testPreorderIterator() {
Iterator
while (i.hasNext()) {
assertEquals(FOO, i.next());
}
}
@Test
public void testInorderIterator() {
Iterator
while (i.hasNext()) {
assertEquals(FOO, i.next());
}
}
@Test
public void testPostorderIterator() {
Iterator
assertFalse(i.hasNext());
}
@Test
public void testEquals() {
BSTInterface
assertFalse(oneNodeTree.equals(tree));
tree.add(new String("foo"));
assertTrue(oneNodeTree.equals(tree));
}
@Test
public void testSameValues() {
BSTInterface
assertTrue(emptyTree.sameValues(tree));
emptyTree.add(1);
emptyTree.add(2);
tree.add(2);
tree.add(1);
assertTrue(emptyTree.sameValues(tree));
}
@Test
public void testIsBalanced() {
// disabled due to late change of isBalanced() specification
// assertTrue(emptyTree.isBalanced());
emptyTree.add(1);
assertTrue(emptyTree.isBalanced());
emptyTree.add(2);
assertTrue(emptyTree.isBalanced());
emptyTree.add(3);
assertFalse(emptyTree.isBalanced());
}
@Test
public void testBalance() {
emptyTree.add(1);
emptyTree.add(2);
emptyTree.add(3);
assertFalse(emptyTree.isBalanced());
emptyTree.balance();
assertTrue(emptyTree.isBalanced());
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started