BST搜索函数在一台机器上返回true，在另一台机器中返回false

Question

我有一个BST程序，这是我的搜索函数，如果在节点中找到指定的数据（d），它将返回true。调用时，节点*s指向树的根节点。

当我在大学的虚拟机上编译这个程序时，它运行得很好，但当我在macbook上编译和运行它时，它返回false。是什么导致了完全不同的输出？我添加了一行来打印它在搜索时经过的每个节点的数据，它会找到具有正确数据的节点，但仍然返回false。

如果有任何帮助，我将不胜感激，我想不出这个函数在不同的编译器下会崩溃的原因。

这是我的mac编译器上的信息

Apple LLVM 6.0版（clang-600.0.57）（基于LLVM 3.5svn）目标：x86_64-apple-darwin14.1.0线程型号：posix

这是关于我的虚拟机编译器的信息

g++（Ubuntu/Linaro 4.6.3-1ubuntu5）4.6.3

这是我的BST搜索功能：

  bool bst::search(int d, node *s){
  cout << s->data << endl;
  if(s->data == d){
    curRoot = s;
    return 1;
  }
  else if(d > s->data){
    if(s->right == NULL)
      return 0;
    else{
      if(s->right->data == d)
        pRoot = s;
      search(d,s->right);
    }
  }
  else{
    if(s->left == NULL)
      return 0;
    else{
      if(s->left->data == d)
        pRoot = s;
      search(d,s->left);
    }
  } 
}

Answer 1

当前函数中存在几个问题/冗余。首先，您需要将递归函数search（）的值返回到堆栈的顶部。

冗余的形式是多个NULL检查，多个数据相等性检查。服务于该目的的函数的浓缩形式如下-

bool bst::search(int d, node *s){
   if(s == NULL) {
      return 0;
   }
   if(s->data == d) {
      return 1;
   }
   if(d > s->data) {
      return search(d,s->right);
   }
   else {
      return search(d,s->left);
   }
}

Answer 2

您似乎认为搜索函数应该只返回一次。。。对于迭代实现来说，这确实是应该的。因此，让我们来看一个，基于sray的简化。

bool bst::search(int d, const node *s)
{
   while (s) {
      if(s->data == d) return 1;
      if(d > s->data) {
         s = s->right;
      }
      else {
         s = s->left;
      }
   }
   return 0;
}

这是可能的，因为递归是尾部递归的——我们可以只替换参数和循环。

递归本身并不是这样工作的。它的工作原理与任何其他函数调用一样。如果您在函数中调用sqrt，您不会认为sqrt会取代您的函数，而是会在计算中使用结果。调用自己的函数时也是如此。有时需要使用递归结果进行进一步计算。考虑这个函数来计算树中的节点：

bool count(const node *s)
{
   if (s)
      return count(s->left) + 1 + count(s->right);
   return 0;
}

让最深的调用为整个树设置返回值是没有好处的。