C中BST中的节点数

Question

int numOfNodes(struct node* rootPtr){
    if(rootPtr== NULL) return 0;

    int r = numOfNodes(rootPtr->right);
    int l = numOfNodes(rootPtr->left);
    return r+l+1; 
}

有人可以向我解释这是如何工作的吗？递归对我来说有点混乱，因为我才刚刚开始。我了解此+1是针对根节点的，但我不了解r和l如何增加。

Answer 1

让我们看一下这棵简单的树：

  Root
 / \
A   B
   / \
  C   D

然后调用和返回如下：

numOfNodes( Root )  
    numOfNodes(B)
        numOfNodes(D)
        return 1
        numOfNodes(C)
        return 1
    return 3    
    numOfNodes(A)
    return 1
return 5

Answer 2

让我们逐步使用一些示例树来运行您的代码，变得越来越复杂。

第一个示例：空树

这是一种边缘情况。如果树为空，则其根节点为NULL，可以看到该函数将立即返回0，这是正确的结果。

第二个例子：一个节点的树

在这种情况下，我们的树只是单个根节点，我们将其称为“ A”。树的结构如下所示：

     (A)
  /       \
NULL     NULL

我们使用NULL指针作为叶子来标记根节点没有子节点。让我们继续进行函数调用。

• 您以numOfNodes作为参数调用A。>>
• 首先，我们检查参数是否不是NULL，情况并非如此，因此我们继续。
• 然后我们以numOfNodes作为参数调用A->right。
  • 我们输入another
  numOfNodes功能，这次用rootNode = A->right
  • 事实证明A->right是NULL。因此，此对numOfNodes的调用不会超过第一个if并返回0。
• 我们返回对numOfNodes的初始调用，其中r现在的值为0。

然后我们第三次调用numOfNodes，这次以rootNode = A->left作为参数。

• 类似地，此对numOfNodes的调用会立即返回0，因为A->left为NULL。

我们返回对numOfNodes的初始调用，其中l现在的值为0

我们现在可以返回最终结果：左侧的节点数（0），右侧的节点数（0）加上我们当前的节点数（1）。总计r+l+1 = 1，这是正确的结果>

您可能已经注意到，在执行过程中该函数称为自身的另一个版本，但与最初调用时使用的参数不同。这个想法是一种非常强大的编程技术，称为recursion，在处理树时特别有用。

本质上，您从树的根开始，要求它计算右边的节点数和左边的节点数，然后加一。知道其右边的节点数非常简单。您使用相同的功能好像右边的节点是新树的根。这可能导致越来越多的人调用相同的计数函数，每次以更深的节点作为“伪根”。级联呼叫到达NULL节点时停止。最终，当每个函数返回到调用它的函数时，结果在树上“浮动”。

第三示例：更完整的树

让我们现在有了带有更多节点的二叉树。假设我们有一棵高3：

        __(A)__
     /          \ 
    (B)         (C)
   /   \       /   \
 NULL  (D)   NULL  NULL
      /   \             
    NULL  NULL

• 我们首先在树的根上调用numOfNodes，即A。 A不是NULL，所以我们继续。
• 我们以numOfNodes作为参数调用A->right。>>
• 因此，我们以numOfNodes作为参数输入A->right的另一个版本（＃2）。事实证明A->right是C，而不是NULL。此版本的numOfNodes不会立即返回0。
• 我们将以numOfNodes作为参数，输入C->right的第三版
。
• 事实证明C->right是NULL，所以numOfNodes的此版本（＃3）返回0
• 因此第二版r中的numOfNodes变量现在具有值0
• 我们计算l变量时会发生相同的事情，因为C->left也是NULL。
• numOfNodes的第二个版本，用C调用的版本，到达其最终指令并返回r+l+1，该值等于0+0+1=1（左侧为0个节点，右侧为0个节点，再加上“假根” [C）。
• 然后我们回到first
numOfNodes，因为我们现在知道r为1。
• 我们现在将为此版本计算l。为此，我们将再次调用numOfNodes，这一次以A->left（即B）作为参数。
• [我不会详细介绍（我鼓励您在纸上做它，这一次我们将再叫numOfNodes四次，并且计算出l等于2。
• 因此，总结果为4（右侧有1个节点，左侧有2个节点，再加上根节点）。