/************************ 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 ) < 0)

return search(el, p.left);

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

return search(el, p.right );

else

return p.key;

}

/*

//Iterative search

public T search(T el) {

BSTNode p = root;

while (p != null) {

if (el.equals(p.key))

return p.key;

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

p = p.left;

else p = p.right;

}

return null;

}

*/

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 ) < 0 )

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

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

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

return p;

}

/* iterative version

public void insert(T el) {

BSTNode p = root, prev = null;

while (p != null) { // find a place for inserting new node;

prev = p;

if (el.compareTo(p.key) < 0)

p = p.left;

else p = p.right;

}

if (root == null) // tree is empty;

root = new BSTNode(el);

else if (el.compareTo(prev.key) < 0)

prev.left = new BSTNode(el);

else prev.right = new BSTNode(el);

}

*/

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) < 0) //target is less than 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;

}

//Iterative delete by copying

/*

public void deleteByCopying(T el) {

BSTNode node, p = root, prev = null;

while (p != null && !p.key.equals(el)) { // find the node p

prev = p; // with element el;

if (el.compareTo(p.key) < 0)

p = p.left;

else p = p.right;

}

node = p;

if (p != null && p.key.equals(el)) {

if (node.right == null) // node has no right child;

node = node.left;

else if (node.left == null) // no left child for node;

node = node.right;

else {

BSTNode tmp = node.left; // node has both children;

BSTNode previous = node; // 1.

while (tmp.right != null) { // 2. find the rightmost

previous = tmp; // position in the

tmp = tmp.right; // left subtree of node;

}

node.key = tmp.key; // 3. overwrite the reference

// to the element being deleted;

if (previous == node) // if node's left child's

previous.left = tmp.left; // right subtree is null;

else previous.right = tmp.left; // 4.

}

if (p == root)

root = node;

else if (prev.left == p)

prev.left = node;

else prev.right = node;

}

else if (root != null)

System.out.println("el " + el + " is not in the tree");

else System.out.println("the tree is empty");

}

*/

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(); } }

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

I want you to write two methods inside the BST class.

- one method to print the maximum value in a tree.

- another method to print the minimum value in a tree.