递归函数的奇怪行为

user3131972 发表于 Dev

用户3131972

此函数必须计算二叉树中的节点数。Tree包含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;
}

大卫·R·特里布尔

总结评论，您的主要问题是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所指出的，使用静态计数器将在第一次调用之后的所有调用上失败，因为它不会在每次调用时都重新初始化为零。完全摆脱它可以使整个过程更简单，并且线程安全。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。