如何证明任意结构的n节点二叉树都存在n+1个NULL指针

你可以用以下几种常见且严谨的方法证明该结论：

方法1：总指针扣除法 #

这是最直接的推导方式：

• n个节点的二叉树每个节点自带2个指针域（左孩子、右孩子），总指针数量固定为2n
• 除根节点外，每个节点都恰好被1个父节点的指针指向，因此非空指针的总数等于树的边数，也就是n-1
• 空指针数量 = 总指针数 - 非空指针数 = 2n - (n-1) = n+1
  代入n=100的情况，可得空指针数为2*100 - 99 = 101，结论成立。

方法2：数学归纳法 #

• 基例验证：当n=1时，二叉树只有1个根节点，左右指针均为空，空指针数为2，符合1+1=2的结论
• 归纳假设：假设任意包含k个节点的二叉树，空指针数均为k+1
• 归纳推导：当节点数为k+1时，可将树拆分为根节点、a个节点的左子树、b个节点的右子树，满足a + b = k。根据归纳假设，左子树空指针数为a+1，右子树空指针数为b+1，总空指针数为(a+1)+(b+1) = a+b+2 = k+2 = (k+1)+1，符合n=k+1时的结论
  因此所有规模的二叉树都满足空指针数为n+1，n=100时结果为101。

方法3：扩展二叉树性质推导 #

将二叉树的所有空指针替换为虚拟的空节点，得到的扩展二叉树属于满二叉树（所有非叶子节点都有两个子节点，空节点为叶子节点）：

• 扩展二叉树的内部节点就是原二叉树的n个真实节点，叶子节点就是我们要计数的空指针对应的虚拟节点，设为x
• 根据满二叉树的性质：满二叉树的叶子节点数 = 内部节点数 + 1，因此直接可得x = n + 1
  代入n=100可得x=101，结论成立。

内容的提问来源于stack exchange，提问作者Mersock