2 
template <class T>
bool BST<T>::search(const T& x, int& len) const
{
    return search(BT<T>::root, x);
}


template <class T>
bool BST<T>::search(struct Node<T>*& root, const T& x)
{
   if (root == NULL)
       return false;
   else
      {
         if (root->data == x)
             return true;
         else if(root->data < x)
             search(root->left, x);
         else 
             search(root->right, x);                 
      }             
}

所以这是我对带有 T 节点的 BST 类的搜索功能。x 是在树中搜索的数据，len 只是它必须经过的节点数量才能找到匹配节点（如果存在）。我还没有实现这一点，我只是在逐步发展我的任务。我通过这样做来调用它：

if(t.search(v[1], len) == true)
       cout << endl << "true";

v 只是我必须创建的一个向量来比较它，所以这只是为它提供一个 int。我得到的错误：

BST.h: In member function âbool BST<T>::search(const T&, int&) const [with T = int]â:
prog5.cc:24:   instantiated from here    
BST.h:78: error: no matching function for call to âBST<int>::search(Node<int>* const&, const int&) constâ    
BST.h:76: note: candidates are: bool BST<T>::search(const T&, int&) const [with T = int]
BST.h:83: note:                 bool BST<T>::search(Node<T>*&, const T&) [with T = int]

所以我不确定我做错了什么或哪里做错了。

4

3 回答 3

2

好的，bool BST<T>::search(struct Node<T>*& root, const T& x)应该像这样在它之后有 const：bool BST<T>::search(struct Node<T>*& root, const T& x) const。基本上，您已经从 const 函数调用了非常量函数，这是一个禁忌。

顺便说一句，这对我来说看起来很可疑“ struct Node<T>*&”......我可能会放弃 & 并使用Node<T>*......但也许你需要它，因为struct？

此外，这是 C++，没有理由将 Node 作为结构体......需要在参数定义中包含结构体看起来很糟糕，恕我直言。为什么不让 Node 成为一个类？

于 2008-10-29T02:49:38.763 回答
1

您的搜索代码存在多个问题：

  • 排序顺序是倒序的，如果节点数据比你搜索的少，你应该在右分支中搜索，而不是左分支。

  • 您应该返回递归调用的结果

  • 也不清楚你为什么root通过引用传递。它应该作为const合格的指针传递，并且方法体也应该是const合格的。

这是一个替代方案：

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    if (root == NULL)
        return false;
    else
    if (root->data == x)
        return true;
    else
    if (root->data < x)
        return search(root->right, x);
    else 
        return search(root->left, x);
}

这是一个更简单的非递归实现：

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    while (root != NULL) {
        if (root->data == x)
            return true;
        if (root->data < x)
            root = root->right;
        else 
            root = root->left;
    }
    return false;
}
于 2016-10-31T20:18:03.623 回答
0

算法 ：

  1. 取节点值数据；
  2. 重复第 3 步到第 5 步，直到找到值或超出树。
  3. 如果数据等于根节点值，则搜索成功并终止算法。
  4. 如果数据小于根节点值，我们必须搜索左子树。
  5. 否则数据小于根节点值，我们必须搜索左子树。
  6. 输出打印消息“找到”或“未找到”。

C++ 实现

    node* search(node* root, int data)
    {
     if (root==NULL || root->data==data) return root;

     if (root->data < data)   return search(root->right, data);

     return search(root->left, data);
   }
于 2016-10-05T18:30:25.133 回答