Searching in tree structure problem

[alihemmati19]

I have a problem with searching in a tree structure data in C++. My code is below. Every node in the tree has 3 children. My 'search' function is recursive and I want to determine that is there any node in the tree that has my 'item'. But 'search' does not work. I think my recursion has some problem.

class tree{
   char* key;
   tree* left;
   tree* mid;
   tree* right;

   public:
   bool search(tree *temp, char *item) //temp is root of tree//
   {                                   //that is initialized //
      if (temp == NULL)                //in main()           //
         return false;
      if (item == temp->key)
         return true;
      if(search( temp->left,item )) return true;
      else if(search( temp->mid,item )) return true;
      else if(search( temp->right,item )) return true;
      else return false;
   }
};

[Galik]

I can't see anything wrong with the recursion myself.

When you say if (item == temp->key) are you trying to compare strings?

Because that is comparing the pointers, NOT the strings. It is testing if item and temp->key point to the very same string. It does not test if those strings contain the same characters.

Maybe look at #include <cstring> and the function std::strcmp();

[alihemmati19]

Thanks, but the problem still exists. By doing what you said, output of 'search' is always True. I'm confused.

[rollie]

Note that strcmp returns 0 when the 2 parameters match. You can likely see what's going wrong by adding some logging functions to your code. In this case, try:

bool search(tree *temp, char *item) //temp is root of tree//
   {                                   //that is initialized //
      if (temp == NULL)                //in main()           //
         return false;
      std::cout << "item = " << item << std::endl;
      std::cout << "temp->key = " << temp->key << std::endl;
      if (strcmp(item, temp->key) == 0)
         return true;
...

--Rollie

[moorecm]

Please post the main function.

Also, be careful of name conflicts. There is a std::search.

[alihemmati19]

Thanks Rollie. I didn't know that strcmp returns 0 when parameters match. And thanks moorecm. I changed my function to 'Search' with capital letter. Below is my modified 'Search' and also main(). But sadly, problem exists. :(

#include <iostream>
#include <cstring>
using namespace std;

class tree{
   char* key;
   tree* left;
   tree* mid;
   tree* right;

   public:
   void setKey(char* n)
   {
    key = n; 
   }
   bool Search(tree *temp, char *item) //temp is root of tree//
   {                                   //that is initialized //
      if (temp == NULL)                //in main()           //
         return false;
      if ( strcmp(item,temp->key)==0 )
         return true;
      if(Search( temp->left,item )) return true;
      else if(Search( temp->mid,item )) return true;
      else if(Search( temp->right,item )) return true;
      else return false;
   }
};

int main()
{
    tree* root=new tree;
    root->setKey("1");

    char* x;        //key of parent
    cin>>x;
    cout<<root->Search(root,x);

    return 0;
}