c - 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 是如何增加的。

标签： cbinary-search-tree

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