Write a program to implement a binary search tree where the user can perform:
(a) Insert a value
in an existing tree.
(b) Delete a value from the tree
(c) Traverse a Tree: Pre-Order, In-Order, Post-Order.
#include<stdio.h>
#include<stdlib.h>
struct BST
{
struct BST *lchild;
int data;
struct BST *rchild;
};
typedef struct BST node;
node *root=NULL, *temp;
void inorder(node *tree){
if(tree!=NULL){
inorder(tree->lchild);
printf(" %d ",tree->data);
inorder(tree->rchild);
}
}
void preorder(node *tree){
if(tree!=NULL){
printf(" %d ",tree->data);
preorder(tree->lchild);
preorder(tree->rchild);
}
}
void postorder(node *tree){
if(tree!=NULL){
postorder(tree->lchild);
postorder(tree->rchild);
printf(" %d ",tree->data);
}
}
void insert(node *root, node *new_node)
{
if(new_node->data < root->data)
{
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
else if (new_node->data >= root->data)
{
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
void search(int val)
{
node *temp=root;
while (temp != NULL)
{
if (temp->data == val)
break;
if (temp->data > val)
temp = temp->lchild;
else
temp = temp->rchild;
}
if(temp!=NULL)
printf("Element %d is found\n",temp->data);
else
printf("\nElement %d is not found\n",val);
}
struct BST* deleteNode(struct BST* root, int val)
{
if (root == NULL)
return root;
if (val < root->data)
{
root->lchild = deleteNode (root->lchild, val);
}
else if (val > root->data)
{
root->rchild = deleteNode (root->rchild, val);
}
else
{
if (root->lchild == NULL)
{
struct BST *temp = root->rchild;
free (root);
return temp;
}
else if (root->rchild == NULL)
{
struct BST *temp = root->lchild;
free (root);
return temp;
}
struct BST *temp = root->rchild;
while (temp->lchild != NULL)
{
temp = temp->lchild;
}
root->data = temp->data;
root->rchild = deleteNode (root->rchild, temp->data);
}
return root;
}
int main()
{
int ch,val;
node *new_node, *temp;
printf("\nProgram For Binary Search Tree ");
while(1)
{
printf("\n1.Insert an Element\n2.Search\n3.Recursive Traversals\n4.Delete a Node\n5. Exit");
printf("\nEnter your Option : ");
scanf("%d",&ch);
switch(ch) {
case 1: new_node = (node *)malloc(sizeof(node));
new_node->lchild=NULL;
new_node->rchild=NULL;
printf("\nEnter The Element : ");
scanf("%d", &new_node->data);
if(root == NULL)
root = new_node;
else
insert(root,new_node);
break;
case 2: printf("\nEnter Element to be searched : ");
scanf("%d",&val);
search(val);
break;
case 3: if(root == NULL)
printf("\nTree Is Not Created\n");
else{
printf("\nThe Inorder display : ");
inorder(root);
printf("\nThe Preorder display : ");
preorder(root);
printf("\nThe Postorder display : ");
postorder(root);
}
break;
case 4: if(root==NULL)
printf("\nBST is EMPTY\n");
else{
printf("\nEnter the element to be deleted : ");
scanf("%d",&val);
root=deleteNode(root,val);
}
break;
case 5: exit(0);
default:
printf("\nINVALID CHOICE\n");
}
}
}
No comments:
Post a Comment