Write each of the following methods inside the BST class /**********************
ID: 3919310 • Letter: W
Question
Write each of the following methods inside the BST class
/************************ BST.java **************************
* generic binary search tree
*/
import java.util.*;
public class BST<T extends Comparable<T>> implements Iterable<T> {
protected BSTNode<T> root = null;
public BST() {
}
public BST(BSTNode<T> p) {
root = p;
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
protected void visit(BSTNode<T> p) {
System.out.print(p.key + " ");
}
public T search(T el) {
return search(el, root);
}
//recursive search
protected T search(T el, BSTNode<T> 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<T> 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<T> p = root;
LLQueue<BSTNode<T>> queue = new LLQueue<BSTNode<T>>();
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<T> p) {
if (p != null) {
visit(p);
preorder(p.left);
preorder(p.right);
}
}
public void inorder() {
inorder(root);
}
protected void inorder(BSTNode<T> p) {
if (p != null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(BSTNode<T> p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
visit(p);
}
}
public void insert(T el) {
root = insert(el, root);
}
protected BSTNode<T> insert(T el, BSTNode<T> p) {
if( p == null )
p = new BSTNode<T>(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<T> 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<T>(el);
else if (el.compareTo(prev.key) < 0)
prev.left = new BSTNode<T>(el);
else prev.right = new BSTNode<T>(el);
}
*/
public void delete (T el) {
root = delete (el, root);
}
//recursive delete by copying
protected BSTNode<T> delete(T el, BSTNode<T> 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<T> 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<T> getMinNode(BSTNode<T> p) {
BSTNode<T> tmp = p;
while (tmp.left != null)
tmp = tmp.left;
return tmp;
}
//Iterative delete by copying
/*
public void deleteByCopying(T el) {
BSTNode<T> 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<T> tmp = node.left; // node has both children;
BSTNode<T> 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<T> iterator() {
return new BSTIterator();
}
private class BSTIterator implements Iterator<T> {
BSTNode<T> p = root;
LLQueue<BSTNode<T>> queue;
public BSTIterator() {
queue = new LLQueue<BSTNode<T>>();
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<T extends Comparable<T>> {
protected T key;
protected BSTNode<T> left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(T el) {
this(el,null,null);
}
public BSTNode(T el, BSTNode<T> lt, BSTNode<T> rt) {
key = el; left = lt; right = rt;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
test your methods in TestIntegerBST class
TestIntegerBST class :
import java.util.Scanner;
import java.util.*;
public class TestIntegerBST {
public static void main (String[] args){
BST<Integer> tree = new BST<Integer>();
int option, target;
Scanner reader = new Scanner(System.in);
do {
System.out.println(" ***************************");
System.out.println("* Testing Binary Search Tree *");
System.out.println("*************************** ");
System.out.println("1. Insert an element");
System.out.println("2. Search for an element");
System.out.println("3. Delete an element");
System.out.println("4. Print in Breadth-First-Order");
System.out.println("5. Print in Pre-Order");
System.out.println("6. Print in In-Order");
System.out.println("7. Print in Post-Order");
System.out.println("8. Print sum of the elements");
System.out.println("9. Quit");
System.out.print(" Select an Option [1...9] : ");
option = reader.nextInt();
switch (option) {
case 1 : System.out.print("Enter the element to insert: ");
tree.insert(reader.nextInt());
break;
case 2 : System.out.print("Enter the element to search for: ");
target = reader.nextInt();
Integer result = tree.search(target);
if (result != null)
System.out.println("Element, "+result+ " was found in the tree");
else
System.out.println("Sorry, the element was not found");
break;
case 3 : System.out.print("Enter the element delete: ");
tree.delete(reader.nextInt());
break;
case 4 : tree.breadthFirst();
break;
case 5 : tree.preorder();
break;
case 6 : tree.inorder();
break;
case 7 : tree.postorder();
break;
case 8 : System.out.print("Sum of the elements in the tree is: "+sum(tree));
break;
} //end of switch
} while (option != 9);
} //end of main
public static int sum(BST<Integer> tree) {
int sum = 0;
for (int n : tree)
sum += n;
return sum;
}
}
(i)protected int Level (T el, BSTNode T> p) A recursive method that returns the level of the node containing el or -1 if el does not exist in the tree. Example: Level of node 12 in the following tree is 3. (ii) protected boolean isDecision Tree(BSTNode p) A recursive method that returns true if the tree referenced by p is a decision tree. Hint: A decision tree is one in which each node has its children as either both empty or both non-empty. (iv) protected int getPathLength(T el, BSTNode A recursive method that returns the length of the path from the root of the tree referenced by p to the node containing el. Example: path length for node 12 in the following tree is 2. Note: For each of the recursive methods above, you need to have a public overloaded version of the method (without parameter p) that calls the recursive version with root as the initial value of p. It is this public method you will call in the TestintegerBST class. 1 0 2 4 1 2 20Explanation / Answer
Here are the methods that you asked for.. please let me know in case of any concerns.. please upvote if answer helped you. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.