c++ - 子字符串的二叉搜索树？

Question

我有一个有效的搜索功能，它将在数据库中搜索确切的值，但我的目标是让它在存储数据的数据库中搜索子字符串，并在搜索子字符串时（使用了 cout <<“检查通过”）我可以看到通过树的搜索缩短了，找到了一些子字符串，而其他更深的却没有？为什么？

  bool contains(const Comparable & key, BinaryNode *leaf)
  {
    //cout << "containsing... for: " << key << endl;
    if(leaf != NULL)
    { 
     //std::string Data = leaf->element;

    //cout << "check passed for contains!" << endl;
    if(leaf->element.find(key) != std::string::npos)
    {
       //std::cout << "Found->" << key << "!" << endl;
       return true;
    }
    else if(key >= leaf->element)
    {
     // cout << "key->" << key << "is less than leaf->" <<leaf->element << endl;
      if(leaf->left != NULL)
       return contains(key, leaf->left);
      else
       return false;
    }
    else if(key < leaf->element)
    { 
      //cout << "key->" << key << "is greater than leaf->" <<leaf->element << endl;
      if(leaf->right != NULL)
       return contains(key, leaf->right);
      else
       return false;
    }
    else
      return false;
  }
 else 
  return false;  

} 

Answer 1

尝试这个 ...

bool contains(const Comparable & key, BinaryNode *leaf)
{
    if(!leaf)
        return false;

    if(leaf->element.find(key) != std::string::npos)
        return true;

    int nResult = leaf->element.compare(key);
    if(nResult == 0)
        return true; // This condition will never be hit.
    else
    if(nResult < 0)
        return contains(key, leaf->left)
    else
    if(nResult > 0)
        return contains(key, leaf->right)
}

还尝试调试并查找键值是否小于/大于叶节点值，那么这是否意味着它对于子字符串也是相同的。如果没有，那么您必须同时搜索左右子树。如果左子树返回 false，则在右子树中搜索。下面的代码...

bool contains(const Comparable & key, BinaryNode *leaf)
{
    if(!leaf)
        return false;

    if(leaf->element.find(key) != std::string::npos)
        return true;

    if( !contains(key, leaf->left) )
        return contains(key, leaf->right)

    return true;
}