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

问题描述：

该函数总是返回比实际节点数大1的答案（例如树有3个节点但返回4）。我甚至试图在纸上手动执行代码，但仍然没有看到问题。有没有关于递归或函数的基础知识，我在这里得到错误？为什么计算二叉搜索树中的节点的递归函数总是返回比预期更大的结果？

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

此人给一个答案是 - 点更大：

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; 
}

我明白了为什么最后一个函数的工作原理，但仍然不知道前两者有什么问题。

答

您所拥有的第一段代码中的问题与其他问题密切相关，因此我们来关注它。这里是你的代码：

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

这里有几件事要注意。首先，将您的编译器警告设置调整到最大。您可能会看到几个警告：

你从来没有真正初始化count价值，所以当你回到count++，你返回一个垃圾值。这可能解释了为什么你会看到过多的人数。
如果您编写return count++;，则表示“增量为count，然后取其旧值 - 尚未递增 - 并将其返回”。这可能不是你想要做的。如果你想增加count，只需写count++。如果你想返回count + 1，只需写return count + 1;。
您编写的return语句会导致您的函数在进行递归调用之前退出 - 对countNode的调用永远不会触发。您可能需要重新对代码重新排序，或删除您使用return语句编写的代码来解决此问题。
你永远不会从countNode捕获返回值。请记住，每次拨打countNode都有自己的count版本，因此在一次递归调用中递增count不会触及其他版本的count。您将需要存储来自两次递归调用的返回值，这将返回左右子树中有多少个节点，并计算出您想如何将它们聚合在一起。

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

基于此，你可以看到其他不正确的实现中发生了什么，以及为什么你的最后一次实现是正确的？

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

相关推荐