LANGUAGE IN JAVA. Implement or adapt a BST class (preferred) or a package of dat
ID: 3771328 • Letter: L
Question
LANGUAGE IN JAVA.
Implement or adapt a BST class (preferred) or a package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete. assume that each node in a BST has at least four fields: key, p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers.
Write a method/function that outputs two, x and y, in a given BST, where the key values of x and y differ by a given integer k.
Write a method/function that decides whether a given BST is a sub-BST of another BST. Note that a BST t1 is a sub-BST of t2 iff one of the following holds:
key[root[t1]] = key[root[t2]], and left[t1] and right[t1] are sub-BSTs of left[t2] and right[t2], respectively,
t1 is a sub-BST of left[t2], or
t1 is a sub-BST of right[t2].
Write a method/function that prunes a BST by “deleting” nodes with key values out of a given range [min, max].
Explanation / Answer
this code is sccessfully excuted in net beans Ide. i will send you excuted out put for you
import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
public class BinarySearchTree {
public static Node root;
public BinarySearchTree(){
this.root = null;
}
public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}
else if(current.data > id){
current = current.left;
}
else
{
current = current.right;
}
}
return false;
}/*
Write a method/function that prunes a BST by “deleting” nodes with key values
out of a given range [min, max].*/
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){
//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public void preorder(Node root){
if(root!=null){
System.out.print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
public void postorder(Node root){
if(root!=null){
postorder(root.left);
postorder(root.right);
System.out.print(" " + root.data);
}
}
//checking subtree or not
/* This function returns true if S is a subtree of T, otherwise false */
/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
boolean areIdentical(Node root1, Node root2)
{
/* base cases */
if (root1 == null && root2 == null)
return true;
if (root1 == null || root2 == null)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data & areIdentical(root1->left, root2->left) && areIdentical(root1->right, root2->right) );
}
/* This function returns true if S is a subtree of T, otherwise false */
boolean isSubtree(Node T, Node S)
{
/* base cases */
if (S == null)
return true;
if (T == null)
return false;
/* Check the tree with root as current node */
if (areIdentical(T,S))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) || isSubtree(T->right, S);
}
public static void main(String arg[]){
BinarySearchTree b = new BinarySearchTree();
Scanner reader = new Scanner(System.in); // Reading from System.in
System.out.println("Enter the number of elements did you have:");
int n = reader.nextInt();
int key;// Scans the next token of the input as an int.
for(int i=0;i<n;i++){
key=reader.nextInt();
b.insert(key); }
//tree traversals
System.out.println("Original Tree :in inorder ");
b.display(b.root);
System.out.println("");
System.out.println("Tretraversal searching of post order");
b.postorder(root);
System.out.println("");
System.out.println("Tretraversal searching of preorder order");
b.preorder(root);
System.out.println("");
/*fininng number*/
System.out.println(" Check whether key value or key Node with value exists : " );
key=reader.nextInt();
if(b.find(key)){
System.out.println(" Given key value "+key +"found");
System.out.println("");
}
else{System.out.println(" Given value not found");}
//delinting node
System.out.println(" Ener the number Delete Node : " );
key=reader.nextInt();
b.delete(key); System.out.println("");
System.out.println(" inorder treversal priniting");System.out.println("");
b.display(root);
//calling method/function that decides whether a given BST is a sub-BST of another BST
if (isSubtree(T, S)){
System.out.println("Tree S is subtree of tree T");}
else
{ System.out.println("Tree S is not a subtree of tree T");}
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
out put:
run:
Enter the number of elements did you have:
5
11 5 25 3 4
Original Tree :in inorder
3 4 5 11 25
Tretraversal searching of post order
4 3 5 25 11
Tretraversal searching of preorder order
11 5 3 4 25
Check whether key value or key Node with value exists :
4
Given key value 4 found
Ener the number Delete Node :
4
inorder treversal priniting
3 5 11 25
BUILD SUCCESSFUL (total time: 29 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.