Untitled
unknown
plain_text
a year ago
3.9 kB
3
Indexable
Never
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* left; struct Node* right; }; // Function to create a new node struct Node* createNode(int key) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = key; newNode->left = newNode->right = NULL; return newNode; } // Function to insert a key into the BST struct Node* insert(struct Node* root, int key) { if (root == NULL) { return createNode(key); } if (key < root->data) { root->left = insert(root->left, key); } else if (key > root->data) { root->right = insert(root->right, key); } return root; } // Function to find the minimum key in the BST struct Node* findMinimum(struct Node* root) { if (root == NULL) { return NULL; } while (root->left != NULL) { root = root->left; } return root; } // Function to find the maximum key in the BST struct Node* findMaximum(struct Node* root) { if (root == NULL) { return NULL; } while (root->right != NULL) { root = root->right; } return root; } // Function to find the second minimum key in the BST struct Node* findSecondMinimum(struct Node* root) { if (root == NULL || (root->left == NULL && root->right == NULL)) { return NULL; } if (root->left != NULL) { return findMinimum(root->left); } return findMinimum(root->right); } // Function to delete a node with zero children struct Node* deleteNode(struct Node* root, int key) { if (root == NULL) { return root; } if (key < root->data) { root->left = deleteNode(root->left, key); } else if (key > root->data) { 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 = findMinimum(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; } // Function to perform an in-order traversal void inorder(struct Node* root) { if (root == NULL) { return; } inorder(root->left); printf("%d ", root->data); inorder(root->right); } // Function to perform a pre-order traversal void preorder(struct Node* root) { if (root == NULL) { return; } printf("%d ", root->data); preorder(root->left); preorder(root->right); } // Function to perform a post-order traversal void postorder(struct Node* root) { if (root == NULL) { return; } postorder(root->left); postorder(root->right); printf("%d ", root->data); } int main() { struct Node* root = NULL; // Inserting elements into the BST root = insert(root, 6); root = insert(root, 2); root = insert(root, 9); root = insert(root, 4); root = insert(root, 13); root = insert(root, 7); root = insert(root, 1); printf("In-order traversal: "); inorder(root); printf("\n"); printf("Pre-order traversal: "); preorder(root); printf("\n"); printf("Post-order traversal: "); postorder(root); printf("\n"); struct Node* minNode = findMinimum(root); printf("Minimum: %d\n", minNode->data); struct Node* maxNode = findMaximum(root); printf("Maximum: %d\n", maxNode->data); struct Node* secondMinNode = findSecondMinimum(root); printf("Second Minimum: %d\n", secondMinNode->data); // Deleting nodes root = deleteNode(root, 1); // Delete a node with 0 children root = deleteNode(root, 9); // Delete a node with 1 child printf("In-order traversal after deletion: "); inorder(root); printf("\n"); return 0; }