此函数如何计算二叉树中的节点数

Question

我有一个函数，我正在尝试分析它的输出是 7:

给定这段代码：

int func_1(struct node* node)
{
    if (node == NULL)
        return 0;
    else
        return func_1(node->left) + 1 + func_1(node->right);
}

这个二叉搜索树：

return 值为 7。

我知道递归，它在这里有点简单，我试着跟进，但我不明白它是如何做到的 returned 7. 我计算它只是向左，向左，然后一次向右，然后而已。这将 return 3。即使它正确地进行了 3 次，在根之后，它仍然是 return 6 而不是 7.

你们能帮帮我吗？

Answer 1

看看叶节点7。

当用节点 7 的值调用 func_1 时，if 语句将分支到 else 部分，因为指向该节点的指针是有效的。

然后 func_1 将被调用两次，一次用于左侧 child，一次用于右侧 child。在这两种情况下函数 return 0，因为左和右 child 是 NULL。该函数将 return 1:

return func_1(node->left) + 1 + func_1(node->right);

相当于：

return func_1(NULL) + 1 + func_1(NULL);

变为：

return 0 + 1 + 0;

Answer 2

看看这个说法

return func_1(node->left) + 1 + func_1(node->right);
                          ^^^^^

如果一个节点不等于NULL，它会计算自己加上相对于该节点的左右子树中的节点数。

所以你会得到一个等于不等于NULL的节点个数的结果。

Answer 3

从语义上讲，它需要左节点数 + 1（当前节点）+ 右节点数。

with func_1(x) 我的意思是调用该特定节点上的函数。

所以完整的计算是

func_1(8) + 1 + func_1(14)
(func_1(7) + 1 + func_1(9)) + 1 + func_1(14)
(1 + 1 + 1) + 1 + (0 + 1 + func_1(17)
3 + 1 + (0 + 1 + (0 + 1 + func_1(18))
3 + 1 + (1 + (1 + (0 + 1 + 0)
结果 7

这个原则在递归中用的很频繁：

How does this function compute the number of nodes in binary tree