c++ - 搜索二叉树函数不起作用c ++

Question

我试图实现一个二叉搜索树：

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key) {
if (ptr == 0) {
 cout<<"No such data: "<<key<<" in the tree"<<endl; 
 return false;
 }
else{
if (ptr->data == key) {
    cout<<"Find a node whose data is "<<key<<endl;
      return true;
} 
else if (ptr->data < key)  return search(ptr->leftPtr,key);

else  return search(ptr->rightPtr,key);
}
}

但无论树是否包含键值，结果总是返回 false。你们可以帮我检查代码吗？我试过调试，但还是不知道。

谢谢！

Answer 1

您的左树下降遍历比较器是向后的。因此，一旦您错误地下降到正确的树中，您就没有机会找到该值。只有根，而且只有根，才能正确找到。

这：

if (ptr->data < key)
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

应该是这样的：

if (key < ptr->data) // <== note key is LESS THAN node.
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

---

也就是说，考虑一下：

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key)
{
    if (ptr == 0) {
        cout<<"No such data: "<<key<<" in the tree"<<endl;
        return false;
    }

    if (key < ptr->data)
        return search(ptr->leftPtr, key);
    else if (ptr->data < key)
        return search(ptr->rightPtr, key);

    cout<<"Found a node whose data is "<< key << endl;
    return true;
}