#include<iostream.h>
#include<alloc.h>
#include<conio.h>
struct tree
{
int item;
struct tree *left,*right;
}*h;
void join(tree *p,tree *q)
{
if(p==NULL)
{h=q;return;}
if(p->item<q->item)
{
if(p->right!=NULL)
join(p->right,q);
else
p->right=q;
}
else
{
if(p->left!=NULL)
join(p->left,q);
else
p->left=q;
}
}
void BST()
{
tree *q;
cout<<"Enter Value";
q=(tree*)malloc(sizeof(tree));
cin>>q->item;
q->right=NULL;
q->left=NULL;
join(h,q);
cout<<"Continue y/n";
if(getche()=='y')
BST();
else
return;
}
void print_inorder(struct tree *p)
{
if(p==NULL)return;
print_inorder(p->left);
cout<<endl<<p->item;
print_inorder(p->right);
}
void del(tree *q,int num)
{
tree *parent=NULL;
while(q!=NULL)
{
if(q->item==num)
break;
else if(q->item>num)
{parent=q;q=q->left;}
else
{parent=q;q=q->right;}
}
cout<<"Parent"<<parent->item;
if(q->left==NULL&&q->right==NULL)
{
if(parent->item<num)parent->right=NULL;
else parent->left=NULL;
free(q);
}
else if(q->left!=NULL&&q->right==NULL)
{
if(parent->item<num)parent->right=q->left;
else parent->left=q->left;
free(q);
}
else if(q->left==NULL&&q->right!=NULL)
{
if(parent->item<num)parent->right=q->right;
else parent->left=q->right;
free(q);
}
else
{
tree *temp=NULL,*inorder_successor=NULL;
temp=q;
inorder_successor=q->right;
while(inorder_successor->left!=NULL)
{
temp=inorder_successor;
inorder_successor=inorder_successor->left;
}
if(inorder_successor->right!=NULL)
temp->left=inorder_successor->right;
else if(q!=temp)
temp->left=NULL;
else
temp->right=NULL;
inorder_successor->left=q->left;
inorder_successor->right=q->right;
if(parent->item<inorder_successor->item)parent->right=inorder_successor;
else parent->left=inorder_successor;
}
}
void main()
{
clrscr();
h=NULL;
cout<<"\nEnter Values to Build a B.S.T\n";
BST();
cout<<"\nInorder Traversal of B.S.T";
print_inorder(h);
cout<<"Enter";
int x;
cin>>x;
del(h,x);
print_inorder(h);
getch();
}
#include<alloc.h>
#include<conio.h>
struct tree
{
int item;
struct tree *left,*right;
}*h;
void join(tree *p,tree *q)
{
if(p==NULL)
{h=q;return;}
if(p->item<q->item)
{
if(p->right!=NULL)
join(p->right,q);
else
p->right=q;
}
else
{
if(p->left!=NULL)
join(p->left,q);
else
p->left=q;
}
}
void BST()
{
tree *q;
cout<<"Enter Value";
q=(tree*)malloc(sizeof(tree));
cin>>q->item;
q->right=NULL;
q->left=NULL;
join(h,q);
cout<<"Continue y/n";
if(getche()=='y')
BST();
else
return;
}
void print_inorder(struct tree *p)
{
if(p==NULL)return;
print_inorder(p->left);
cout<<endl<<p->item;
print_inorder(p->right);
}
void del(tree *q,int num)
{
tree *parent=NULL;
while(q!=NULL)
{
if(q->item==num)
break;
else if(q->item>num)
{parent=q;q=q->left;}
else
{parent=q;q=q->right;}
}
cout<<"Parent"<<parent->item;
if(q->left==NULL&&q->right==NULL)
{
if(parent->item<num)parent->right=NULL;
else parent->left=NULL;
free(q);
}
else if(q->left!=NULL&&q->right==NULL)
{
if(parent->item<num)parent->right=q->left;
else parent->left=q->left;
free(q);
}
else if(q->left==NULL&&q->right!=NULL)
{
if(parent->item<num)parent->right=q->right;
else parent->left=q->right;
free(q);
}
else
{
tree *temp=NULL,*inorder_successor=NULL;
temp=q;
inorder_successor=q->right;
while(inorder_successor->left!=NULL)
{
temp=inorder_successor;
inorder_successor=inorder_successor->left;
}
if(inorder_successor->right!=NULL)
temp->left=inorder_successor->right;
else if(q!=temp)
temp->left=NULL;
else
temp->right=NULL;
inorder_successor->left=q->left;
inorder_successor->right=q->right;
if(parent->item<inorder_successor->item)parent->right=inorder_successor;
else parent->left=inorder_successor;
}
}
void main()
{
clrscr();
h=NULL;
cout<<"\nEnter Values to Build a B.S.T\n";
BST();
cout<<"\nInorder Traversal of B.S.T";
print_inorder(h);
cout<<"Enter";
int x;
cin>>x;
del(h,x);
print_inorder(h);
getch();
}
No comments:
Post a Comment