/* DELETION OF BINARY SEARCH TREE */
import java.io.*;
class Node
{
int data;
Node lef,rig;
Node(int d)
{
data=d;
lef=null;
rig=null;
}
void display()
{
System.out.println(data);
}
}
class Binary
{
DataInputStream nn=new
DataInputStream(System.in);
Node root;
Binary()
{
root=null;
}
void insert()
{
try
{
System.out.print("Enter
the element: ");
int
d=Integer.parseInt(nn.readLine());
Node n=new Node(d);
Node curr=root,par=root;
if(root==null)
root=n;
else
{
while(1==1)
{
if(curr.data<n.data)
{
par=curr;
curr=curr.rig;
if(curr==null)
{
par.rig=n;
break;
}
}
else
{
par=curr;
curr=curr.lef;
if(curr==null)
{
par.lef=n;
break;
}
}
}}}
catch(Exception e)
{}
}
void delete()
{
try
{
System.out.print("enter
the element to delete : ");
int p=Integer.parseInt(nn.readLine());
Node curr=root;
Node par=null;
int flag=0,isleft=0;
while(curr.data!=p)
{
par=curr;
if(p<curr.data)
{
curr=curr.lef;
isleft=1;
}
else
{
curr=curr.rig;
isleft=0;
}
if(curr==null)
{
flag=1;
break;
}}
if(flag==1)
System.out.print("not
found");
else
{
if(curr.lef==null&&curr.rig==null)
{
if(curr==root)
root=null;
else if(isleft==1)
par.lef=null;
else
par.rig=null;
}
if(curr.lef==null&&curr.rig!=null)
{
if(curr==root)
curr=null;
else if(isleft==0)
par.rig=curr.rig;
else
par.lef=curr.rig;
}
if(curr.lef!=null&&curr.rig==null)
{
if(curr==root)
curr=null;
else if(isleft==0)
par.rig=curr.lef;
else
par.lef=curr.lef;
}
if(curr.rig!=null&&curr.lef!=null)
{
Node delnode=curr;
Node parsucc=delnode;
Node succ=delnode;
Node curr1=delnode.rig;
while(curr1!=null)
{
parsucc=succ;
succ=curr1;
curr1=curr1.lef;
}
if(succ!=delnode.rig)
{
parsucc.lef=succ.rig;
succ.rig=delnode.rig;
}
if(curr==root)
curr=succ;
else if(isleft==1)
par.lef=succ;
else
par.rig=succ;
succ.lef=curr.lef;
}}
}
catch(Exception e)
{}
}
void traverse()
{
Node curr=root;
io(curr);
}
void io(Node curr)
{
if(curr!=null)
{
io(curr.lef);
curr.display();
io(curr.rig);
}}}
class Bt
{
public static void
main(String args[])throws Exception
{
int p;
Binary b=new Binary();
do
{
DataInputStream get=new DataInputStream(System.in);
System.out.println("\n1.insert\n2.delete\n3.inorder
trversal");
System.out.print("Enter
the choice: ");
int
ch=Integer.parseInt(get.readLine());
p=ch;
switch(ch)
{
case 1 : b.insert();break;
case 2 : b.delete();break;
case 3 : b.traverse();break;
}
}while(p<4);
}}
OUTPUT
1.insert
2.delete
3.inorder traversal
Enter the choice: 1
Enter the element: 2
1.insert
2.delete
3.inorder traversal
Enter the choice: 1
Enter the element: 3
1.insert
2.delete
3.inorder traversal
Enter the choice: 1
Enter the element: 1
1.insert
2.delete
3.inorder traversal
Enter the choice: 3
1
2
3
1.insert
2.delete
3.inorder traversal
Enter the choice: 2
enter the element to delete :
1
1.insert
2.delete
3.inorder traversal
Enter the choice: 3
2
3
1.insert
2.delete
3.inorder traversal
Enter the choice: 2
enter the element to delete :
5
not found
1.insert
2.delete
3.inorder traversal
Enter the choice: 4
0 comments:
Post a Comment