Binary Search Tree

//Prog For BST

import java.io.*;
import java.util.*;

class Nodetype
{
int info;
Nodetype left;
Nodetype right;
Nodetype(int i)
{
info=i;
left=null;
right=null;
}
}
class Functions
{
Nodetype tree;
Nodetype maketree(int x)
{
Nodetype node=new Nodetype(x);
return(node);
}/*end maketree*/
void setleft(Nodetype p,int x)
{
if(p==null)
System.out.println("\nInvalid insertion");
else
if(p.left!=null)
System.out.println("\nInvalid insertion");
else
p.left=maketree(x);
}/*end setleft*/
void setright(Nodetype p,int x)
{
if(p==null)
System.out.println("\nInvalid insertion");
else
if(p.right!=null)
System.out.println("\nInvalid insertion");
else
p.right=maketree(x);
}/*end setright*/
void intrav(Nodetype ptree)
{
if(ptree!=null)
{
intrav(ptree.left);
System.out.print(ptree.info+" ");
intrav(ptree.right);
}
}/*end intrav*/
void deletee(int  key)
{
Nodetype p,q,f,s,rp;
p=tree;
q=null;
while(p!=null && p.info!=key)
{
q=p;
p=(key < p.info)? p.left: p.right;
}
if(p==null)
return;
if(p.left==null)
rp=p.right;
else
if(p.right==null)
rp=p.left;
else
{
f=p;
rp=p.right;
s=rp.left;
while(s!=null)
{
f=rp;
rp=s;
s=rp.left;
}
if(f!=p)
{
f.left=rp.right;
rp.right=p.right;
}
rp.left=p.left;
}
if(q==null)
tree=rp;
else
if(p==(q.left))
(q.left)=rp;
else
(q.right)=rp;
System.out.println("\n...........number deleted");
System.out.println("\nInorder : ");
intrav(tree);
return;
}/*end deletee*/

void insert(int key)
{
Nodetype v,p,q;
q=null;
p=tree;
while(p!=null)
{
if(key==p.info)
{
System.out.println("Sorry !....."+key+" is a duplicate\n");
return;
}
q=p;
if(key<p.info)
p=p.left;
else
p=p.right;
}
v=maketree(key);
if(q==null)
tree=v;
else
if(key<q.info)
q.left=v;
else
q.right=v;
System.out.println("\nInorder : ");
intrav(tree);
}/*end insert*/
void search(int key)
{
Nodetype p;
p=tree;
while((p!=null) && (key!=p.info))
p=(key<p.info)? p.left:p.right;
if(p==null)
{
System.out.println("\nNumber not Found!...........");
return;
}
if(key==p.info)
System.out.println("\nNumber Found!...........");
System.out.print("\nInorder : ");
intrav(tree);
}/*end search*/
void create()
{
int num,ch,ans=1;
do
{
System.out.println("\n1.Insert");
System.out.println("\n2.Search");
System.out.println("\n3.Delete");
System.out.print("\nEnter your choice : ");
ch=getNumber();
switch(ch)
{
case 1: System.out.print("\nEnter number to be inserted : ");
num=getNumber();
insert(num);
break;
case 2: System.out.print("\nEnter number to be searched : ");
num=getNumber();
   search(num);
   break;
case 3: System.out.print("\nEnter number to be deleted : ");
num=getNumber();
    deletee(num);
break;
default:System.out.print("\nWrong choice");
}
System.out.print("\nDo you want to continue(1/0) : ");
ans=getNumber();
}
while(ans==1);
}/*end create*/
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getnumber*/
}
class BST
{
public static void main(String main[])
{
Functions f=new Functions();
f.create();
}/*end main*/
}


/*
Sample Input and Output :
1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 10

Inorder : 10
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 50

Inorder : 10 50
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 5

Inorder : 5 10 50
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 2

Enter number to be searched : 100

Number not Found!...........

Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 100

Inorder : 5 10 50 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 2

Enter number to be searched : 100

Number Found!...........

Inorder : 5 10 50 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 40

Inorder : 5 10 40 50 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 30

Inorder : 5 10 30 40 50 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 3

Enter number to be deleted : 50

...........number deleted

Inorder : 5 10 30 40 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 3

Enter number to be deleted : 40

...........number deleted

Inorder : 5 10 30 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 1

Enter number to be inserted : 45

Inorder : 5 10 30 45 100
Do you want to continue(1/0) : 1

1.Insert

2.Search

3.Delete

Enter your choice : 2

Enter number to be searched : 50

Number not Found!...........

Do you want to continue(1/0) : 0
*/