By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,456 Members | 1,480 Online
Bytes IT Community

Home Questions Articles Browse Topics Latest Top Members FAQ

home > topics > c / c++ > questions > simple binary search tree in c++.. help with find
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,456 IT Pros & Developers. It's quick & easy.

simple binary search tree in C++.. HELP WITH FIND

gekko3558
P: 6
I am writing a simple binary search tree (nodes are int nodes) with a BSTNode class and a BST class. I have followed the instructions from my C++ book, and now I am trying to get a remove method working. But before I get to the remove, I need to get my find method working. Basically, I am trying to get a "find" method working that will search for a giving int value, and return the node with that value. I have designed my current find with the help of my book, but for some off reason, when I run my program and try to find the values I do, it returns "10" (the root) everytime, and will not complete when I try to find a number thats not in the tree. Any help would be great!

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using std::cout;
  3. using std::endl;
  4.  
  5. class BSTNode
  6. {
  7.  friend class BST;
  8.   public:
  9.    BSTNode(int); 
  10.    int getValue();
  11.     void print();
  12.  
  13.   private:
  14.    int value;
  15.    BSTNode *leftPtr;
  16.    BSTNode *rightPtr;
  17. };
  18.  
  19. class BST
  20. {
  21.  public:
  22.    BST();
  23.    void insertNode(const int &);
  24.     BSTNode find(const int);
  25.  
  26.  private:
  27.    BSTNode *rootPtr;
  28.  
  29.    void insertNodeHelper(BSTNode**, const int &);
  30.     BSTNode findHelper(BSTNode**, const int);
  31. };
  32.  
  33. /****
  34.  MAIN
  35. *****/
  36. int main(void)
  37. {
  38.    cout << "TESTING MY BSTNode CLASS:" << endl
  39.        << "creating nodes with values 3, 4, and 5" << endl << endl;
  40.     BSTNode node1 = BSTNode(3);
  41.     cout << "node1 has value of: " << node1.getValue() << endl;
  42.     BSTNode node2 = BSTNode(4);
  43.     cout << "node2 has value of: " << node2.getValue() << endl;
  44.     BSTNode node3 = BSTNode(5);
  45.     cout << "node3 has value of: " << node3.getValue() << endl;
  46.  
  47.     cout << endl << "Using the print method, the values are:" << endl;
  48.     node1.print();
  49.     node2.print();
  50.     node3.print();
  51.  
  52.     cout << endl << endl << "TESTING MY BST CLASS:" << endl
  53.        << "adding 10, 5, 15, 20, 8, and 10 to the tree" << endl;
  54.     //Binary Search Tree
  55.     BST tree = BST();
  56.     tree.insertNode(10);
  57.     tree.insertNode(5);
  58.     tree.insertNode(15);
  59.     tree.insertNode(20);
  60.     tree.insertNode(8);
  61.     tree.insertNode(10);
  62.  
  63.     cout << endl << "testing the find method" << endl;
  64.     cout << tree.find(10).getValue() << " ";
  65.     tree.find(5).print();
  66.     tree.find(15).print();
  67.     tree.find(20).print();
  68.  
  69.     return 0;
  70. }
  71.  
  72. /***************
  73.  BSTNode Methods
  74. ****************/
  75.  
  76. //CONSTRUCTOR
  77. BSTNode::BSTNode(int d)
  78.    : value(d),
  79.      leftPtr(NULL),
  80.      rightPtr(NULL)
  81.    {}
  82.  
  83. //METHODS
  84. int BSTNode::getValue()
  85.    {return value;}
  86. void BSTNode::print()
  87.    {cout << value << " ";}
  88.  
  89. /***********
  90.  BST Methods
  91. ************/
  92.  
  93. //CONSTRUCTOR
  94. BST::BST() 
  95.    {rootPtr = NULL;}
  96.  
  97. //INSERT METHOD
  98. void BST::insertNode(const int &value)
  99.    {insertNodeHelper(&rootPtr, value);}
  100. void BST::insertNodeHelper(BSTNode **ptr, const int &value)
  101. {
  102.    if (*ptr == NULL)  
  103.       *ptr = new BSTNode(value);
  104.    else
  105.    {     
  106.       if (value < (*ptr)->value)
  107.          insertNodeHelper(&((*ptr)->leftPtr), value);
  108.       else
  109.       {
  110.  
  111.          if (value > (*ptr)->value)
  112.             insertNodeHelper(&((*ptr)->rightPtr), value);
  113.          else  //SKIPS DUPLICATE NUMBERS
  114.             cout << "   " << value << " already exists in the tree... no duplicates will be added" << endl;
  115.       }
  116.    }
  117. }
  118.  
  119. //FIND METHOD FOR USE WITH REMOVE
  120. BSTNode BST::find(const int value)
  121.    {return findHelper(&rootPtr, value);}
  122. BSTNode BST::findHelper(BSTNode **ptr, const int value)
  123. {
  124.    if (value == (*ptr)->value)
  125.        return **ptr;
  126.     else
  127.     {
  128.        if ((*ptr)->value > value)
  129.           findHelper(&((*ptr)->leftPtr), value);
  130.  
  131.        else
  132.         {
  133.            if ((*ptr)->value < value)
  134.              findHelper(&((*ptr)->rightPtr), value);
  135.  
  136.           else
  137.              {cout << "node not found"; return BSTNode(-1);}
  138.         }
  139.     }
  140. }
  141.  
Apr 5 '07 #1
Share this Question
Share on Google+
5 Replies
Ganon11
Expert 2.5K+
P: 3,652
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
Apr 5 '07 #2
gekko3558
P: 6
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
that is a very great idea, however it did not change the output. Any other suggestions?
Apr 5 '07 #3
Ganon11
Expert 2.5K+
P: 3,652
Ah-hah!

In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.
Apr 5 '07 #4
gekko3558
P: 6
Ah-hah!

In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.
HAHA, yeah i actually JUST noticed this right before I read this comment. Dumbest mistake ever lol. But I did this, the find works great... EXCEPT when the value i search for is not found... The problem now seems in returning a NULL pointer im guessing, perhaps I'm making another stupid mistake. I have changed my entire code to as follows:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using std::cout;
  3. using std::endl;
  4.  
  5. class BSTNode
  6. {
  7.  friend class BST;
  8.   public:
  9.    BSTNode(int); 
  10.    int getValue();
  11.     void print();
  12.  
  13.   private:
  14.    int value;
  15.    BSTNode *leftPtr;
  16.    BSTNode *rightPtr;
  17. };
  18.  
  19. class BST
  20. {
  21.   public:
  22.    BST();
  23.    void insertNode(const int &);
  24.     BSTNode* find(const int &);
  25.  
  26.   private:
  27.    BSTNode *rootPtr;
  28.  
  29.    void insertNodeHelper(BSTNode**, const int &);
  30.     BSTNode* findHelper(BSTNode*, const int &);
  31. };
  32.  
  33. /****
  34.  MAIN
  35. *****/
  36. int main(void)
  37. {
  38.    cout << "TESTING MY BSTNode CLASS:" << endl
  39.        << "creating nodes with values 3, 4, and 5" << endl << endl;
  40.     BSTNode node1 = BSTNode(3);
  41.     cout << "node1 has value of: " << node1.getValue() << endl;
  42.     BSTNode node2 = BSTNode(4);
  43.     cout << "node2 has value of: " << node2.getValue() << endl;
  44.     BSTNode node3 = BSTNode(5);
  45.     cout << "node3 has value of: " << node3.getValue() << endl;
  46.  
  47.     cout << endl << "Using the print method, the values are:" << endl;
  48.     node1.print();
  49.     node2.print();
  50.     node3.print();
  51.  
  52.     cout << endl << endl << "TESTING MY BST CLASS:" << endl
  53.        << "adding 3, 2, 5, 1, 4, 6, and 4 to the tree" << endl;
  54.     //Binary Search Tree
  55.     BST tree = BST();
  56.     tree.insertNode(3);
  57.     tree.insertNode(2);
  58.     tree.insertNode(5);
  59.     tree.insertNode(1);
  60.     tree.insertNode(4);
  61.     tree.insertNode(6);
  62.     tree.insertNode(4);
  63.  
  64.     cout << endl << "testing the find method" << endl;
  65.     for(int i = 1; i <= 6; i++)
  66.     {
  67.        if(tree.find(i) == NULL)
  68.            cout << i << " was not found!" << endl;
  69.        else
  70.            (tree.find(i))->print();
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
  76. /***************
  77.  BSTNode Methods
  78. ****************/
  79.  
  80. //CONSTRUCTOR
  81. BSTNode::BSTNode(int d)
  82.    : value(d),
  83.      leftPtr(NULL),
  84.      rightPtr(NULL)
  85.    {}
  86.  
  87. //METHODS
  88. int BSTNode::getValue()
  89.    {return value;}
  90. void BSTNode::print()
  91.    {cout << value << " ";}
  92.  
  93. /***********
  94.  BST Methods
  95. ************/
  96.  
  97. //CONSTRUCTOR
  98. BST::BST() 
  99.    {rootPtr = NULL;}
  100.  
  101. //INSERT METHOD
  102. void BST::insertNode(const int &value)
  103.    {insertNodeHelper(&rootPtr, value);}
  104. void BST::insertNodeHelper(BSTNode **ptr, const int &value)
  105. {
  106.    if (*ptr == NULL)  
  107.       *ptr = new BSTNode(value);
  108.    else
  109.    {     
  110.       if (value < (*ptr)->getValue())
  111.          insertNodeHelper(&((*ptr)->leftPtr), value);
  112.       else
  113.       {
  114.  
  115.          if (value > (*ptr)->getValue())
  116.             insertNodeHelper(&((*ptr)->rightPtr), value);
  117.          else  //SKIPS DUPLICATE NUMBERS
  118.             cout << "   " << value << " already exists in the tree... no duplicates will be added" << endl;
  119.       }
  120.    }
  121. }
  122.  
  123. //BEGINNING OF REMOVE
  124. //FIND METHOD FOR USE WITH REMOVE
  125. BSTNode* BST::find(const int &value)
  126.    {return findHelper(rootPtr, value);}
  127. BSTNode* BST::findHelper(BSTNode *ptr, const int &value)
  128. {
  129.    while (ptr!=NULL || (ptr)->getValue() == value)
  130.    {
  131.       if ((ptr)->getValue() > value)
  132.          ptr = (ptr)->leftPtr;
  133.       else if ((ptr)->getValue() < value)
  134.          ptr = (ptr)->rightPtr;
  135.       else if ((ptr)->getValue() == value)
  136.          break;
  137.    }
  138.  
  139.    if (!ptr)
  140.        return NULL;
  141.    else
  142.       return ptr;
  143. }
  144.  
Apr 5 '07 #5
gekko3558
P: 6
nevermind!!!! I figured it out, thanks so much for you help though..

instead of checking
Expand|Select|Wrap|Line Numbers
  1. if(!tree.find(value))
  2. {
  3.    not found code
  4. }
  5. else
  6. {
  7.    found code
  8. }
  9.  
i needed to do it this way
Expand|Select|Wrap|Line Numbers
  1. if(tree.find(value))
  2. {
  3.    found code
  4. }
  5. else
  6. {
  7.    not found code
  8. }
  9.  
Apr 5 '07 #6

Post your reply

Sign in to post your reply or Sign up for a free account.

Question stats

  • viewed: 4690
  • replies: 5
  • date asked: Apr 5 '07
BYTES.COM © 2020 About Bytes | Advertise on Bytes | Privacy Policy | Manage Cookies
Sitemap | C / C++ Answers Sitemap | C / C++ Insights Sitemap

Follow us to get the Latest Bytes Updates