Untitled
unknown
plain_text
3 months ago
5.2 kB
5
Indexable
#include <iostream> using namespace std; class TreeNode { public: int data; TreeNode* left; TreeNode* right; TreeNode(int val) { data = val; left = right = NULL; } }; // insert a new node into the tree TreeNode* insert(TreeNode* root, int data) { // if the tree is empty, create a new node and return it if (root == NULL) { return new TreeNode(data); } // if data is less than root data, insert it in the left subtree if (data < root->data) { root->left = insert(root->left, data); } // if data is greater than root data, insert it in the right subtree else if (data > root->data) { root->right = insert(root->right, data); } return root; // Return the root of the subtree } // Find the node with the minimum value (used for deletion) TreeNode* findMin(TreeNode* root) { while (root->left != NULL) { root = root->left; } return root; } // delete a node from the tree TreeNode* deleteNode(TreeNode* root, int data) { // if the tree is empty, return NULL if (root == NULL) { return root; } // if the data to be deleted is smaller than root's data, it's in the left subtree if (data < root->data) { root->left = deleteNode(root->left, data); } // If the data to be deleted is greater than root's data, it's in the right subtree else if (data > root->data) { root->right = deleteNode(root->right, data); } // If the data is equal to root's data, we've found the node to delete else { // case 1: Node has no children (leaf node) if (root->left == NULL && root->right == NULL) { delete root; root = NULL; } // case 2: Node has only one child else if (root->left == NULL) { TreeNode* temp = root; root = root->right; delete temp; } else if (root->right == NULL) { TreeNode* temp = root; root = root->left; delete temp; } // case 3: Node has two children else { // the inorder successor TreeNode* temp = findMin(root->right); root->data = temp->data; // replace the root's data with the inorder successor root->right = deleteNode(root->right, temp->data); // Delete the inorder successor } } return root; // Return the updated root } // Inorder traversal to display the BST (left-root-right) void inorder(TreeNode* root) { if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); } } // Search for a node TreeNode* search(TreeNode* root, int key) { // tree is empty or the key is found at the root if (root == NULL || root->data == key) { return root; } // search in the left subtree if (key < root->data) { return search(root->left, key); } return search(root->right, key); } // Function to print the result of the search void searchNode(TreeNode* root, int key) { TreeNode* result = search(root, key); if (result != NULL) { cout << "Node with value " << key << " found in the tree." << endl; } else { cout << "Node with value " << key << " not found in the tree." << endl; } } int main() { TreeNode* root = NULL; int choice, value; while (true) { cout << "*******\nMenu:\n********"; cout << "1. Insert a node\n"; cout << "2. Delete a node\n"; cout << "3. Display tree (Inorder Traversal)\n"; cout << "4. Search for a node\n"; cout << "5. Exit\n"; cout << "Enter your choice: "; cin >> choice; switch (choice) { case 1: // Insert a node cout << "Enter value to insert: "; cin >> value; root = insert(root, value); cout << "Node inserted successfully!\n"; break; case 2: // Delete a node cout << "Enter value to delete: "; cin >> value; root = deleteNode(root, value); cout << "Node deleted successfully if it exists!\n"; break; case 3: // Display cout << "Inorder Traversal of the tree: "; inorder(root); cout << endl; break; case 4: // Search for a node cout << "Enter value to search: "; cin >> value; searchNode(root, value); break; case 5: // Exit the program cout << "Exiting the program...\n"; exit(0); default: cout << "Invalid choice! Please try again.\n"; } } return 0; }
Editor is loading...
Leave a Comment