fueanta

Binary Search Tree in C++ [FULL]

Sep 16th, 2017
315
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // AUTHOR : Fueanta
  2. // Implementation of BST in CPP
  3. // Last Modified : September 16, 2017 (Generic BST Data Structure, Node count)
  4. // Contact EMAIL : fueanta@gmail.com [let me know if you find any bug]
  5.  
  6. #include <iostream>
  7. #include <string>
  8. #include <stdlib.h>
  9. #include <queue>
  10.  
  11. using std::queue;
  12. using namespace std;
  13.  
  14. void menu();
  15.  
  16. int main() {
  17.     menu();
  18.     cout << endl;
  19.     main();
  20.     return 0;
  21. }
  22.  
  23. template <class T>
  24. class tree_node {
  25. public:
  26.     T key;
  27.     tree_node<T> *left, *right;
  28. };
  29.  
  30. template <class T>
  31. class bst
  32. {
  33.     tree_node<T>* root_;
  34.     int count_;
  35.     bool deletion_;
  36.  
  37. public:
  38.     bst()
  39.     {
  40.         root_ = nullptr;
  41.         count_ = 0;
  42.         deletion_ = false;
  43.     }
  44.  
  45.     void tree_initiate();
  46.     tree_node<T>* make_node(T);
  47.     void create_tree();
  48.     void insert_node();
  49.     void insert_engine(tree_node<T>* &, T);
  50.     void delete_node();
  51.     void delete_engine(tree_node<T>* &, T);
  52.     void search_node();
  53.     tree_node<T>* search_engine(tree_node<T>*, T);
  54.     static tree_node<T>* find_max(tree_node<T>*); void find_max();
  55.     static tree_node<T>* find_min(tree_node<T>*); void find_min();
  56.     void delete_tree(tree_node<T>*&); void delete_tree();
  57.     void pre_order(tree_node<T>*); void pre_order();
  58.     void in_order(tree_node<T>*); void in_order();
  59.     void post_order(tree_node<T>*); void post_order();
  60.     void disp_tree(tree_node<T>*); void disp_tree();
  61.     int count_nodes() const;
  62.  
  63.     friend void menu();
  64. };
  65.  
  66. bst<int> bin; /* ##### -|-|CHANGE BST TYPE HERE|-|- ##### */
  67.  
  68. template <typename T>
  69. void bst<T>::tree_initiate() {
  70.     if (root_ != nullptr)
  71.         delete_tree(root_);
  72.     deletion_ = false;
  73.     this->count_ = 0;
  74. }
  75.  
  76. template <typename T>
  77. tree_node<T>* bst<T>::make_node(T data) {
  78.     tree_node<T>* node_ptr = new tree_node<T>;
  79.     if (node_ptr == nullptr) {
  80.         cout << "\nOut of memory." << endl;
  81.         return nullptr;
  82.     }
  83.     else {
  84.         cout << "\nMemory allocated for a new node." << endl;
  85.         node_ptr->key = data; node_ptr->left = node_ptr->right = nullptr;
  86.         ++this->count_;
  87.         return node_ptr;
  88.     }
  89. }
  90.  
  91. template <typename T>
  92. void bst<T>::create_tree() {
  93.     tree_initiate();
  94.     cout << "\n*** How many elements will be on the new tree? Elements: ";
  95.     int n; cin >> n;
  96.     for (auto i = 0; i < n; i++) {
  97.         cout << "\nElement " << i + 1 << ": ";
  98.         T data; cin >> data;
  99.         insert_engine(root_, data);
  100.     }
  101.     cout << "\n*** New Tree has been created with " << n << " elements." << endl;
  102. }
  103.  
  104. template <typename T>
  105. void bst<T>::insert_node() {
  106.     if (root_ != nullptr) {
  107.         cout << "\n*** Which element do you wish to insert into the BST? Data value: ";
  108.         T data; cin >> data;
  109.         insert_engine(root_, data);
  110.         cout << "\n*** Element " << data << " has been inserted." << endl;
  111.     }
  112.     else cout << "\nCreate a BST first. [Choice no: 1]" << endl;
  113. }
  114.  
  115. template <typename T>
  116. void bst<T>::insert_engine(tree_node<T>* &node, T data) {
  117.     if (node == nullptr)
  118.         node = make_node(data);
  119.     else if (data < node->key)
  120.         insert_engine(node->left, data);
  121.     else if (data > node->key)
  122.         insert_engine(node->right, data);
  123. }
  124.  
  125. template <typename T>
  126. void bst<T>::delete_node() {
  127.     if (root_ != nullptr) {
  128.         cout << "\n*** Which element do you wish to delete from the BST? Element: ";
  129.         T data; cin >> data;
  130.         delete_engine(root_, data);
  131.         if (deletion_ == true) {
  132.             cout << "\nElement " << data << " just got deleted." << endl;
  133.             --this->count_;
  134.             deletion_ = false;
  135.         }
  136.         else
  137.             cout << "\nElement " << data << " could not be found so operation failed." << endl;
  138.     }
  139.     else cout << "\n*** Deletetion cannot be done. [Empty Tree]" << endl;
  140. }
  141.  
  142. template <typename T>
  143. void bst<T>::delete_engine(tree_node<T>* &node, T data) {
  144.     if (node != nullptr) {
  145.         if (data < node->key)
  146.             delete_engine(node->left, data);
  147.         else if (data > node->key)
  148.             delete_engine(node->right, data);
  149.         else {
  150.             deletion_ = true;
  151.             if (node->left == nullptr && node->right == nullptr) {
  152.                 delete node;
  153.                 node = nullptr;
  154.             }
  155.             else if (node->left == nullptr) {
  156.                 tree_node<T>* temp = node;
  157.                 node = node->right;
  158.                 delete temp;
  159.             }
  160.             else if (node->right == nullptr) {
  161.                 tree_node<T>* temp = node;
  162.                 node = node->left;
  163.                 delete temp;
  164.             }
  165.             else {
  166.                 tree_node<T>* temp = find_max(node->left); // or, find_min(node->right);
  167.                 node->key = temp->key;
  168.                 delete_engine(node->left, temp->key);
  169.                 // or, DeleteEngine(node->right, temp->key);
  170.             }
  171.         }
  172.     }
  173. }
  174.  
  175. template <typename T>
  176. void bst<T>::delete_tree() {
  177.     if (root_ == nullptr)
  178.         cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  179.     else {
  180.         delete_tree(root_);
  181.         cout << "\nTree has been deleted." << endl;
  182.     }
  183. }
  184.  
  185. template <typename T>
  186. void bst<T>::delete_tree(tree_node<T>* &node) {
  187.     if (node != nullptr) {
  188.         delete_tree(node->left);
  189.         delete_tree(node->right);
  190.         delete node;
  191.         node = nullptr;
  192.     }
  193.     this->count_ = 0;
  194. }
  195.  
  196. template <typename T>
  197. void bst<T>::search_node() {
  198.     if (root_ != nullptr) {
  199.         cout << "\n*** Which element do you wish to search in the BST? Element: ";
  200.         T data; cin >> data;
  201.         tree_node<T> * node = search_engine(root_, data);
  202.         if (node == nullptr)
  203.             cout << "\nGiven element could not be found in your tree." << endl;
  204.         else cout << "\nGiven element " << data << " has been found." << endl;
  205.     }
  206.     else cout << "\n*** Search cannot be done. [Empty Tree]" << endl;
  207. }
  208.  
  209. template <typename T>
  210. tree_node<T>* bst<T>::search_engine(tree_node<T>* node, T data) {
  211.     if (node != nullptr) {
  212.         if (data < node->key)
  213.             node = search_engine(node->left, data);
  214.         else if (data > node->key)
  215.             node = search_engine(node->right, data);
  216.     }
  217.     return node;
  218. }
  219.  
  220. template <typename T>
  221. void bst<T>::find_min() {
  222.     if (root_ != nullptr)
  223.         cout << "\nMin: " << find_min(root_)->key << endl;
  224.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  225. }
  226.  
  227. template <typename T>
  228. tree_node<T>* bst<T>::find_min(tree_node<T>* node) {
  229.     while (node->left != nullptr)
  230.         node = node->left;
  231.     return node;
  232. }
  233.  
  234. template <typename T>
  235. void bst<T>::find_max() {
  236.     if (root_ != nullptr)
  237.         cout << "\nMax: " << find_max(root_)->key << endl;
  238.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  239. }
  240.  
  241. template <typename T>
  242. tree_node<T>* bst<T>::find_max(tree_node<T>* node) {
  243.     while (node->right != nullptr)
  244.         node = node->right;
  245.     return node;
  246. }
  247.  
  248. template <typename T>
  249. void bst<T>::pre_order() {
  250.     if (root_ != nullptr) {
  251.         cout << "\nPre-Order: ";
  252.         pre_order(root_); cout << endl;
  253.     }
  254.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  255. }
  256.  
  257. template <typename T>
  258. void bst<T>::pre_order(tree_node<T>* node) {
  259.     if (node != nullptr) {
  260.         cout << node->key << " ";
  261.         pre_order(node->left);
  262.         pre_order(node->right);
  263.     }
  264. }
  265.  
  266. template <typename T>
  267. void bst<T>::in_order() {
  268.     if (root_ != nullptr) {
  269.         cout << "\nIn-Order: ";
  270.         in_order(root_); cout << endl;
  271.     }
  272.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  273. }
  274.  
  275. template <typename T>
  276. void bst<T>::in_order(tree_node<T>* node) {
  277.     if (node != nullptr) {
  278.         in_order(node->left);
  279.         cout << node->key << " ";
  280.         in_order(node->right);
  281.     }
  282. }
  283.  
  284. template <typename T>
  285. void bst<T>::post_order() {
  286.     if (root_ != nullptr) {
  287.         cout << "\nPost-Order: ";
  288.         post_order(root_); cout << endl;
  289.     }
  290.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  291. }
  292.  
  293. template <typename T>
  294. void bst<T>::post_order(tree_node<T>* node) {
  295.     if (node != nullptr) {
  296.         post_order(node->left);
  297.         post_order(node->right);
  298.         cout << node->key << " ";
  299.     }
  300. }
  301.  
  302. template <typename T>
  303. void bst<T>::disp_tree() {
  304.     if (root_ != nullptr) {
  305.         cout << "\nBST by level: ";
  306.         disp_tree(root_); cout << endl;
  307.     }
  308.     else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
  309. }
  310.  
  311. template <typename T>
  312. void bst<T>::disp_tree(tree_node<T>* node) {
  313.     queue <tree_node<T>*> bst;
  314.     bst.push(node);
  315.     while (!bst.empty()) {
  316.         if (bst.front()->left != nullptr)
  317.             bst.push(bst.front()->left);
  318.         if (bst.front()->right != nullptr)
  319.             bst.push(bst.front()->right);
  320.         cout << bst.front()->key << " ";
  321.         bst.pop();
  322.     }
  323.     cout << endl;
  324. }
  325.  
  326. template <typename T>
  327. int bst<T>::count_nodes() const
  328. {
  329.     return count_;
  330. }
  331.  
  332. void menu() {
  333.     cout << "Choice List: " << endl;
  334.     cout << "\n01. Create a new BST.\n02. Insert into BST.\n03. Delete from BST.\n04. Search in BST."
  335.         << "\n05. Maximum value in BST.\n06. Minimum value in BST.\n07. Pre-Order Traverse."
  336.         << "\n08. In-Order Traverse {{Ascending Order}}.\n09. Post-Order Traverse.\n10. Display by Levels.\n11. Delete Tree.\n12. Show total number of nodes.\n13. EXIT !" << endl;
  337.     int choice; cout << "\nChoose : "; cin >> choice;
  338.  
  339.     switch (choice) {
  340.     case 1: bin.create_tree();
  341.         break;
  342.     case 2: bin.insert_node();
  343.         break;
  344.     case 3: bin.delete_node();
  345.         break;
  346.     case 4: bin.search_node();
  347.         break;
  348.     case 5: bin.find_max();
  349.         break;
  350.     case 6: bin.find_min();
  351.         break;
  352.     case 7: bin.pre_order();
  353.         break;
  354.     case 8: bin.in_order();
  355.         break;
  356.     case 9: bin.post_order();
  357.         break;
  358.     case 10: bin.disp_tree();
  359.         break;
  360.     case 11: bin.delete_tree();
  361.         break;
  362.     case 12: cout << "\nTotal number of nodes: " << bin.count_nodes() << endl;
  363.         break;
  364.     case 13: cout << "\nTerminating ....\n\n";
  365.         bin.delete_tree(bin.root_);
  366.         exit(0);
  367.     default: cout << "\nWrong Choice. [Choose between 1 - 13]\n" << endl;
  368.         menu();
  369.     }
  370. }
RAW Paste Data