该函数如何计算树中节点的数量？

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

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

Answer 3

首先，你自己试过了吗？

基本上，它为每个非零节点加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)，因为节点0不为空，它关系到return语句是： return 1 + count(left) + count(right)。您需要了解一个基本的事情，即您的递归函数中的某个操作只发生在其他操作之后。换句话说，直到操作count(left)完成后才会发生操作count(right)。现在看看你在那里的return语句，并根据上面的树翻译它。这将是1+count(Node1)+count(Node2)。所以count(Node2)在count(Node1)完成之前没有得到计算。因此，对于count(Node1)，count函数将以Node1作为参数被调用（再次）。因此，现在让我们忘掉半计算表达式1+count(Node1)+count(Node2)（我们稍后再回来）。

现在对于count(Node1)，Node1不是NULL，因此进入return语句。这将（再次）是1+count(left)+count(right)。但是等一下，Node1没有左右节点。因此，当count(left)被调用的参数为NULL时，它将返回0，并且count(right)也会发生同样的情况。所以count(Node1)的表达式变成1 + 0 + 0。没有更多的计数函数被调用Node1，因此它返回到它的原始调用者，这是返回语句count(Node0)。

由于我们有count(Node1)想通了，我们用count(Node0)的返回语句替换它。现在变成1 + (1 + 0 + 0) + count(Node2)。

现在我打算让这个更快一点。由于Node2有两个子节点，Node2的return语句将为1 + count(Node3) + count(Node4)。就像Node1,count(Node3)和count(Node4)将分别返回1 + 0 + 0，将count(Node2)的返回语句变为1 + (1 + 0 + 0) + (1 + 0 + 0)。

现在count(Node2)已完全计算，让我们回归到count(Node2)原始调用者，这是1 + (1 + 0 + 0) + count(Node2)。替换我们从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 4

考虑这些树：

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

与一个节点，根树。这将调用：

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

与左，右NULL，因此将返回1 + 0 + 0

一棵树，根和一个右叶

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

将返回1 （根据上述规则）的树根为0，树根为1的根（按上述规则），即1 + 0 + 1

依此类推。

Answer 5

To understand recursion, you must first understand recursion.