My first binary search tree
Please tell me its bugs or any idea you have.
Code:
#include <iostream>
//#define _RECURSIVE
class BinTree{
private:
struct Hub{
int val;
Hub* left;
Hub* right;
Hub(int val, Hub* left, Hub* right) : val(val), left(left), right(right){};
};
Hub*& FindSuccessor(Hub*);
void R_PrintOn(Hub*);
void R_Destroyer(Hub *);
#ifdef _RECURSIVE
void R_Put(Hub*, int);
Hub*& R_Find(Hub*&, int);
#endif
int count;
Hub *root;
public:
BinTree(){root = NULL; count = 0;}
void PrintOn();
Hub*& Find(int val); //Public for test only
void Put(int val);
void Remove(int val);
int Count() {return count;}
~BinTree(){
if(root) R_Destroyer(root);
}
};
void BinTree::Put(int aVal)
{
if(!root){
root = new Hub(aVal, NULL, NULL);
}
#ifdef _RECURSIVE
else
R_Put(root, aVal);
#else
else{
Hub* it = root;
while(it){
if(aVal == it->val) return;
else if(aVal > it->val){
if(!it->right) {
it->right=new Hub(aVal, NULL, NULL);
break;
}
else
it = it->right;
}
else{
if(!it->left) {
it->left=new Hub(aVal, NULL, NULL);
break;
}
else
it = it->left;
}
}
}
#endif
++count;
}
BinTree::Hub*& BinTree::Find(int val)
{
#ifdef _RECURSIVE
if(val == root->val) return root;
else return R_Find(root, val);
#else
Hub* it = root;
if(val == it->val) return root;
while(true){
if(val > it->val)
{
if(it->right == NULL) return it->right;
else if(it->right->val == val) return it->right;
else it = it->right;
}
else
{
if(it->left == NULL) return it->left;
else if(it->left->val == val) return it->left;
else it = it->left;
}
}
#endif
}
void BinTree::Remove(int rVal)
{
Hub** it = &Find(rVal);
if((*it)->left == NULL && (*it)->right == NULL)
{
delete *it;
*it = NULL;
}
else if((*it)->right == NULL)
{
Hub* t = (*it)->left;
delete *it;
*it = t;
}
else if((*it)->left == NULL )
{
Hub* t = (*it)->right;
delete *it;
*it = t;
}
else
{
Hub** suc = &FindSuccessor(*it); //Find Successor
(*it)->val = (*suc)->val; //Copy Successor to Bad Item
Hub* t = (*suc)->right; //Remove Successor
delete *suc;
*suc = t;
}
}
BinTree::Hub*& BinTree::FindSuccessor(Hub* h)
{
int v = h->val;
Hub** it = &h->right;
while((*it)->left == NULL) {
if((*it)->right == NULL) return *it;
else *it = (*it)->right;
}
return *it;
}
#ifdef _RECURSIVE
void BinTree::R_Put(Hub* h, int aVal)
{
if(aVal == h->val) return;
else if(aVal > h->val){
if(h->right == NULL) h->right = new Hub(aVal, NULL, NULL);
else R_Put(h->right, aVal);
}
else{
if(h->left == NULL) h->left = new Hub(aVal, NULL, NULL);
else R_Put(h->left, aVal);
}
}
BinTree::Hub*& BinTree::R_Find(Hub*& h, int val)
{
if(val > h->val)
{
if(h->right == NULL || h->right->val == val) return h->right;
else return R_Find(h->right, val);
}
else
{
if(h->left == NULL || h->left->val == val) return h->left;
else return R_Find(h->left, val);
}
}
#endif
void BinTree::PrintOn()
{
if(root) R_PrintOn(root);
}
void BinTree::R_PrintOn(Hub* h)
{
using namespace std;
cout << h->val << endl;
if(h->right) R_PrintOn(h->right);
if(h->left) R_PrintOn(h->left);
}
void BinTree::R_Destroyer(Hub *h)
{
if(h->right) R_Destroyer(h->right);
if(h->left) R_Destroyer(h->left);
delete h;
}