c - 递归函数的奇怪行为

Question

此函数必须计算二叉树中的节点数。树包含1000多个节点，递归调用的次数应该是一样的，但是变量'count'的值不大于10。为什么？我做错了什么？

int tree_depth(BST_T *tree) {
    static int count;
    count++;
    if(tree->left!=NULL) tree_depth(tree->left);
    else if(tree->right!=NULL) tree_depth(tree->right);
    return count;
}

Answer 1

总结评论，您的主要问题是else。摆脱它将使代码能够计算每个子树的两个分支。

另一个问题是，对于此类事情使用静态变量通常被认为是不好的做法。为什么不让每个调用都返回传递给它的子树中的节点数呢？这样你的代码是线程安全的，更正确的，而且更简单:

int tree_depth(const BST_T *tree)
{
    int  count = 1;

    if (tree == NULL)
        return 0;
    if (tree->left != NULL)
        count += tree_depth(tree->left);
    if (tree->right != NULL)
        count += tree_depth(tree->right);
    return count;
}

我还向树中添加了一个 const，因为您不会以任何方式修改树，而只是读取它。

还要注意病态树(即左链接全部为空或右链接全部为空的树，本质上只是一个链表而不是树树)，将导致 N 嵌套需要一个有 N 个节点的树。

附录

根据下面的一些评论对上面的代码进行了一些更正。我还添加了一个额外的检查来测试树指针本身是否为空。

此外，正如@twalberg 指出的那样，使用静态计数器将在第一次调用后的所有调用中失败，因为它不会在每次调用时重新初始化为零。完全摆脱它会使整个事情变得更简单，并且线程安全。