fueanta

BST Implementation in C++

Nov 25th, 2016
177
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // AUTHOR : Fueanta
  2. // Implementation of BST in CPP
  3. // First of its kind. Updated later
  4. // Contact EMAIL : fueanta@gmail.com [let me know if you find any bug]
  5.  
  6. #include <iostream>
  7. #include <stdlib.h>
  8. using namespace std;
  9.  
  10. struct TreeNode {
  11.     int key;
  12.     TreeNode *left, *right;
  13. } *root;
  14.  
  15. bool deletion;
  16.  
  17. TreeNode* MakeNode(int);
  18. void CreateTree();
  19. void InsertNode();
  20. void InsertEngine(TreeNode* &, int);
  21. void DeleteNode();
  22. void DeleteEngine(TreeNode* &, int);
  23. void SearchNode();
  24. TreeNode* SearchEngine(TreeNode*, int);
  25. TreeNode* find_max(TreeNode*); void find_max();
  26. TreeNode* find_min(TreeNode*); void find_min();
  27. void DeleteTree(TreeNode*&); void DeleteTree();
  28. void PreOrder(TreeNode* node); void PreOrder();
  29. void InOrder(TreeNode* node); void InOrder();
  30. void PostOrder(TreeNode* node); void PostOrder();
  31. void menu();
  32.  
  33. void treeInitiate() {
  34.     if (root != NULL)
  35.         DeleteTree(root);
  36.     deletion = false;
  37. }
  38.  
  39. int main() {
  40.     menu();
  41.     cout << endl;
  42.     main();
  43.     return 0;
  44. }
  45.  
  46. TreeNode* MakeNode(int data) {
  47.     TreeNode* NodePtr = new TreeNode;
  48.     if (NodePtr == NULL) {
  49.         cout << "\nOut of memory." << endl;
  50.         return NULL;
  51.     }
  52.     else {
  53.         cout << "\nMemory allocated for a new node." << endl;
  54.         NodePtr->key = data; NodePtr->left = NodePtr->right = NULL;
  55.         return NodePtr;
  56.     }
  57. }
  58.  
  59. void CreateTree() {
  60.     cout << "\n*** How many elements will be on the new tree? Elements: ";
  61.     int n; cin >> n;
  62.     treeInitiate();
  63.     for (int i = 0; i < n; i++) {
  64.         cout << "\nElement " << i + 1 << ": ";
  65.         int data; cin >> data;
  66.         InsertEngine(root, data);
  67.     }
  68.     cout << "\n*** New Tree has been created with " << n << " elements." << endl;
  69. }
  70.  
  71. void InsertNode() {
  72.     if (root != NULL) {
  73.         cout << "\n*** Which element do you wish to insert into the BST? Data value: ";
  74.         int data; cin >> data;
  75.         InsertEngine(root, data);
  76.         cout << "\n*** Element " << data << " has been inserted." << endl;
  77.     }
  78.     else cout << "\nCreate a BST first. [Choice no: 1]" << endl;
  79. }
  80.  
  81. void InsertEngine(TreeNode* &node, int data) {
  82.     if (node == NULL)
  83.         node = MakeNode(data);
  84.     else if (data < node->key)
  85.         InsertEngine(node->left, data);
  86.     else if (data > node->key)
  87.         InsertEngine(node->right, data);
  88. }
  89.  
  90. void DeleteNode() {
  91.     if (root != NULL) {
  92.         cout << "\n*** Which element do you wish to delete from the BST? Element: ";
  93.         int data; cin >> data;
  94.         DeleteEngine(root, data);
  95.         if (deletion == true) {
  96.             cout << "\nElement " << data << " just got deleted." << endl;
  97.             deletion = false;
  98.         }
  99.         else
  100.             cout << "\nElement " << data << " could not be found so operation failed." << endl;
  101.     }
  102.     else cout << "\n*** Deletetion cannot be done. [Empty Tree]" << endl;
  103. }
  104.  
  105. void DeleteEngine(TreeNode* &node, int data) {
  106.     if (node != NULL) {
  107.         if (data < node->key)
  108.             DeleteEngine(node->left, data);
  109.         else if (data > node->key)
  110.             DeleteEngine(node->right, data);
  111.         else {
  112.             deletion = true;
  113.             if (node->left == NULL && node->right == NULL) {
  114.                 delete node;
  115.                 node = NULL;
  116.             }
  117.             else if (node->left == NULL) {
  118.                 TreeNode* temp = node;
  119.                 node = node->right;
  120.                 delete temp;
  121.                 temp = NULL;
  122.             }
  123.             else if (node->right == NULL) {
  124.                 TreeNode* temp = node;
  125.                 node = node->left;
  126.                 delete temp;
  127.                 temp = NULL;
  128.             }
  129.             else {
  130.                 TreeNode* temp = find_max(node->left); // find_min(node->right);
  131.                 node->key = temp->key;
  132.                 DeleteEngine(node->left, temp->key);
  133.                 // node->right = DeleteEngine(node->right, temp->key);
  134.             }
  135.         }
  136.     }
  137. }
  138.  
  139. void DeleteTree() {
  140.     if (root == NULL)
  141.         cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  142.     else {
  143.         DeleteTree(root);
  144.         cout << "\nTree has been deleted." << endl;
  145.     }
  146. }
  147.  
  148. void DeleteTree(TreeNode* &node) {
  149.     if (node != NULL) {
  150.         DeleteTree(node->left);
  151.         DeleteTree(node->right);
  152.         delete node;
  153.         node = NULL;
  154.     }
  155. }
  156.  
  157. void SearchNode() {
  158.     if (root != NULL) {
  159.         cout << "\n*** Which element do you wish to search in the BST? Element: ";
  160.         int data; cin >> data;
  161.         TreeNode* node;
  162.         node = SearchEngine(root, data);
  163.         if (node == NULL)
  164.             cout << "\nGiven element could not be found in your tree." << endl;
  165.         else cout << "\nGiven element " << data << " has been found." << endl;
  166.     }
  167.     else cout << "\n*** Search cannot be done. [Empty Tree]" << endl;
  168. }
  169.  
  170. TreeNode* SearchEngine(TreeNode* node, int data) {
  171.     if (node != NULL) {
  172.         if (data < node->key)
  173.             node = SearchEngine(node->left, data);
  174.         else if (data > node->key)
  175.             node = SearchEngine(node->right, data);
  176.     }
  177.     return node;
  178. }
  179.  
  180. void find_min() {
  181.     if (root != NULL)
  182.         cout << "\nMin: " << find_min(root)->key << endl;
  183.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  184. }
  185.  
  186. TreeNode* find_min(TreeNode* node) {
  187.     while (node->left != NULL)
  188.         node = node->left;
  189.     return node;
  190. }
  191.  
  192. void find_max() {
  193.     if (root != NULL)
  194.         cout << "\nMax: " << find_max(root)->key << endl;
  195.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  196. }
  197.  
  198. TreeNode* find_max(TreeNode* node) {
  199.     while (node->right != NULL)
  200.         node = node->right;
  201.     return node;
  202. }
  203.  
  204. void PreOrder() {
  205.     if (root != NULL) {
  206.         cout << "\nPre-Order: ";
  207.         PreOrder(root); cout << endl;
  208.     }
  209.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  210. }
  211.  
  212. void PreOrder(TreeNode* node) {
  213.     if (node != NULL) {
  214.         cout << node->key << " ";
  215.         PreOrder(node->left);
  216.         PreOrder(node->right);
  217.     }
  218. }
  219.  
  220. void InOrder() {
  221.     if (root != NULL) {
  222.         cout << "\nIn-Order: ";
  223.         InOrder(root); cout << endl;
  224.     }
  225.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  226. }
  227.  
  228. void InOrder(TreeNode* node) {
  229.     if (node != NULL) {
  230.         InOrder(node->left);
  231.         cout << node->key << " ";
  232.         InOrder(node->right);
  233.     }
  234. }
  235.  
  236. void PostOrder() {
  237.     if (root != NULL) {
  238.         cout << "\nPost-Order: ";
  239.         PostOrder(root); cout << endl;
  240.     }
  241.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  242. }
  243.  
  244. void PostOrder(TreeNode* node) {
  245.     if (node != NULL) {
  246.         PostOrder(node->left);
  247.         PostOrder(node->right);
  248.         cout << node->key << " ";
  249.     }
  250. }
  251.  
  252. void menu() {
  253.     cout << "Choice List: " << endl;
  254.     cout << "\n01. Create a new BST.\n02. Insert into BST.\n03. Delete from BST.\n04. Search in BST."
  255.         << "\n05. Maximum value in BST.\n06. Minimum value in BST.\n07. Pre-Order Traverse."
  256.         << "\n08. In-Order Traverse.\n09. Post-Order Traverse.\n10. DELETE TREE\n11. EXIT !" << endl;
  257.     int choice; cout << "\nChoose : "; cin >> choice;
  258.  
  259.     switch (choice) {
  260.     case 1: CreateTree();
  261.         break;
  262.     case 2: InsertNode();
  263.         break;
  264.     case 3: DeleteNode();
  265.         break;
  266.     case 4: SearchNode();
  267.         break;
  268.     case 5: find_max();
  269.         break;
  270.     case 6: find_min();
  271.         break;
  272.     case 7: PreOrder();
  273.         break;
  274.     case 8: InOrder();
  275.         break;
  276.     case 9: PostOrder();
  277.         break;
  278.     case 10: DeleteTree();
  279.         break;
  280.     case 11: cout << "\nTerminating ....\n\n";
  281.         DeleteTree(root);
  282.         exit(0);
  283.     default: cout << "\nWrong Choice. [Choose between 1 - 10]\n" << endl;
  284.         menu();
  285.     }
  286. }
RAW Paste Data