Advertisement
Guest User

Untitled

a guest
Mar 28th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.85 KB | None | 0 0
  1. #ifndef BST_H
  2. #define BST_H
  3.  
  4. #include "Node.h"
  5.  
  6. template <typename TYPE>
  7. class BST
  8. {
  9. private:
  10. Node <TYPE> * root;
  11.  
  12. Node <TYPE> * _search(Node <TYPE> *, const TYPE &) const;
  13. Node <TYPE> * _insert(Node <TYPE> *, const TYPE &);
  14. void _inorderTraverse(Node <TYPE> * pRoot, void (*process) (TYPE dataIn));
  15. void _destruct(Node <TYPE> *);
  16.  
  17. public:
  18. BST();
  19. ~BST();
  20. bool insert(const TYPE &);
  21. bool search(TYPE &) const;
  22. bool update(const TYPE &);
  23. void inorderTraverse(void (*process) (TYPE dataIn));
  24. };
  25.  
  26.  
  27. template <typename TYPE>
  28. BST <TYPE> :: BST()
  29. {
  30. root = nullptr;
  31. }
  32.  
  33. template <typename TYPE>
  34. BST <TYPE> :: ~BST()
  35. {
  36. _destruct(root);
  37. }
  38.  
  39. template <typename TYPE>
  40. void BST <TYPE> :: _destruct(Node <TYPE> * pRoot)
  41. {
  42. if (pRoot)
  43. {
  44. _destruct(pRoot->left);
  45. _destruct(pRoot->right);
  46.  
  47. delete pRoot;
  48. }
  49. }
  50.  
  51. template <typename TYPE>
  52. Node <TYPE> * BST <TYPE> :: _insert(Node <TYPE> * pRoot, const TYPE & dataIn)
  53. {
  54. if (pRoot)
  55. {
  56. if (dataIn < pRoot->data)
  57. pRoot->left = _insert(pRoot->left, dataIn);
  58.  
  59. if (dataIn > pRoot->data)
  60. pRoot->right = _insert(pRoot->right, dataIn);
  61. }
  62. else
  63. pRoot = new (nothrow)Node <TYPE>(dataIn);
  64.  
  65. return pRoot;
  66. }
  67.  
  68. template <typename TYPE>
  69. Node <TYPE> * BST <TYPE> ::_search(Node <TYPE> * pRoot, const TYPE & dataOut) const
  70. {
  71. if (pRoot)
  72. {
  73. cout << dataOut << "|" << pRoot->data << endl;
  74. if (dataOut < pRoot->data)
  75. pRoot = _search(pRoot->left, dataOut);
  76.  
  77. //cout << "1" << endl;
  78. //cout << dataOut << "|" << pRoot->data << endl;
  79. //cout << "2" << endl;
  80.  
  81. else if (dataOut > pRoot->data)
  82. pRoot = _search(pRoot->right, dataOut);
  83. }
  84. return pRoot;
  85. }
  86.  
  87. template <typename TYPE>
  88. void BST <TYPE> :: _inorderTraverse(Node <TYPE> * pRoot, void (* process) (TYPE dataIn))
  89. {
  90. if (pRoot)
  91. {
  92. _inorderTraverse(pRoot->left, process);
  93. process(pRoot->data);
  94. _inorderTraverse(pRoot->right, process);
  95. }
  96. }
  97.  
  98. template <typename TYPE>
  99. bool BST <TYPE> :: insert(const TYPE & dataIn)
  100. {
  101. bool success = false;
  102. Node <TYPE> * pFound;
  103.  
  104. pFound = _search(root, dataIn);
  105.  
  106. cout << "!" << endl;
  107.  
  108. if (!pFound)
  109. {
  110. root = _insert(root, dataIn);
  111. success = true;
  112. }
  113.  
  114. return success;
  115. }
  116.  
  117. template <typename TYPE>
  118. bool BST <TYPE> :: search(TYPE & dataOut) const
  119. {
  120. bool success = false;
  121. Node <TYPE> * pFound;
  122.  
  123. pFound = _search(root, dataOut);
  124.  
  125. if (pFound)
  126. {
  127. dataOut = pFound->data;
  128. success = true;
  129. }
  130.  
  131. return success;
  132. }
  133.  
  134. template <typename TYPE>
  135. bool BST <TYPE> :: update(const TYPE & dataIn)
  136. {
  137. bool search = false;
  138. Node <TYPE> * pFound;
  139.  
  140. pFound = _search(root, dataIn);
  141.  
  142. if (pFound)
  143. {
  144. pFound->data = dataIn;
  145. success = true;
  146. }
  147.  
  148. return success;
  149. }
  150.  
  151. template <typename TYPE>
  152. void BST <TYPE> :: inorderTraverse(void (*process) (TYPE dataIn))
  153. {
  154. _inorderTraverse(root, process);
  155. }
  156.  
  157. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement