证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1

Question

证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1

Answer 1

证明：
假设n(i)表示度为i的结点,如n(0)表示叶子结点,n(2)表示既有左孩子也有右孩子的结点.
n表示二叉树的所有结点数.
有(1)式：
n = n(0) + n(1) + n(2) (1)
除了根结点外,所有结点都有一条分支指向它,有(2)式
分支数 = n - 1 (2)
分支只能由度为1和度为2的结点发出,并且度为2的结点发出2条分支,有(3)式
分支数 = n(1) * 1 + n(2) *2 (3)
合并(2)、(3)式,得(4)式
n - 1 = n(1) + 2 * n(2) (4)
由(1)减去(4),得(5)式
1 = n(0) - n(2) (5)
变化(5)式,得(6)式
n(0) = n(2) + 1 (6)
即证.