BINARY SEARCH TREE:
1.Implement binary search tree (BST) to perform a following operation:
i) BST - create,recursive traversal-Inorder,preorder,postorder
ii)insert and delete
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left,*right;
}BST;
BST *create();
BST *insert(BST *,int);
BST *inorder(BST *);
BST *preorder(BST *);
BST *postorder(BST *);
BST *delete(BST *,int);
static int count=0;
int main ()
{
int ch,x,m;
BST *root=NULL,*ans;
do
{
printf("\n1:create\n2:insert\n3:inorder\n4:preorder\n5:postorder");
printf("\n6:delete");
printf("\n\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:root=create();
break;
case 2:printf("enter the data to be inserted:");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:printf("\nDISPLAY:\n");
inorder(root);
break;
case 4:printf("\nDISPLAY:\n");
preorder(root);
break;
case 5:printf("\nDISPLAY:\n");
postorder(root);
break;
case 6:printf("enter the key u want to be delete:");
scanf("%d",&x);
root=delete(root,x);
break;
default:printf("\nInvalid Case!!!\n");
}
}while(ch!=0);
}
BST *create()
{
BST *root=NULL;
int x,i,n;
printf("enter the nodes to be created:");
scanf("%d",&n);
printf("\nenter the data:");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}
BST *insert(BST *tree,int x)
{
BST *newnode;
if(tree==NULL)
{
newnode=(BST *)malloc(sizeof(BST));
newnode->data=x;
newnode->left=NULL;
newnode->right=NULL;
return(newnode);
}
if(x<tree->data)
{
tree->left=insert(tree->left,x);
return(tree);
}
else if(x>tree->data)
{
tree->right=insert(tree->right,x);
return(tree);
}
else
printf("\nduplicate data");
return(tree);
}
BST *inorder(BST *tree)
{ // left-root-right
if(tree!=NULL)
{
inorder(tree->left);
printf("%d\n",tree->data);
inorder(tree->right);
}
}
BST *preorder(BST *tree)
{ // root-left-right
if(tree!=NULL)
{
printf("%d\n",tree->data);
preorder(tree->left);
preorder(tree->right);
}
}
BST *postorder(BST *tree)
{ // left-right-root
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%d\n",tree->data);
}
}
BST *delete(BST *tree,int x)
{
BST * temp;
if(tree==NULL)
{
printf("\nelement is not found!!!");
return(tree);
}
// If the key to be deleted
// is smaller than the root's
// key, then it lies in left subtree
if(x<tree->data)
{
tree->left=delete(tree->left,x);
return(tree);
}
// If the key to be deleted
// is greater than the root's
// key, then it lies in right subtree
if(x>tree->data)
{
tree->right=delete(tree->right,x);
return(tree);
}
if(tree->left==NULL && tree->right==NULL)
{
temp=tree;
free(temp);
return(NULL);
}
// node with only one child or no child
if(tree->left==NULL)
{
temp=tree;
tree=tree->right;
free(temp);
return(tree);
}
if(tree->right==NULL)
{
temp=tree;
tree=tree->left;
free(temp);
return(tree);
}
temp=tree->right;
while(temp->left!=NULL)
temp=temp->left;
tree->data=temp->data;
tree->right=delete(tree->right,temp->data);
return(tree);
}
OUTPUT:
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:1
enter the nodes to be created:5
enter the data:88
55
6
66
44
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:2
enter the data to be inserted:12
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:3
DISPLAY:
6
12
44
55
66
88
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:4
DISPLAY:
88
55
6
44
12
66
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:5
DISPLAY:
12
44
6
66
55
88
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:6
enter the key u want to be delete:6
1:create
2:insert
3:inorder
4:preorder
5:postorder
6:delete
enter your choice:3
DISPLAY:
12
44
55
66
88
.
Comments
Post a Comment
hey