Program for BST without Menu driven approach for
1) Insertion
2) Deletion(3 Cases)
3) Search
4) Smallest
5) Largest
6) Mirror
7) Inorder Traversal
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data; //node will store an integer
struct node *right_child; // right child
struct node *left_child; // left child
};
void search(int i, struct node *n) {
if (n == NULL)
printf("\nValue does not exist in tree!");
else if(n->data == i)
printf("\nValue found!");
else if(i > n->data)
search(i, n->right_child);
else
search(i, n->left_child);
}
void mirror(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;
/* do the subtrees */
//mirror(node->left_child);
//mirror(node->right_child);
/* swap the pointers in this node */
temp = node->left_child;
node->left_child = node->right_child;
node->right_child = temp;
}
}
struct node* smallest(struct node *root)
{
while(root != NULL && root->left_child != NULL)
{
root = root->left_child;
}
//printf("\nSmallest value is %d\n", root->data);
return root;
}
struct node* largest(struct node *root)
{
while (root != NULL && root->right_child != NULL)
{
root = root->right_child;
}
// printf("\nLargest value is %d", root->data);
return root;
}
//function to create a node
struct node* new_node(int x)
{
struct node *p;
p = malloc(sizeof(struct node));
p->data = x;
p->left_child = NULL;
p->right_child = NULL;
return p;
}
struct node* insert(struct node *root, int x)
{
//searching for the place to insert
if(root==NULL)
return new_node(x);
else if(x>root->data) // x is greater. Should be inserted to right
root->right_child = insert(root->right_child, x);
else // x is smaller should be inserted to left
root->left_child = insert(root->left_child,x);
return root;
}
// funnction to delete a node
struct node* delete(struct node *root, int x)
{
//searching for the item to be deleted
if(root==NULL)
return NULL;
if (x>root->data)
root->right_child = delete(root->right_child, x);
else if(x<root->data)
root->left_child = delete(root->left_child, x);
else
{
//No Children
if(root->left_child==NULL && root->right_child==NULL)
{
free(root);
return NULL;
}
//One Child
else if(root->left_child==NULL || root->right_child==NULL)
{
struct node *temp;
if(root->left_child==NULL)
temp = root->right_child;
else
temp = root->left_child;
free(root);
return temp;
}
//Two Children
else
{
struct node *temp = smallest(root->right_child);
root->data = temp->data;
root->right_child = delete(root->right_child, temp->data);
}
}
return root;
}
void inorder(struct node *root)
{
if(root!=NULL) // checking if the root is not null
{
inorder(root->left_child); // visiting left child
printf(" %d ", root->data); // printing data at root
inorder(root->right_child);// visiting right child
}
}
int main()
{
/*
20
/ \
/ \
5 30
/ \ /\
/ \ / \
1 15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
struct node *root,*min,*max;
int x;
//struct node *min;
root = new_node(20);
insert(root,5);
insert(root,1);
insert(root,15);
insert(root,9);
insert(root,7);
insert(root,12);
insert(root,30);
insert(root,25);
insert(root,40);
insert(root, 45);
insert(root, 42);
inorder(root);
printf("\n");
root = delete(root, 1);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
root = delete(root, 40);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 45
/ /
/ /
9 42
/ \
/ \
7 12
*/
root = delete(root, 45);
/*
20
/ \
/ \
5 30
\ / \
\ / \
15 25 42
/
/
9
/ \
/ \
7 12
*/
root = delete(root, 20);
inorder(root);
//postorder(root)
/*
15 25
/ \ / \
/ \ / \
5 30 OR 5 30
\ / \ \ \
\ / \ \ \
12 25 42 15 42
/ /
/ /
7 9
*/ / \
//20 REPLACED WITH //20 REPLACED
/ \ WITH
//INORDER PREDECESSOR 15 //INORDER
7 SUCCESSOR 25
12
printf("\n");
min=smallest(root);
printf("\nSmallest value is %d\n", min->data);
max=largest(root);
printf("\nlargest value is %d\n", max->data);
printf("\n enetr element to search\n");
scanf("%d",&x);
search(x,root);
mirror(root);
inorder(root);
return 0;
}
