这个函数如何计算树中的节点数？

Question

计算树中节点数量的函数。

int count(node *t)
{    
    int i;  
    if (t == NULL)         
        return(0);  
    i = 1 + count(t->left) + count(t->right); // recursion occurs address of left node is passed and 
    return(i);                                // continue to pass until whole left node
}                                             // is traversed and the value of t is
                                              // NULL and 0 is returned same for right node counting
                                              // i = 1 + 0 + 0 = 1

节点数是如何计算的？

Answer 1

要了解递归，你必须首先了解递归。

Answer 2

这是计算树节点的递归实现。它针对根节点进行调用，并返回“左子树中的节点数加上右子树中的节点数”，这是递归完成的，直到到达叶节点。

Answer 3

总计数包括当前/根节点加上左分支的计数加上右分支的计数。您的哨兵是 NULL，这意味着您已到达当前正在计数的任何分支的叶节点。然后你就放松下来。递归 ：）

Answer 4

首先，你自己尝试过吗？

基本上，它为每个非空节点加 1。大致如下：1 + number_of_nodes_to_the_left + number_of_nodes_to_the_right。其扩展为：1+(1+number_of_nodes_to_the_left_in_left+number_of_nodes_to_the_right_in_left) + (1+number_of_nodes_to_the_left_in_right + number_of_nodes_to_the_right_in_right)。继续扩展，您会发现树中的每个非空节点基本上都是 1 + 1 + 1 +....。

编辑：为了更好地说明这一点，请考虑以下树：

     Node0
       |
(left) |  (right)
Node1 _|_ Node2
            |
     (left) |  (right)
     Node3 _|_ Node4

当您执行 int node_count = count(Node0) 时，由于 Node0 不为 NULL，因此它会转到 return 语句，其中是：
返回 1 + 计数（左）+ 计数（右）。您需要了解一件基本的事情，即递归函数中的每个操作都是相继发生的。换句话说，直到操作 count(left) 之前，操作 count(right) 才会发生) 已完成。现在看一下那里的 return 语句，并根据上面的树进行翻译。它将是1+count(Node1)+count(Node2)。因此，在 count(Node1) 完成之前不会计算 count(Node2)。因此，对于 count(Node1)，将再次以 Node1 作为参数调用 count 函数。现在，让我们暂时忘记半计算表达式 1+count(Node1)+count(Node2) （我们稍后会再讨论它）。

现在，对于 count(Node1)，Node1 不为 NULL，因此继续执行 return 语句。这将（再次）是1+count(left)+count(right)。但是等等，Node1 没有左节点和右节点。因此，当以 NULL 参数调用 count(left) 时，它会返回 0，count(right) 也会发生同样的情况。因此，count(Node1) 的表达式变为 1 + 0 + 0。不再为 Node1 调用计数函数，因此它返回到其原始调用者，即count(Node0)的返回语句。

既然我们已经计算出了 count(Node1)，那么让我们将其替换为 count(Node0) 的 return 语句。现在变为 1 + (1 + 0 + 0) + count(Node2)。

现在我要让它更快一点。由于 Node2 有两个子节点，因此 Node2 的返回语句将为 1 + count(Node3) + count(Node4)。就像 Node1 一样，count(Node3) 和 count(Node4) 将分别返回 1 + 0 + 0，从而改变 return 语句count(Node2) 为 1 + (1 + 0 + 0) + (1 + 0 + 0)。

现在 count(Node2) 已完全计算完毕，让我们返回到 count(Node2) 的原始调用者，即 1 + (1 + 0 + 0) + 计数（节点2）。替换我们从 count(Node2) 得到的内容，我们得到 1 + (1+0+0) + (1 + (1+0+0) + (1+0+ 0））。将其相加，我们得到 5 的值。 此值将返回给调用 count(Node0) 的函数，例如语句 int node_count = count(Node0) 和 node_count 的值为 5。

Answer 5

考虑这些树：

一棵没有节点的树（即 NULL 指针） - 返回 0

一棵只有一个节点（即根）的树。这将调用：

 i=1+count(t->left)+count(t->right);

with left 和 right NULL，因此将返回 1 + 0 + 0

具有根和单个右叶的树

 i=1+count(t->left)+count(t->right);

将返回 1 表示根，0 表示以左侧为根的树（根据上述规则），并且1 表示以右侧为根的树（根据上述规则），即 1 + 0 + 1

等等。