/* binary search tree with deletion */
# include <stdio.h>
typedef struct btree
{
int data;
struct btree *left,*right;
}btree;
btree *insert(btree *root,int data)
{
btree *x,*y;
y=root;
x=(btree *)malloc(sizeof(btree));
x->data=data;
x->left=x->right=NULL;
if (root==NULL)
root=x;
else
{
for (;;)
{
if (data < y->data)
{
if (y->left==NULL)
{
y->left=x;
break;
}
else
y=y->left;
}
else
if (y->right==NULL)
{
y->right=x;
break;
}
else
y=y->right;
}
}
return(root);
}
btree *searching(btree *root,int val,btree **parent)
{
btree *y;
*parent=NULL;
y=root;
while ((y!=NULL) && (y->data!=val))
{
if (val<y->data)
{
*parent=y;
y=y->left;
}
else
if (val>y->data)
{
*parent=y;
y=y->right;
}
}
return(y);
}
inorder(btree *root)
{
if (root!=NULL)
{
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}
preorder(btree *root)
{
if (root!=NULL)
{
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}
maxmin(btree *root,int *min,int *max)
{
btree *y;
y=root;
while (y->right!=NULL)
y=y->right;
*max=y->data;
y=root;
while (y->left!=NULL)
y=y->left;
*min=y->data;
}
postorder(btree *root)
{
if (root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}
btree *delete(btree *root)
{
int val;
btree *y,*p=NULL,*k,*t;
printf("ENTER A VALUE TO BE DELETED ");
scanf("%d",&val);
y=searching(root,val,&p);
if (y==NULL)
printf("THE ELEMENT IS NOT FOUND \n");
else
{
if ((y->left==NULL) && (y->right==NULL)) /* if y is a leaf node */
{
if (p==NULL) /* if the element to be deleted is the root node */
{
free(y);
root=NULL;
}
else
{
if (p->left==y)
p->left=NULL;
else
p->right=NULL;
}
}
else
if ((y->left==NULL) || (y->right==NULL))
{
if (p==NULL) /* if the element to be deleted is the root node */
{
if (root->left==NULL)
root=root->right;
else
root=root->left;
free(y);
}
else
{
if (p->left==y)
if (y->right==NULL)
p->left=y->left;
else
p->left=y->right;
else
if (y->right==NULL)
p->right=y->left;
else
p->right=y->right;
}
}
else
{
k=y->right;
if (k->left==NULL)
{
y->data=k->data;
if (k->right==NULL)
{
y->right=NULL;
free(k);
}
else
{
y->right=k->right;
free(k);
}
}
else
{
t=k;
while (t->left!=NULL)
{
p=t;
t=t->left;
}
y->data=t->data;
if (t->right==NULL)
p->left=NULL;
else
p->left=t->right;
free(t);
}
}
return(root);
}
int menu()
{
int op;
printf(" \n TREE MENU\n");
printf("1: CREATION \n");
printf("2: INSERTION \n");
printf("3: DELETION \n");
printf("4: MAXMIN \n");
printf("5: INORDER \n");
printf("6: POSTORDER \n");
printf("7: EXIT \n");
printf("ENTER YOUR OPTION \n");
scanf("%d",&op);
return(op);
}
main()
{
btree *root=NULL,*y;
int val=1,op=1;
int max=0,min=0;
while (op!=7)
{
op=menu();
switch(op)
{
case 1: /* CREATION */
printf("ENTER THE VALUES TO CONSTUCT THE BINARY SEARCH TREE AT END
ENTER 0 \n");
while (val!=0)
{
scanf("%d",&val);
if (val!=0)
root=insert(root,val);
}
break;
case 2: /* INSERTION OF ONE VALUE */
printf("ENTER THE VALUE TO BE INSERTED \n");
scanf("%d",&val);
root=insert(root,val);
break;
case 3: /* DELETION OF ONE GIVEN VALUE */
root=delete(root);
break;
case 4: maxmin(root,&min,&max);
printf("THE MAXIMUM IS %d \n ",max);
printf("THE MINIMUM IS %d \n",min);
break;
}
printf("\n\n PREORDER IS .... \n");
preorder(root);
printf("\n\n INORDER IS .... \n");
inorder(root);
printf("\n\n POSTORDER IS .... \n");
postorder(root);
}
}
