c++ - 为什么这个递归函数计算二叉搜索树中的节点总是返回比预期更大的结果？

Question

该函数总是返回比实际节点数大 1 的答案(例如树有 3 个节点但返回 4)。我什至尝试在纸上手动执行代码，但仍然没有发现问题。我在这里弄错了关于递归或函数的任何基础知识吗？

int countNode (Tree &T)
{
    int count;
    if(T==NULL) return 0; 
    return count++;
    countNode(T->left);
    countNode(T->right);
}

这个给出的答案比 2 大:

int countNode (Tree &T)
{
    int count;
    if(T==NULL) return 0; 
    return count+=1;
    countNode(T->left);
    countNode(T->right);
}

然而，这非常有效:

int countNode (Tree &T)
{   
    if(T==NULL) return 0; 
    int a = countNode(T->left);
    int b = countNode(T->right);
    int count = a + b + 1;
    return count;
}

我明白为什么最后一个功能有效，但仍然不知道前两个功能有什么问题。

Answer 1

您的第一段代码中的问题与其他问题密切相关，因此让我们重点关注它。这是您的代码:

int countNode (Tree &T)
{
    int count;
    if(T==NULL) return 0; 
    return count++;
    countNode(T->left);
    countNode(T->right);
}

这里有几点需要注意。首先，将编译器警告设置调到最大值。您可能会看到几个警告:

1. 您实际上从未初始化过 count 的值，因此当您返回 count++ 时，您返回的是垃圾值。这可能解释了为什么您会看到多计数。

2. 如果你写 return count++;，你是在说“增加 count，然后取它的旧值——还没有增加——然后返回它。”那可能不是您想要做的。如果你想增加count，就写count++。如果要返回count + 1，只写return count + 1;即可。

3. 您编写的 return 语句将导致您的函数在进行任何递归调用之前退出 - 对 countNode 的调用永远不会到达也不会触发。您可能需要重新排序代码或删除您使用 return 语句编写的代码来解决这个问题。

4. 您永远不会捕获 countNode 的返回值。请记住，对 countNode 的每次调用都有其自己的 count 版本，因此在一次递归调用中简单地增加 count 不会触及其他版本的计数。您需要存储两个递归调用的返回值，它们应该返回左子树和右子树中有多少个节点，并确定您希望如何将它们聚合在一起。

我认为编译器警告可能会标记前三个问题，但最后一个问题要微妙一些。

基于此，你能看出另一个不正确的实现是怎么回事吗，为什么你上一个实现是正确的？