BST 搜索函数 returns 在一台机器上为真，在另一台机器上为假

Question

我有一个 BST 程序，这是我的搜索功能，如果在节点中找到指定的数据 (d)，则 returns 为真。调用时node *s指向树的根节点。

当我在我大学的虚拟 machine 上编译这个程序时，它工作得很好，但是当我编译时 returns 错误，并且运行它在我的 mac 书上。什么会导致完全不同的输出？我加了一行，打印出它搜索时经过的每个节点的数据，它找到了数据正确的节点，但还是returns false.

非常感谢任何帮助，我想不出为什么这个函数会在不同的编译器下崩溃的原因。

这是关于我的mac编译器

的信息

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

这是我的虚拟machine编译器

上的信息

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

您当前的函数中有几个problems/redundancies。首先，您需要 return 将递归函数 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

您似乎认为搜索功能应该 return 仅一次...这确实是迭代实现的方式。那么我们来看一个，基于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;
}

让最深的调用为整棵树设置 return 值对你没有好处。

BST 搜索函数 returns 在一台机器上为真，在另一台机器上为假

BST search function returns true on one machine and false on another

c++

g++

binary-search-tree