Please assist on this assignment. In java, implement the BinarySearchTree class.
ID: 3715385 • Letter: P
Question
Please assist on this assignment. In java, implement the BinarySearchTree class. The BinarySearchTree class extends the BinaryTree class which implements the Tree interface. The assignment is to implement all of the abstract methods of the BinaryTree class recursively. Please incude main method in BinarySearchTree class, use recursion in the code, and make sure the code produces the output.
They are:
Insert.
Iterator (non-recursive).
Remove.
Search.
You must also implement an Iterator inner class for the BinarySearchTree class. You must submit a modified BinarySearchTree.java file with your source code.
Do not submit and do not modify the Tree.java or BinaryTree.java files. Please see the codes below for this assignment.
Explanation / Answer
Main.java
-------------------------------------
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
bst.insert(3);
bst.insert(1);
bst.insert(4);
bst.insert(9);
bst.insert(2);
bst.insert(7);
bst.insert(6);
bst.insert(8);
bst.insert(5);
bst.insert(15);
bst.insert(12);
bst.insert(11);
bst.insert(13);
bst.insert(16);
bst.insert(18);
bst.insert(0);
printBST(bst);
bst.remove(9);
System.out.println(" ");
printBST(bst);
}
private static <E extends Comparable<? super E>> void printBST(BinarySearchTree<E> b) {
Iterator<E> it = b.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
-----------------------------------------------------------------------------------------
import java.util.Iterator;
import java.util.Stack;
public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {
public void insert(E data) {
root = insertR(root, data);
}
private Node<E> insertR(Node<E> cur, E data) {
if (cur == null) return new Node<E>(data);
int cmp = data.compareTo(cur.data);
if (cmp < 0) {
cur.left = insertR(cur.left, data);
} else if (cmp > 0) {
cur.right = insertR(cur.right, data);
}
return cur;
}
public void remove(E data) {
root = removeR(root, data);
}
private Node<E> removeR(Node<E> cur, E data) {
if (cur == null) return null;
int cmp = data.compareTo(cur.data);
if (cmp < 0) {
cur.left = removeR(cur.left, data);
return cur;
}
else if (cmp > 0) {
cur.right = removeR(cur.right, data);
return cur;
}
if (cur.left == null || cur.right == null) {
return cur.left == null ? cur.right : cur.left;
}
Node<E> iop = findIOP(cur);
cur.data = iop.data;
cur.left = removeR(cur.left, iop.data);
return cur;
}
private Node<E> findIOP(Node<E> cur) {
Node<E> temp = cur.left;
while (temp.right != null) temp = temp.right;
return temp;
}
public boolean search(E data) {
return searchR(root, data);
}
private boolean searchR(Node<E> cur, E data) {
if (cur == null) return false;
int cmp = data.compareTo(cur.data);
if (cmp < 0) return searchR(cur.left, data);
else if (cmp > 0) return searchR(cur.right, data);
return true;
}
public Iterator<E> iterator() {
final Stack<Node<E>> stack = new Stack<>();
stack.push(root);
return new Iterator<E>() {
private Stack<Node<E>> s = stack;
public boolean hasNext() {
return !s.empty();
}
@Override
public void remove() {
}
public E next() {
Node<E> next = s.pop();
if (next.right != null) s.push(next.right);
if (next.left != null) s.push(next.left);
return next.data;
}
};
}
}
---------------------------------------------------------------------------------------
public abstract class BinaryTree<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 abstract void insert(E data);
public abstract void remove(E data);
public abstract boolean search(E data);
protected Node<E> root;
}