Thread: 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;

}

Find will bomb out if the tree is empty.
You have a bad habbit of checking xxxx->left and xxxx->right against NULL before a recursive call, instead if simply checking xxxx for NULL at the start of the function. Don't worry about that one extra recursive call. Better to keep the code size down.

Use constructor initialisation lists.

Hint: I also have code for this on my website.

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*, int);
      void R_Destroyer(Hub *);
#ifdef _RECURSIVE
      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(){
            
#ifdef _RECURSIVE
            R_Destroyer(root);
#else
      
            Hub *it = root;
            Hub *save;

            while ( it != NULL ) {
                  if ( it->left != NULL ) {
                    /* Right rotation */
                    save = it->left;
                    it->left = save->right;
                    save->right = it;
                  }
                  else {
                    save = it->right;
                    delete it ;
                  }

            it = save;
      
            }
#endif
      }

};

void BinTree::Put(int aVal)
{
      Hub** h = &Find(aVal);
      if(*h == NULL){ 
            *h = new Hub(aVal, NULL, NULL); 
            ++count;
      }

}
BinTree::Hub*& BinTree::Find(int val)
{
#ifdef _RECURSIVE
      if(root == NULL || val == root->val) return root;
      else return R_Find(root, val);
      
#else
      Hub* it = root;
      
      if(root == NULL || 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;      
            delete *suc;      //Remove Successor
            *suc = t;
      }


}

BinTree::Hub*& BinTree::FindSuccessor(Hub* h)
{
      int v = h->val;
      Hub** it = &h->right;
      while((*it)->left != NULL) {
            it = &(*it)->left;
      }
      return *it;
}

#ifdef _RECURSIVE

BinTree::Hub*& BinTree::R_Find(Hub*& h, int val)
{      
      if(h == NULL || h->val == val) return h;

      else if(val > h->val)
      {
            return R_Find(h->right, val);
      }
      else
      {
            return R_Find(h->left, val);
      }
      

}
#endif

void BinTree::PrintOn()
{
      if(root) R_PrintOn(root, 0);
}

void BinTree::R_PrintOn(Hub* h, int depth)
{
      using namespace std;
      if(h == NULL) return;
      R_PrintOn(h->right, depth + 2);
      for(int i = 0; i< depth; ++i) cout << " "; 
      cout << h->val << endl;
      R_PrintOn(h->left, depth + 2);
}

void BinTree::R_Destroyer(Hub *h)
{
      if(h == NULL) return;
      R_Destroyer(h->right);
      R_Destroyer(h->left);
      delete h;

}

My initial reaction is to get rid of all that #ifdef _RECURSIVE stuff.

All very interesting, but you're bloating the code with what is in effect duplicate code to achieve the same thing (and duplicating debug time, understanding time and maintenance time). If the non-recursive works just fine, and is easy to understand, then just go with it.

The destructor is a little on the large side to be embedded in the class definition itself.

That _RECURSIVE is because my book used recursive function. But I didn't like recursive things. So I implemented non-recursive ones. But I felt that I have escaped from recursive ones, so came back to fight with them and made them too.

I used references and pointer to pointers in such a way that I get surprised when it works.

Hint: I also have code for this on my website.

Template syntax is very confuzing for me at the mean time (I've not covered its chapter yet).

Use constructor initialisation lists.

For BinTree class I think you mean. OK.

[OFF-TOPIC]
In Arabic "Salem" means healthy. We use it in Farsi too nowadays.
[/OFF-TOPIC]