关于二叉树“外部节点数=内部节点数+1”性质的困惑

你混淆了性质里「外部节点」的定义——这条 |external nodes| = |internal nodes| + 1 的性质，对应的是扩展二叉树（补全二叉树）的定义，不是你理解的普通二叉树里的叶子节点。

具体来说：

• 这里的「内部节点」指原二叉树里的所有实际节点；
• 「外部节点」指为补全二叉树，给每个实际节点缺失的子节点补上的虚节点（即空指针对应的虚拟节点）。

拿你的示例树计算：
原树结构如下：

* (R)
 \
  \
   * (C)

补全成扩展二叉树后：

• R缺失左子节点，补上1个虚节点；
• C缺失左、右两个子节点，补上2个虚节点；
  此时外部节点共3个，内部实际节点是R和C（共2个），3 = 2 + 1，完全符合这条性质。

你最初的错误，是把性质里的「外部节点」当成了原树里的叶子节点（实际节点），这就和性质的定义不匹配了。

另外补充一条普通二叉树的通用性质：叶子节点数 = 有两个子节点的节点数 + 1，这条在你的示例里是成立的——叶子节点C是1个，有两个子节点的节点数是0，1 = 0 + 1，完全符合。

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