this is the bst class /************************ BST.java ***********************
ID: 3704001 • Letter: T
Question
this is the bst class
/************************ 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;
}
}
}
2 Write each of the following methods inside the BST class 11 Marks 1 eachl not element does A recursive method that returns the level of the node containing el or -1 i exist in the tree Exomple: Level of node 12 is 3 A recursive method that retuarns true if the tree referenced by p is balanced (n) protected boolean isBalanced (BSTodeT p) betweern Hint: A balanced tree is oither empty or one in which for each node,the difference bet the heights of left and right sub-trees is less than 2 and both lett and rightsub-es balanced (iv) public void printPath(T el, BST Node«Typ) A recursive method that prints all the nodes in the path from the root of the tree referenced by ? to the node containing el. Hint: For the tree shown in the folowing figure, the output should be: t0, 15, 12 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 2 20Explanation / Answer
/************************ 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;
Queue<BSTNode<T>> queue = new Queue<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;
}
public int Level(T el) {
return level(el, root,1);
}
public int Level(T el,BSTNode<T> p) {
return level(el, root,1);
}
protected int level(T el, BSTNode<T> p ,int level)
{
if (p == null)
return -1;
if (p.key.compareTo(el)==0)
return level;
int downlevel = level(el, p.left, level + 1);
if (downlevel != -1)
return downlevel;
downlevel = level(el ,p.right, level + 1);
return downlevel;
}
public boolean isBalanced() {
return isBalanced(root);
}
protected boolean isBalanced(BSTNode<T> p )
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
if (p == null)
return true;
/* Get the height of left and right sub trees */
lh = height(p.left);
rh = height(p.right);
if (Math.abs(lh - rh) <= 1
&& isBalanced(p.left)
&& isBalanced(p.right))
return true;
return false;
}
int height(BSTNode<T> p)
{
if (p == null)
return 0;
return 1 + Math.max(height(p.left), height(p.right));
}
/*
* 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;
Queue<BSTNode<T>> queue;
public BSTIterator() {
queue = new Queue<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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.