//binary search tree
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left,*right;
};
//create node
struct node *newnode(int item){
struct node *temp=malloc(sizeof(struct node));
if(temp==NULL)
return temp;
else{
temp->data=item;
temp->left=NULL;
temp->right=NULL;
}
return temp;
}
//a)INSERTION
struct node *insert(struct node *root,int key){
//return a new node if the tree is empty
if(root==NULL)
return newnode(key);
if(key<root->data)
root->left=insert(root->left,key);
else
root->right=insert(root->right,key);
return root;
}
//b)DELETION
struct node *minvalue(struct node *node)/*TO FIND THE INORDER SUCCESSOR*/
{
struct node *current=node;
//FIND THE LEFT MOST LEAF
while(current!=NULL && current->left!=NULL)
current=current->left;
return current;
}
struct node *deletenode(struct node *root,int key)/*DELETING NODE*/
{
//Return if the tree is empty
if(root==NULL)
return root;
//Find the node to be deleted
if(key<root->data)
root->left=deletenode(root->left,key);
else if(key>root->data)
root->right=deletenode(root->right,key);
else{
//If the node is with only one child or no child here the case is key==root->data
if(root->left==NULL){
struct node *temp=root->right;
free(root);
return temp;
}
else if(root->right==NULL){
struct node *temp=root->left;
free(root);
return temp;
}
//If the node has two children
struct node *temp=minvalue(root->right);
//place the inorder successor in position of the node to be deleted
root->data=temp->data;
//Delete the inorder successor
root->right=deletenode(root->right,temp->data);
}
return root;
}
//c)SEARCH A NODE
struct node *search(struct node *root,int key){
//Base cases:root is null or key is present at root
if(root==NULL||root->data==key)
return root;
//Key is greater than root's key
if(root->data<key)
return search(root->right,key);
//Key is smaller than root's key
else
return search(root->left,key);
}
//d)COUNT LEAF AND NON_LEAF NODES
//d.a)leaf nodes
int countleafnode(struct node *root){
if(root==NULL)
return 0;
if(root->left==NULL && root->right==NULL)
return 1;
else
return countleafnode(root->left)+countleafnode(root->right);
}
//d.b)non-leaf nodes
int countnonleafnode(struct node *root){
if(root==NULL ||(root->left==NULL && root->right==NULL))
return 0;
else
return 1+countnonleafnode(root->left)+countnonleafnode(root->right);//here we add 1 because root is also a non-leaf node
}
//5)HEIGHT
int height(struct node *root){
/*if(node==NULL)
return 0;
else{
int leftHeight=height(node->left);
int rightHeight=height(node->right);
return max(leftHeight,rightHeight)+1;
}*/
/*int h = 0;
if(root != NULL)
{
int lHeight = height(root->left);
int rHeight = height(root->right);
int maxHeight = max(lHeight,rHeight);
h = maxHeight + 1;
}
return h; */
int left,right;
if(root == NULL)
return -1;
else
{
left=height(root->left);
right=height(root->right);
if (left > right)
return left+1;
else
return right+1;
}
}
void inorder(struct node *root){
if(root!=NULL)
{
inorder(root->left);
printf("%3d",root->data);
inorder(root->right);
}
}
void preorder(struct node *root){
if(root!=NULL)
{
printf("%3d",root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node *root){
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%3d",root->data);
}
}
//CALCULATE TOTAL NODES
int totalnodes(struct node *tree){
if(tree==NULL)
return 0;
else
return (totalnodes(tree->left)+totalnodes(tree->right)+1);//1 is added for root node
}
//Invert A BST
struct node *mirrorImage(struct node *tree){
struct node *ptr;
if(tree!=NULL){
mirrorImage(tree->left);
mirrorImage(tree->right);
ptr=tree->left;
tree->left=tree->right;
tree->right=ptr;
}
return tree;
}
//delete tree
struct node *deleteTree(struct node *tree){
if(tree!=NULL){
deleteTree(tree->left);
deleteTree(tree->right);
//printf("\n Deleting node: %d", tree->data);
free(tree);
}
}
//Find The smallest value
struct node *findsmallestelement(struct node *tree){
if(tree==NULL||tree->left==NULL)
return tree;
else
return findsmallestelement(tree->left);
}
//Find The Largestest value
struct node *findlargestelement(struct node *tree){
if(tree==NULL||tree->right==NULL)
return tree;
else
return findlargestelement(tree->right);
}
int main(){
int choice,val;
struct node *root=NULL,*temp;
do{
printf("\nBST PROGRAMS FOR EXAM\n");
printf("\n1.INSERTION\n2.DELETION\n3.SEARCHING\n4.COUNT LEAF NODES OR EXTERNAL NODES\n5.COUNT NON-LEAF NODES OR INTERNAL NODES\n6.CALCULATE HEIGHT\n7.TRAVERSALS\n8.DELETE TREE\n9.COUNT TOTAL NODES\n10.MIRROR IMAGE\n11.FIND SMALLEST NODE\n12.FIND LARGEST\n13.EXIT");
printf("\nENTER YOUR CHOICE:");
scanf("%d",&choice);
switch(choice){
case 1:
printf("\nENTER DATA FOR INSERTION:");
scanf("%d",&val);
root=insert(root,val);
printf("\nNODE INSERTED");
break;
case 2: printf("\nENTER DATA FOR DELETION:");
scanf("%d",&val);
root=deletenode(root,val);
printf("\nNODE DELETED");
break;
case 3:
printf("\nENTER DATA FOR SEARCHING:");
scanf("%d",&val);
temp=search(root,val);
if(temp==NULL)
printf("\nNODE IS NOT PRESENT");
else
printf("\nNODE IS PRESENT");
break;
case 4:printf("\nNUMBER OF LEAF NODES ARE:%d",countleafnode(root));
break;
case 5:printf("\nNUMBER OF NONLEAF NODES ARE:%d",countnonleafnode(root));
break;
case 6:printf("\nHEIGHT OF THE TREE IS:%d",height(root));
int maxh=totalnodes(root)-1;
printf("\nMAX HEIGHT IS %d ",maxh);
break;
case 7:printf("\nINORDER TRAVERSAL:\n");
inorder(root);
printf("\nPREORDER TRAVERSAL:\n");
preorder(root);
printf("\nPOStORDER TRAVERSAL:\n");
postorder(root);
break;
case 8:root=deleteTree(root);
printf("\nAFTER DELETING THE TREE:");
printf("\nINORDER TRAVERSAL:\n");
inorder(root);
break;
case 9:printf("\nTOTAL NUMBER OF NODES=%d",totalnodes(root));
break;
case 10: root=mirrorImage(root);
printf("\nAFTER INVERTING THE TREE:");
printf("\nINORDER TRAVERSAL:\n");
inorder(root);
break;
case 11:temp=findsmallestelement(root);
printf("\nSMALLEST ELEMENT IS:%d",temp->data);
break;
case 12:temp=findlargestelement(root);
printf("\nLARGEST ELEMENT IS:%d",temp->data);
break;
case 13:exit(0);
break;
default:printf("\nENTER VALID CHOICE");
}
}while(choice!=13);
return 0;
}
Comments