Java Code For Binary Search Tree
Posted by
Unknown
import java.util.*;
class Node
{
Node left,right;
int data;
}
class BST
{
Node root;
BST()
{
root=null;
}
void insert(int x)
{
Node newrec=new Node();
newrec.data=x;
newrec.left=newrec.right=null;
if(root==null)
{
root=newrec;
}
else
{
Node a,b=null;
a=root;
while(a!=null)
{
b=a;
if(a.data<=x)
a=a.left;
else a=a.right;
}
if(b.data<=x)
b.left=newrec;
else b.right=newrec;
}
}
void delete(int x)
{
if(root==null)
System.out.println("Tree is Empty");
else
{
Node a,b=null,c;
a=root;
while(a!=null&&a.data!=x)
{
b=a;
if(a.data<=x)
a=a.left;
else a=a.right;
}
if(a==null)
System.out.println("Element is not present");
else
{
if(a.left==null&&a.right!=null)
{
if(a==root)
root=a.right;
else
{
if(b.left==a)
b.left=a.right;
else b.right=a.right;
}
}
else if(a.left!=null&&a.right==null)
{
if(a==root)
root=a.left;
else
{
if(b.left==a)
b.left=a.left;
else b.right=a.left;
}
}
else if(a.left==null&&a.right==null)
{
if(a==root)
root=null;
else
{
if(b.left==a)
b.left=null;
else b.right=null;
}
}
else
{
if(a==root)
{
root=a.right;
root.left=a.left;
}
else
{
if(b.left==a)
{
c=a.right;
while(c.left!=null)
c=c.left;
c.left=a.left;
b.left=a.right;
}
else
{
c=a.right;
while(c.left!=null)
c=c.left;
c.left=a.left;
b.right=a.right;
}
}
}
}
}
}
void display(int x)
{
switch(x)
{
case 1:inorder(root);
break;
case 2:preorder(root);
break;
case 3:postorder(root);
break;
default:System.out.println("Wrong Choice:");
}
System.out.println();
}
void search(int x)
{
Node a,b=null;
a=root;
while(a!=null&&a.data!=x)
{
b=a;
if(a.data<=x)
a=a.left;
else a=a.right;
}
if(a==null)
System.out.println(x+" is not present");
else System.out.println(x+" is present");
}
void postorder(Node x)
{
if(x!=null)
{
postorder(x.left);
postorder(x.right);
System.out.print(x.data+" ");
}
}
void preorder(Node x)
{
if(x!=null)
{
System.out.print(x.data+" ");
preorder(x.left);
preorder(x.right);
}
}
void inorder(Node x)
{
if(x!=null)
{
preorder(x.left);
System.out.print(x.data+" ");
preorder(x.right);
}
}
}
class BSTExp
{
public static void main(String args[])
{
Scanner src=new Scanner(System.in);
int ch,x;
BST b=new BST();
do
{
System.out.println("Enter choice 1:Insert 2:Delete 3:Search 4:Display 5:Exit");
ch=src.nextInt();
switch(ch)
{
case 1:System.out.println("Enter element to be inserted");
x=src.nextInt();
b.insert(x);
break;
case 2: System.out.println("Enter element to be Deleted");
x=src.nextInt();
b.delete(x);
break;
case 3:System.out.println("Enter element to be Searched");
x=src.nextInt();
b.search(x);
break;
case 4:System.out.println("Enter choice 1:Inorder 2:Preorder 3:Postorder");
x=src.nextInt();
b.display(x);
break;
case 5:System.out.println("THANK YOU");
break;
default: System.out.println("WRONG CHOICE");
}
}while(ch!=5);
}
}
