467,219 Members | 1,420 Online
Bytes | Developer Community
Ask Question

Home New Posts Topics Members FAQ

home > topics > c / c++ > questions > simple binary search tree in c++.. help with find

Post your question to a community of 467,219 developers. It's quick & easy.

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

gekko3558
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
  • viewed: 4840
Share:
5 Replies
Ganon11
Expert 2GB
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
Apr 5 '07 #2
gekko3558
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 2GB
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
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
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.

Similar topics
help in explaining binary tree
8 posts views Thread by Jerry Khoo | last post: by
Binary Trees
11 posts views Thread by jova | last post: by
Binary Search Tree Split() function
reply views Thread by j | last post: by
binary search tree removal - stuck - HELP!!
4 posts views Thread by Tarique Jawed | last post: by
Binary Tree
15 posts views Thread by Foodbank | last post: by
Link Error, Why doesn't my simple binary search tree class work??
1 post views Thread by hn.ft.pris@gmail.com | last post: by
Balancing a Binary Tree
4 posts views Thread by whitehatmiracle@gmail.com | last post: by
Binary Search Tree
11 posts views Thread by Defected | last post: by
Empty binary trees
7 posts views Thread by Vinodh | last post: by
BYTES.COM © 2021
About Us
Advertise
Terms Of Use
Privacy Policy
Manage Cookies
Contact Us
Sitemap
C / C++ Answers Sitemap
C / C++ Insights Sitemap

Follow us! Get the Latest Bytes Updates
By using this site, you agree to our Privacy Policy and Terms of Use.