Complete C program to create a binary search tree and perform all the operation
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *tree;
void create_tree(struct node *);
struct node *insertElement(struct node *, int);
void preorderTraversal(struct node *);
void inorderTraversal(struct node *);
void postorderTraversal(struct node *);
struct node *findSmallestElement(struct node *);
struct node *findLargestElement(struct node *);
struct node *deleteElement(struct node *, int);
struct node *mirrorImage(struct node *);
int totalNodes(struct node *);
int totalExternalNodes(struct node *);
int totalInternalNodes(struct node *);
int Height(struct node *);
struct node *deleteTree(struct node *);
int main()
{
int option, val;
struct node *ptr;
create_tree(tree);
clrscr();
do
{
printf("\n ******MAIN MENU******* \n");
printf("\n 1. Insert Element");
printf("\n 2. Preorder Traversal");
printf("\n 3. Inorder Traversal");
printf("\n 4. Postorder Traversal");
printf("\n 5. Find the smallest element");
printf("\n 6. Find the largest element");
printf("\n 7. Delete an element");
printf("\n 8. Count the total number of nodes");
printf("\n 9. Count the total number of external nodes");
printf("\n 10. Count the total number of internal nodes");
printf("\n 11. Determine the height of the tree");
printf("\n 12. Find the mirror image of the tree");
printf("\n 13. Delete the tree");
printf("\n 14. Exit");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1:
printf("\n Enter the value of the new node : ");
scanf("%d", &val);
tree = insertElement(tree, val);
break;
case 2:
printf("\n The elements of the tree are : \n");
preorderTraversal(tree);
break;
case 3:
printf("\n The elements of the tree are : \n");
inorderTraversal(tree);
break;
case 4:
printf("\n The elements of the tree are : \n");
postorderTraversal(tree);
break;
case 5:
ptr = findSmallestElement(tree);
printf("\n Smallest element is :%d",ptr–>data);
break;
case 6:
ptr = findLargestElement(tree);
printf("\n Largest element is : %d", ptr–>data);
break;
case 7:
printf("\n Enter the element to be deleted : ");
scanf("%d", &val);
tree = deleteElement(tree, val);
break;
case 8:
printf("\n Total no. of nodes = %d", totalNodes(tree));
break;
case 9:
printf("\n Total no. of external nodes = %d",
totalExternalNodes(tree));
break;
case 10:
printf("\n Total no. of internal nodes = %d",
totalInternalNodes(tree));
break;
case 11:
printf("\n The height of the tree = %d",Height(tree));
break;
case 12:
tree = mirrorImage(tree);
break;
case 13:
tree = deleteTree(tree);
break;
}
}while(option!=14);
getch();
return 0;
}
void create_tree(struct node *tree)
{
tree = NULL;
}
struct node *insertElement(struct node *tree, int val)
{
struct node *ptr, *nodeptr, *parentptr;
ptr = (struct node*)malloc(sizeof(struct node));
ptr–>data = val;
ptr–>left = NULL;
ptr–>right = NULL;
if(tree==NULL)
{
tree=ptr;
tree–>left=NULL;
tree–>right=NULL;
}
else
{
parentptr=NULL;
nodeptr=tree;
while(nodeptr!=NULL)
{
parentptr=nodeptr;
if(val<nodeptr–>data)
nodeptr=nodeptr–>left;
else
nodeptr = nodeptr–>right;
}
if(val<parentptr–>data)
parentptr–>left = ptr;
else
parentptr–>right = ptr;
}
return tree;
}
void preorderTraversal(struct node *tree)
{
if(tree != NULL)
{
printf("%d\t", tree–>data);
preorderTraversal(tree–>left);
preorderTraversal(tree–>right);
}
}
void inorderTraversal(struct node *tree)
{
if(tree != NULL)
{
inorderTraversal(tree->left);
printf("%d\t", tree->data);
inorderTraversal(tree->right);
}
}
void postorderTraversal(struct node *tree)
{
if(tree != NULL)
{
postorderTraversal(tree->left);
postorderTraversal(tree->right);
printf("%d\t", tree->data);
}
}
struct node *findSmallestElement(struct node *tree)
{
if( (tree == NULL) || (tree->left == NULL))
return tree;
else
return findSmallestElement(tree ->left);
}
struct node *findLargestElement(struct node *tree)
{
if( (tree == NULL) || (tree->right == NULL))
return tree;
else
return findLargestElement(tree->right);
}
struct node *deleteElement(struct node *tree, int val)
{
struct node *cur, *parent, *suc, *psuc, *ptr;
if(tree–>left==NULL)
{
printf("\n The tree is empty ");
return(tree);
}
parent = tree;
cur = tree–>left;
while(cur!=NULL && val!= cur–>data)
{
parent = cur;
cur = (val<cur–>data)? cur–>left:cur–>right;
}
if(cur == NULL)
{
printf("\n The value to be deleted is not present in the tree");
return(tree);
}
if(cur–>left == NULL)
ptr = cur–>right;
else if(cur–>right == NULL)
ptr = cur–>left;
else
{
// Find the in–order successor and its parent
psuc = cur;
cur = cur–>left;
while(suc–>left!=NULL)
{
psuc = suc;
suc = suc–>left;
}
if(cur==psuc)
{
// Situation 1
suc–>left = cur–>right;
}
else
{
// Situation 2
suc–>left = cur–>left;
psuc–>left = suc–>right;
suc–>right = cur–>right;
}
ptr = suc;
}
// Attach ptr to the parent node
if(parent–>left == cur)
parent–>left=ptr;
else
parent–>right=ptr;
free(cur);
return tree;
}
int totalNodes(struct node *tree)
{
if(tree==NULL)
return 0;
else
return(totalNodes(tree–>left) + totalNodes(tree–>right) + 1);
}
int totalExternalNodes(struct node *tree)
{
if(tree==NULL)
return 0;
else if((tree–>left==NULL) && (tree–>right==NULL))
return 1;
else
return (totalExternalNodes(tree–>left) +
totalExternalNodes(tree–>right));
}
int totalInternalNodes(struct node *tree)
{
if( (tree==NULL) || ((tree–>left==NULL) && (tree–>right==NULL)))
return 0;
else
return (totalInternalNodes(tree–>left)
+ totalInternalNodes(tree–>right) + 1);
}
int Height(struct node *tree)
{
int leftheight, rightheight;
if(tree==NULL)
return 0;
else
{
leftheight = Height(tree–>left);
rightheight = Height(tree–>right);
if(leftheight > rightheight)
return (leftheight + 1);
else
return (rightheight + 1);
}
}
struct node *mirrorImage(struct node *tree)
{
struct node *ptr;
if(tree!=NULL)
{
mirrorImage(tree–>left);
mirrorImage(tree–>right);
ptr=tree–>left;
ptr–>left = ptr–>right;
tree–>right = ptr;
}
}
struct node *deleteTree(struct node *tree)
{
if(tree!=NULL)
{
deleteTree(tree–>left);
deleteTree(tree–>right);
free(tree);
}
}
Output
*******MAIN MENU*******
1. Insert Element
2. Preorder Traversal
3. Inorder Traversal
4. Postorder Traversal
5. Find the smallest element
6. Find the largest element
7. Delete an element
8. Count the total number of nodes
9. Count the total number of external nodes
10. Count the total number of internal nodes
11. Determine the height of the tree
12. Find the mirror image of the tree
13. Delete the tree
14. Exit
Enter your option : 1
Enter the value of the new node : 1
Enter the value of the new node : 2
Enter the value of the new node : 4
Enter your option : 3
2 1 4
Enter your option : 14