Write each of the following methods inside the BST class /**********************
ID: 3919077 • 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;
}
}
}
(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
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);
}
//methods....
//overloading method to level
public int Level(T el)
{
return Level(el,root);
}
protected int Level(T el, BSTNode<T> p) {
int l;
//finding node
if (p == null)
return -1;//means node doesn't exist
else if(el.compareTo(p.key ) < 0)
{
l=Level(el, p.left);//recursive call
}
else if(el.compareTo(p.key) > 0)
{
l=Level(el, p.right );//recursive call
}
else
return 1;
if(l==-1)
return -1;
return 1+l;
}
//overloading method of isDecisionTree
public boolean isDecisionTree(T el)
{
return isDecisionTree(el,root);
}
protected boolean isDecisionTree(T el, BSTNode<T> p) {
//finding node
if (p == null)
return false;//means node doesn't exist
else if(el.compareTo(p.key ) < 0)
return isDecisionTree(el, p.left);//recursive call
else if(el.compareTo(p.key) > 0)
return isDecisionTree(el, p.right );//recursive call
else//if node is found
{
//if both are null or both not null
if((p.left==null && p.right==null )||(p.left!=null && p.right!=null ))
return true;
else//if not
return false;
}
}
//overloading public method of getPathLength
public int getPathLength(T el)
{
return getPathLength(el,root);
}
protected int getPathLength(T el, BSTNode<T> p) {
int l;
//finding node
if (p == null)
return -1;//means node doesn't exist
else if(el.compareTo(p.key ) < 0)
l=getPathLength(el, p.left);//recursive call
else if(el.compareTo(p.key) > 0)
l=getPathLength(el, p.right );//recursive call
else
return 0;
if(l==-1)return -1;
return 1+l;//finding length
}
//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;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.