c program :
// 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