SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef BST_H
  2. #define BST_H
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. template<class elemType>
  9. struct node {
  10.     elemType info;
  11.     node<elemType> *leftLink;
  12.     node<elemType> *rightLink;
  13. };
  14.  
  15. template<class elemType>
  16. class BST
  17. {
  18. public:
  19.     BST();
  20.     ~BST();
  21.  
  22.     void insert(elemType &insertItem);
  23.     bool search(elemType &searchItem);
  24.     bool isEmpty();
  25.     void inorderTraversal();
  26.     void preorderTraversal();
  27.     void postorderTraversal();
  28.     void destroy(node<elemType> *point);
  29.     elemType getMaxElem();
  30.     void bstToFile(ofstream &file1);
  31.  
  32. private:
  33.     void insert(elemType &item, node<elemType> *point);
  34.     void inorderTraversal(node<elemType> *point);
  35.     void preorderTraversal(node<elemType> *point);
  36.     void postorderTraversal(node<elemType> *point);
  37.     void bstToFile(node<elemType> *point, ofstream &f);
  38.  
  39.     node<elemType> *root;
  40. };
  41.  
  42. template<class elemType>
  43. BST<elemType>::BST() {
  44.     root = NULL;
  45. }
  46.  
  47. template<class elemType>
  48. BST<elemType>::~BST() {
  49.     destroy(root);
  50. }
  51.  
  52. template<class elemType>
  53. void BST<elemType>::insert(elemType &insertItem) {
  54.     if(root == NULL)
  55.     {
  56.         root = new node<elemType>;
  57.         root->info = insertItem;
  58.         root->leftLink = NULL;
  59.         root->rightLink = NULL;
  60.     }
  61.     else
  62.     {
  63.         insert(insertItem, root);
  64.     }
  65. }
  66.  
  67. template<class elemType>
  68. bool BST<elemType>::search(elemType &searchItem) {
  69.     node<elemType> *current;
  70.  
  71.     bool found = false;
  72.  
  73.     if(root == NULL)
  74.     {
  75.         cout << "Cannot search an empty tree." << endl;
  76.     }
  77.     else
  78.     {
  79.         current = root;
  80.         while(current != NULL && found == false)
  81.         {
  82.             if(searchItem == current->info)
  83.                 found = true;
  84.  
  85.             else if(searchItem < current->info)
  86.                 current = current->leftLink;
  87.             else
  88.                 current = current->rightLink;
  89.         }
  90.     }
  91.  
  92.     return found;
  93. }
  94.  
  95.  
  96. template<class elemType>
  97. bool BST<elemType>:: isEmpty() {
  98.     return (root == NULL);
  99. }
  100.  
  101. template<class elemType>
  102. void BST<elemType>::inorderTraversal() {
  103.     inorderTraversal(root);
  104. }
  105.  
  106.  
  107. template<class elemType>
  108. void BST<elemType>::preorderTraversal() {
  109.     preorderTraversal(root);
  110. }
  111.  
  112.  
  113. template<class elemType>
  114. void BST<elemType>::postorderTraversal() {
  115.     postorderTraversal(root);
  116. }
  117.  
  118.  
  119. template<class elemType>
  120. void BST<elemType>::destroy(node<elemType> *point) {
  121.     if(point != NULL)
  122.     {
  123.         destroy(point->leftLink);
  124.         destroy(point->rightLink);
  125.         delete point;
  126.         point = NULL;
  127.     }
  128. }
  129.  
  130.  
  131. template<class elemType>
  132. elemType BST<elemType>::getMaxElem() {
  133.     elemType max;
  134.  
  135.     if(root == NULL)
  136.     {
  137.         cout << "Error: Tree is empty." << endl;
  138.     }
  139.  
  140.     else
  141.     {
  142.         node<elemType> *current;
  143.         current = root;
  144.  
  145.         while(current->rightLink != NULL)
  146.         {
  147.             current = current->rightLink;
  148.         }
  149.    
  150.          max = current->info;
  151.     }
  152.  
  153.     return max;
  154. }
  155.  
  156. template<class elemType>
  157. void BST<elemType>::bstToFile(ofstream &file1) {
  158.     bstToFile(root, file1);
  159. }
  160.  
  161. template<class elemType>
  162. void BST<elemType>::insert(elemType &item, node<elemType> *point) {
  163.     node<elemType> *newNode;
  164.     newNode = new node<elemType>;
  165.     newNode->info = item;
  166.     newNode->leftLink = NULL;
  167.     newNode->rightLink = NULL;
  168.    
  169.         if(item == point->info)
  170.         {
  171.             cout << "Duplicates elements are not allowed." << endl;
  172.             return;
  173.         }
  174.         else
  175.         {
  176.  
  177.             if(item < point->info)
  178.             {
  179.                 if(point->leftLink != NULL)
  180.                     insert(item, point->leftLink);
  181.                 else
  182.                     point->leftLink = newNode;
  183.             }
  184.             else
  185.             {
  186.                 if(point->rightLink != NULL)
  187.                     insert(item, point->rightLink);
  188.                 else
  189.                     point->rightLink = newNode;
  190.             }
  191.            
  192.          }
  193.  
  194. }
  195.  
  196. template<class elemType>
  197. void BST<elemType>::inorderTraversal(node<elemType> *point) {
  198.  
  199.     if(point != NULL)
  200.     {
  201.         inoderTraversal(point->leftLink);
  202.         cout << point->info << " ";
  203.         inorderTraversal(point->rightLink);
  204.     }
  205. }
  206.  
  207.  
  208. template<class elemType>
  209. void BST<elemType>::preorderTraversal(node<elemType> *point) {
  210.  
  211.     if(point != NULL)
  212.     {
  213.         cout << point->info << " ";
  214.         inoderTraversal(point->leftLink);
  215.         inorderTraversal(point->rightLink);
  216.     }
  217. }
  218.  
  219. template<class elemType>
  220. void BST<elemType>::postorderTraversal(node<elemType> *point) {
  221.  
  222.     if(point != NULL)
  223.     {
  224.         inoderTraversal(point->leftLink);
  225.         inorderTraversal(point->rightLink);
  226.         cout << point->info << " ";
  227.     }
  228. }
  229.  
  230. template<class elemType>
  231. void BST<elemType>::bstToFile(node<elemType> *point, ofstream &f) {
  232.     if(point == NULL)
  233.     {
  234.         return;
  235.     }
  236.  
  237.     bstToFile(point->leftLink, f);
  238.     f << point->info;
  239.     bstToFile(point->rightLink, f);
  240. }
  241.  
  242.  
  243. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top