My first binary search tree

This is a discussion on My first binary search tree within the C++ Programming forums, part of the General Programming Boards category; Please tell me its bugs or any idea you have. Code: #include <iostream> //#define _RECURSIVE class BinTree{ private : struct ...

  1. #1
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231

    Post 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;
    
    }
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    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;
    
    }
    Last edited by siavoshkc; 08-06-2007 at 03:01 AM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    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]
    Last edited by siavoshkc; 08-06-2007 at 06:08 AM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21