Guest User

Untitled

a guest
Mar 22nd, 2019
80
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