Bst
#include <stdio.h>
#include <stdlib.h>
// Structure definition for a BST node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function prototypes
Node* createNode(int data);
Node* insert(Node* root, int data);
Node* deleteNode(Node* root, int data);
Node* minValueNode(Node* node);
Node* search(Node* root, int data);
void inorderTraversal(Node* root);
void menu();
int main() {
Node* root = NULL;
int choice, data;
while (1) {
menu();
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the data to insert: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("Enter the element to search: ");
scanf("%d", &data);
Node* result = search(root, data);
if (result) {
printf("Element %d found in the tree.\n", data);
} else {
printf("Element %d not found in the tree.\n", data);
}
break;
case 3:
printf("Enter the element to delete: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 4:
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
break;
case 5:
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert a node in the BST
Node* insert(Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Function to find the node with the minimum value
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// Function to delete a node from the BST
Node* deleteNode(Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Node with only one child or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function to search for a node in the BST
Node* search(Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
}
return search(root->right, data);
}
// Function for inorder traversal of the BST
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Function to display the menu
void menu() {
printf("\nMenu:\n");
printf("1. Insert Node\n");
printf("2. Search Node\n");
printf("3. Delete Node\n");
printf("4. Inorder Traversal\n");
printf("5. Exit\n");
}
Comments
Post a Comment