Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef BST_H
- #define BST_H
- #include "Node.h"
- template <typename TYPE>
- class BST
- {
- private:
- Node <TYPE> * root;
- Node <TYPE> * _search(Node <TYPE> *, const TYPE &) const;
- Node <TYPE> * _insert(Node <TYPE> *, const TYPE &);
- void _inorderTraverse(Node <TYPE> * pRoot, void (*process) (TYPE dataIn));
- void _destruct(Node <TYPE> *);
- public:
- BST();
- ~BST();
- bool insert(const TYPE &);
- bool search(TYPE &) const;
- bool update(const TYPE &);
- void inorderTraverse(void (*process) (TYPE dataIn));
- };
- template <typename TYPE>
- BST <TYPE> :: BST()
- {
- root = nullptr;
- }
- template <typename TYPE>
- BST <TYPE> :: ~BST()
- {
- _destruct(root);
- }
- template <typename TYPE>
- void BST <TYPE> :: _destruct(Node <TYPE> * pRoot)
- {
- if (pRoot)
- {
- _destruct(pRoot->left);
- _destruct(pRoot->right);
- delete pRoot;
- }
- }
- template <typename TYPE>
- Node <TYPE> * BST <TYPE> :: _insert(Node <TYPE> * pRoot, const TYPE & dataIn)
- {
- if (pRoot)
- {
- if (dataIn < pRoot->data)
- pRoot->left = _insert(pRoot->left, dataIn);
- if (dataIn > pRoot->data)
- pRoot->right = _insert(pRoot->right, dataIn);
- }
- else
- pRoot = new (nothrow)Node <TYPE>(dataIn);
- return pRoot;
- }
- template <typename TYPE>
- Node <TYPE> * BST <TYPE> ::_search(Node <TYPE> * pRoot, const TYPE & dataOut) const
- {
- if (pRoot)
- {
- cout << dataOut << "|" << pRoot->data << endl;
- if (dataOut < pRoot->data)
- pRoot = _search(pRoot->left, dataOut);
- //cout << "1" << endl;
- //cout << dataOut << "|" << pRoot->data << endl;
- //cout << "2" << endl;
- else if (dataOut > pRoot->data)
- pRoot = _search(pRoot->right, dataOut);
- }
- return pRoot;
- }
- template <typename TYPE>
- void BST <TYPE> :: _inorderTraverse(Node <TYPE> * pRoot, void (* process) (TYPE dataIn))
- {
- if (pRoot)
- {
- _inorderTraverse(pRoot->left, process);
- process(pRoot->data);
- _inorderTraverse(pRoot->right, process);
- }
- }
- template <typename TYPE>
- bool BST <TYPE> :: insert(const TYPE & dataIn)
- {
- bool success = false;
- Node <TYPE> * pFound;
- pFound = _search(root, dataIn);
- cout << "!" << endl;
- if (!pFound)
- {
- root = _insert(root, dataIn);
- success = true;
- }
- return success;
- }
- template <typename TYPE>
- bool BST <TYPE> :: search(TYPE & dataOut) const
- {
- bool success = false;
- Node <TYPE> * pFound;
- pFound = _search(root, dataOut);
- if (pFound)
- {
- dataOut = pFound->data;
- success = true;
- }
- return success;
- }
- template <typename TYPE>
- bool BST <TYPE> :: update(const TYPE & dataIn)
- {
- bool search = false;
- Node <TYPE> * pFound;
- pFound = _search(root, dataIn);
- if (pFound)
- {
- pFound->data = dataIn;
- success = true;
- }
- return success;
- }
- template <typename TYPE>
- void BST <TYPE> :: inorderTraverse(void (*process) (TYPE dataIn))
- {
- _inorderTraverse(root, process);
- }
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement