/************************ BST.java **************************

* generic binary search tree

*/

import java.util.*;

public class BST > implements Iterable {

protected BSTNode root = null;

public BST() {

}

public BST(BSTNode p) {

root = p;

}

public void clear() {

root = null;

}

public boolean isEmpty() {

return root == null;

}

protected void visit(BSTNode p) {

System.out.print(p.key + " ");

}

public T search(T el) {

return search(el, root);

}

//recursive search

protected T search(T el, BSTNode p) {

if (p == null)

return null;

else if(el.compareTo(p.key )

return search(el, p.left);

else if(el.compareTo(p.key) > 0)

return search(el, p.right );

else

return p.key;

}

public boolean isInTree(T el) {

return search(el) != null;

}

public void breadthFirst() {

BSTNode p = root;

LLQueue> queue = new LLQueue>();

if (p != null) {

queue.enqueue(p);

while (!queue.isEmpty()) {

p = queue.dequeue();

visit(p);

if (p.left != null)

queue.enqueue(p.left);

if (p.right != null)

queue.enqueue(p.right);

}

}

}

public void preorder() {

preorder(root);

}

protected void preorder(BSTNode p) {

if (p != null) {

visit(p);

preorder(p.left);

preorder(p.right);

}

}

public void inorder() {

inorder(root);

}

protected void inorder(BSTNode p) {

if (p != null) {

inorder(p.left);

visit(p);

inorder(p.right);

}

}

public void postorder() {

postorder(root);

}

protected void postorder(BSTNode p) {

if (p != null) {

postorder(p.left);

postorder(p.right);

visit(p);

}

}

public void insert(T el) {

root = insert(el, root);

}

protected BSTNode insert(T el, BSTNode p) {

if( p == null )

p = new BSTNode(el);

else if(el.compareTo(p.key )

p.left = insert(el, p.left );

else if( el.compareTo(p.key ) > 0 )

p.right = insert(el, p.right );

return p;

}

public void delete (T el) {

root = delete (el, root);

}

//recursive delete by copying

protected BSTNode delete(T el, BSTNode p) {

if (p == null)

return null;

else if (el.compareTo(p.key)

p.left = delete(el, p.left); // delete from left

else if (el.compareTo(p.key) > 0) //target is greater than p.key

p.right = delete(el, p.right);

else { //p.key is the key to be deleted

if (p.left == null || p.right == null) {//if there is one or no child

if (p.left == null) //if no left child

p = p.right;

else //if no right child or no child at all

p = p.left;

}

else { //if p has two children

BSTNode tmp = getMinNode(p.right);//get the successor of the p.key

p.key = tmp.key; //replace p.key with its successor

p.right = delete(tmp.key, p.right); //delete the successor from the right subtree.

}

}

return p;

}

//given a non-empty tree, retuns the node with the minimum key.

private BSTNode getMinNode(BSTNode p) {

BSTNode tmp = p;

while (tmp.left != null)

tmp = tmp.left;

return tmp;

}

public Iterator iterator() {

return new BSTIterator();

}

private class BSTIterator implements Iterator {

BSTNode p = root;

LLQueue> queue;

public BSTIterator() {

queue = new LLQueue>();

queue.enqueue(p);

}

public boolean hasNext() {

return !queue.isEmpty();

}

public T next() {

p = queue.dequeue();

if (p.left != null)

queue.enqueue(p.left);

if (p.right != null)

queue.enqueue(p.right);

return p.key;

}

public void remove() {

// not implemented

}

}

//Generic BSTNode class;

private class BSTNode> {

protected T key;

protected BSTNode left, right;

public BSTNode() {

left = right = null;

}

public BSTNode(T el) {

this(el,null,null);

}

public BSTNode(T el, BSTNode lt, BSTNode rt) {

key = el; left = lt; right = rt;

}

}

}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

import java.util.LinkedList;

public class LLQueue { private LinkedList list = new LinkedList(); public LLQueue() { } public void clear() { list.clear(); } public boolean isEmpty() { return list.isEmpty(); } public T firstEl() { return list.getFirst(); } public T dequeue() { return list.removeFirst(); } public void enqueue(T el) { list.add(el); } public String toString() { return list.toString(); } }

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

2. (a)Define the following additional methods inside the BST class: i). protected boolean isLeaf(BSTNode