证明：练习4.4：<mark>N个节点的二叉树，存在N+1个null节点</mark>

令：N = 节点个数

  • 每个非根节点，都有父节点：

令：F = （需要的）父节点个数

  • F = N-1
  • F 也可以理解为：“全部节点中，有子节点的边数”

所以：null节点数 = 2 * N - F = N + 1

证明：练习4.6：<mark>二叉树的满节点（full node）个数加一等于非空二叉树的树叶的个数</mark>

二叉树节点有三种情况

  • 没有子节点 =》 树叶 =》 令个数为 L
  • 一个子节点 =》 令个数为 A
  • 两个子节点 =》 满节点 =》 令个数为 B

总共的节点个数：<mark>N=L+A+B</mark>

<mstyle mathcolor="&#35;ff0011"> 证 明 ： L = B + 1 </mstyle> \color{#ff0011}{证明：L = B + 1 } 证明：L=B+1
根据上面的证明4.4

知道有N+1个null节点
其中，一个树叶提供两个null节点，有一个子节点的节点提供一个null节点
所以，A + 2L = N + 1
所以，<mark>A = N + 1 - 2L</mark>

上面的结论<mark>A = N + 1 - 2L</mark>代入 <mark>N=L+A+B</mark>
得到： <mstyle mathcolor="&#35;064f3f"> N = L + N + 1 − 2 L + B </mstyle> \color{#064f3f}{N = L + N + 1 - 2L + B } N=L+N+1−2L+B
化简之后，就是结论： <mstyle mathcolor="&#35;ff0011"> L = B + 1 </mstyle> \color{#ff0011}{L = B + 1 } L=B+1