BST Class
Implement the BST class which includes following functions -
1. search
Given an element, find if that is present in BSt or not. Return true or false.
2. insert -
Given an element, insert that element in the BST at the correct position. Assume unique elements will be given.
3. delete -
Given an element, remove that element from the BST. If the element which is to be deleted has both children, replace that with the minimum element from right sub-tree.
4. printTree (recursive) -
Print the BST in ithe following format -
For printing a node with data N, you need to follow the exact format -
wherer, N is data of any node present in the binary tree. x and y are the values of left and right child of node N. Print the children only if it is not null.
There is no space in between.
You need to print all nodes in the recursive format in different lines.
Note : main function is given for your reference which we are using internally to test the class.
Compilar Code
/***************
* BinaryTreeNode class already given -
*
class BinaryTreeNode<T> {
T data;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
public BinaryTreeNode(T data) {
this.data = data;
}
}
***************/
/**************
* Main function that we are using internally
*
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int choice, input;
while(true) {
choice = s.nextInt();
switch(choice) {
case 1 :
input = s.nextInt();
bst.insertData(input);
break;
case 2 :
input = s.nextInt();
bst.deleteData(input);
break;
case 3 :
input = s.nextInt();
System.out.println(bst.search(input));
break;
default :
bst.printTree();
return;
}
}
*******************/
Driver Code
public class BinarySearchTree {
private BinaryTreeNode<Integer> root;
private int size;
private static boolean isPresentHelper(BinaryTreeNode<Integer> root,int x)
{
if(root == null)
{
return false;
}
if(root.data == x)
{
return true;
}
if(x<root.data)
{
return isPresentHelper(root.left,x);
}
else
{
return isPresentHelper(root.right,x);
}
}
public boolean search(int x)
{
return isPresentHelper(root,x);
}
private BinaryTreeNode<Integer> insertDataHelper(BinaryTreeNode<Integer> node,int input)
{
if(node == null)
{
BinaryTreeNode<Integer> newRoot = new BinaryTreeNode<>(input);
return newRoot;
}
if(input<node.data)
{
node.left = insertDataHelper(node.left,input);
}
if(input>node.data)
{
node.right = insertDataHelper(node.right,input);
}
return node;
}
//Now we will make a function to ensert data into the bst
public void insertData(int input)
{
root = insertDataHelper(root,input);
}
private void printTreeHelper(BinaryTreeNode<Integer> node)
{
if(node == null)
{
return;
}
System.out.print(node.data+":");
if(node.left != null)
{
System.out.print("L:"+node.left.data+",");
}
if(node.right != null)
{
System.out.print("R:"+node.right.data);
}
System.out.println();
printTreeHelper(node.left);
printTreeHelper(node.right);
}
//Now we will make a function to printTree
public void printTree()
{
printTreeHelper(root);
}
//Now this functio will use to find minimum element fron right side
private int minimum(BinaryTreeNode<Integer> root)
{
if(root==null)
{
return Integer.MAX_VALUE;
}
int leftMin = minimum(root.left);
int rightMin = minimum(root.right);
return Math.min(root.data, Math.min(leftMin,rightMin));
}
//Now we will make a function to delete data from the node
private BinaryTreeNode<Integer> deleteDataHelper(BinaryTreeNode<Integer> root,int x)
{
if(root == null)
{
return null;
}
if(root.data < x)
{
root.right = deleteDataHelper(root.right,x);
return root;
}
if(root.data>x)
{
root.left = deleteDataHelper(root.left,x);
return root;
}
if(root.left==null && root.right==null)
{
return null;
}
if(root.left != null && root.right==null)
{
return root.left;
}
if(root.right != null && root.left==null)
{
return root.right;
}
//now if booth children is prestent
int rightMin = minimum(root.right);
root.data = rightMin;
root.right = deleteDataHelper(root.right,rightMin);
return root;
}
public void deleteData(int input)
{
root = deleteDataHelper(root,input);
}
}
About Ninja
Soratemplates is a blogger resources site is a provider of high quality blogger template with premium looking layout and robust design
Like Our Facebook Fan Page
Subscribe For Free Email Updates
No comments:
Post a Comment