473,856 Members | 1,745 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

gekko3558
6 New Member
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
5 5280
Ganon11
3,652 Recognized Expert Specialist
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
Apr 5 '07 #2
gekko3558
6 New Member
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
3,652 Recognized Expert Specialist
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
6 New Member
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
6 New Member
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

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

Similar topics

8
2788
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am cs students and are now facing difficult problems in understanding what a binary tree is, how it works, and the algorithm to display, arrange, find, delete the leaf node in binary tree. I hope that anyone with expereince in building binary tree could help me in explaining the binary tree functions, and give a sample code of the whole picture behind the tree. And...
11
2539
by: jova | last post by:
Is there a difference between a Binary Tree and a Binary Search Tree? If so can someone please explain. Thank You.
0
4258
by: j | last post by:
Hi, Anyone out there with binary search tree experience. Working on a project due tomorrow and really stuck. We need a function that splits a binary tree into a bigger one and smaller one(for a random binary search tree. We've tried everything but are in the land of pointer hell. If someone could help it would be a huge help. our code follows. We've tried 2 diff methods the split() and splitter() functions #include <iostream> #include...
4
9025
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working, even the removal, I just don't know how to keep track of the parent, so that I can set its child to the child of the node to be removed. IE - if I had C / \ B D
15
5109
by: Foodbank | last post by:
Hi all, I'm trying to do a binary search and collect some stats from a text file in order to compare the processing times of this program (binary searching) versus an old program using linked lists. I'm totally new to binary searches by the way. Can anyone help me with the commented sections below? Much of the code such as functions and printfs has already been completed. Any help is greatly appreciated. Thanks,
1
2957
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template <typename Tclass Tree{ private: Tree<T*left;
4
11020
by: whitehatmiracle | last post by:
Hello I have written a program for a binary tree. On compiling one has to first chose option 1 and then delete or search. Im having some trouble with the balancing function. It seems to be going into an infinite loop, i think im messing up with the pointers. Heres the code. //press 1, first, Do not press it a second time!!!
11
1191
by: Defected | last post by:
Hi, How i can create a Binary Search Tree with a class ? thanks
7
3879
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left'...
0
9916
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11056
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10782
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10384
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9531
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7932
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5761
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4575
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4174
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.