Implement the insert, remove, and search methods of the BinarySearchTree
class. Included are the Main, Tree, and TreeException classes.
Do not make changes to those classes. Your tree should work with
them as shown. All operations should be implemented recursively.
Additional methods may be needed.
/*
* Tree.java
*
*/
import java.util.Iterator;
import java.util.Vector;
public abstract class Tree<E> implements Iterable<E> {
protected class Node<T> {
protected Node(T data) {
this.data = data;
}
protected T data;
protected Node<T> left;
protected Node<T> right;
}
public void insert(E data) {
Node<E> temp = new Node<E>(data);
root = insert(root, temp);
}
protected abstract Node<E> insert(Node<E> curr, Node<E> node);
public Iterator<E> iterator() {
Vector<E> vector = new Vector<E>();
traverse(vector, root);
return vector.iterator();
}
public void remove(E data) {
root = remove(root, data);
}
protected abstract Node<E> remove(Node<E> curr, E data) throws TreeException;
public boolean search(E key) {
return search(root, key);
}
protected abstract boolean search(Node<E> curr, E key);
private void traverse(Vector<E> vector, Node<E> curr) {
if (curr != null) {
traverse(vector, curr.left);
vector.add(curr.data);
traverse(vector, curr.right);
}
}
private Node<E> root;
}
/*
*
* TreeException.java
*
*/
public class TreeException extends RuntimeException {
public TreeException() {}
public TreeException(String msg) { super(msg); }
}/*
*
* BinarySearchTree.java
*
*/
public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E>
{
private Node insert(Comparable temp, Node curr) {
if(curr == null)
curr = new Node(temp);
else if(temp.compareTo(curr.data) < 0)
curr.left = insert(temp, curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = insert(temp, curr.right);
return curr;
}
private Node remove(Comparable temp, Node curr) {
if(curr == null)
throw new TreeException(temp.toString( ));
if(temp.compareTo(curr.data) < 0)
curr.left = remove(temp, curr.left );
else if(temp.compareTo(curr.data) > 0 )
curr.right = remove(temp, curr.right );
else if(curr.left != null && curr.right != null ) {
curr.data = findMin(curr.right).data;
curr.right = removeMin(curr.right );
} else
curr = ( curr.left != null ) ? curr.left : curr.right;
return curr;
}
private Node removeMin(Node curr) {
if(curr == null) {
throw new TreeException();
}
else if(curr.left != null) {
curr.left = removeMin(curr.left);
return curr;
}
else {
return curr.right;
}
}
private Node findMin(Node curr) {
if(curr != null) {
while(curr.left != null) {
curr = curr.left;
}
}
return curr;
}
private Node search(Comparable temp, Node curr) {
while(curr != null) {
if(temp.compareTo(curr.data) < 0)
curr = curr.left;
else if(temp.compareTo(curr.data) > 0)
curr = curr.right;
else
return curr; // Match
}
return null; // Not found
}
}Can anybody help with this program, I'm getting an error message after I'd complie it.
Here is the error message:
Exception in thread "main" java.lang.AbstractMethodError: Tree.insert(LTree$Node;LTree$Node;)LTree$Node;
at Tree.insert(Tree.java:21)
at Main.main(Main.java:12)
