Question

为什么二叉树度为0的结点总比度为2的结点多1个，证明下！

Answer 1

对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。
因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：
n=n0+n1+n2
（1）
再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。
又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。
将此式代入上式，得：
n=n1+2n2+1
（2）
用（1）式减去（2）式，并经过调整后得到：n0=n2+1。