C++递归函数返回值

作为一项家庭作业，我正在实现一个二叉搜索树，并且正在做一些搜索某些数据的位置（以便能够稍后修改/删除它）的部分，这里是我的一块代码：C++递归函数返回值

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，但每一次这个函数返回根本身。然后我想也许这与foo的第一个实例没有返回值有关，所以我将search(x, pos->right)更改为return search(x, pos->right)，对于左侧则同样如此，此时一切正常。这使我困惑，我试着做了几运行具有以下虚拟函数只是为了了解那会返回

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

我虽然没有规定什么情况下返回if语句是假的，它剧照工程和输出1.我想也许foo(0)刚刚回到无论foo(1)在递归返回，检查我尝试这样：

int boo() { 
    return 1; 
} 

int foo() { 
    boo(); 
}

，并呼吁foo()，这就造成了“富必须返回值”的错误，很明显将boo()更改为return boo()固定它。所以我的问题是为什么第一个案件输出根？为什么第二个案例甚至有效？

来源

2016-12-29 user3002386

如果没有'return'语句返回某个不同于'void'的函数的末尾，就会导致未定义的行为。你幸运没有[鼻子守护神]（http://www.urbandictionary.com/define.php?term=nasal%20demons）！ –

@DietmarKühl感谢参考鼻子deamons :) –

拿起并返回一个'node *'似乎很奇怪，但是你对于搜索的递归调用的结果并没有做任何事情（因此没有有效的'return'）。 – crashmstr

你有这里的问题是，你不宣传你的递归调用的返回值回原来的调用者。事实上，当这些调用返回时，该值将被丢弃。

更糟糕的是，在情况下，你不觉得你的对手，你作为书面未能返回任何东西，这是不确定的行为。获得根节点的事实更多的是编译器或当前内存布局的怪癖，而不是定义的结果。

正如@Mike指出的那样，对于二叉树，根据搜索值是否大于或小于当前节点的值，您应该只在搜索中遍历一个子树。传统上，左边的树保存的值小于当前节点，而右边的树保留的值更大。

来源

2016-12-29 20:34:06

另外他们不应该需要在bst中搜索这两个子树 – Mike

C++递归函数返回值

回答

相关问题