C++递归函数return值

Question

作为作业，我正在实现一个二叉搜索树，并且正在做搜索一些数据的位置的部分（以便能够 modify/remove 它稍后），这是我的一段代码:

node*& bst::search(data& x, node*& pos) {
    if (pos->get().num == x.num) {
        return pos;
    }
    if (pos->right != NULL) search(x, pos->right);
    if (pos->left != NULL) search(x, pos->left);
}

在我调用的源文件中search(data_to_find, root)。在我的例子中，我有一棵这种形式的整数树：

1
 2
  3

根指向 1。当我想搜索元素 3 时，我期望得到指向 3 的指针，但每次这个函数 return 都是根本身。然后我想这可能与 foo 的第一个实例没有 returning 值有关，所以我将 search(x, pos->right) 更改为 return search(x, pos->right) 并且左侧相同，这次一切正常。这让我感到困惑，我尝试使用以下虚拟函数运行几次，只是为了了解它会做什么 return

int foo(int x = 0) {
    if (x == 1) {
        return x;
    }
    x++;
    foo(x);
}

虽然我没有指定 return 以防 if 语句为假，但它仍然有效并输出 1。我想也许 foo(0) 只是 returned 任何 foo(1) return 在递归中编辑，检查我是否尝试过这个：

int boo() {
    return 1;
}

int foo() {
    boo();
}

并调用 foo()，导致 "foo must return a value" 错误，显然将 boo() 更改为 return boo() 修复了它。所以我的问题是为什么第一个案例输出 root？为什么第二种情况甚至有效？

Answer 1

这里的问题是您没有将递归调用的 return 值传播回原始调用者。实际上，当那些调用 return 时，该值被丢弃。

更糟糕的是，在找不到匹配项的情况下，您所写的功能将无法 return 任何事情，这是未定义的行为。您获得根节点的事实更多是编译器的怪癖或您当前的内存布局，而不是定义的结果。

正如@Mike 所指出的，对于二叉树，您应该只在搜索中遍历一个子树，这取决于您的搜索值是大于还是小于当前所持有的值节点。传统上，左树保存的值小于当前节点，而右树保存的值大于当前节点。

C++递归函数return值

C++ recursive function return value

c++

recursion

pointers

return-value

binary-search-tree