Binary search tree
program:
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d -> ", root->key);
inorder(root->right);
}
}
void preorder(struct node *root) {
if (root != NULL) {
printf("%d -> ", root->key);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d -> ", root->key);
}
}
struct node *insert(struct node *node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
struct node *minValueNode(struct node *node) {
struct node *current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node *deleteNode(struct node *root, int key) {
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
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;
}
struct node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
void freeMemory(struct node *root) {
if (root == NULL)
return;
freeMemory(root->left);
freeMemory(root->right);
free(root);
}
int main() {
int choice, value;
struct node *root = NULL;
do {
printf("\n1. Insertion\n2. Deletion\n3. inorder\n4. preorder\n5. postorder\n6. Exit");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the value to be insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Enter the value to be deleted: ");
scanf("%d", &value);
root = deleteNode(root, value);
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
freeMemory(root);
break;
default:
printf("\nWrong selection!!! Try again!!!");
}
} while (choice != 6);
return 0;
}
output :
50
/ \
20 80
/ \ / \
5 30 65 90
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 50
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 20
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 80
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 5
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 30
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 65
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 1
Enter the value to be insert: 90
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 3
5 -> 20 -> 30 -> 50 -> 65 -> 80 -> 90 ->
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 4
50 -> 20 -> 5 -> 30 -> 80 -> 65 -> 90 ->
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 5
5 -> 30 -> 20 -> 65 -> 90 -> 80 -> 50 ->
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 2
Enter the value to be deleted: 50
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 4
65 -> 20 -> 5 -> 30 -> 80 -> 90 ->
1. Insertion
2. Deletion
3. inorder
4. preorder
5. postorder
6. Exit
Enter your choice: 6
Comments
Post a Comment