在任意一棵二叉树中,度为0的结点（即叶子结点）总是比度为2的结点多一个?

Question

在任意一棵二叉树中,度为0的结点（即叶子结点）总是比度为2的结点多一个?

Answer 1

我说说我的理解哈度为零的结点,即D、E、F三个结点嘛.度为2的结点有A、B两个结点.所以说度为0的结点（即叶子结点）总是比度为2的结点多一个.设叶子的结点数是n0,度为1的结点数是n1,度为2的结点数是n2,则结点数是n0+n1+n2;其次,所有结点也等于度为1结点数(即n1)与度为2结点数（即n2）的2倍再加1(这个是树的性质,即树中结点数等于所有节点的度数加1).即n0+n1+n2=n1+2n2+1.解得n0=n2+1.再解释为什么是2倍呢?为什么加1?拿树中根节点（即A）来说,必有度数等于它下面的结点数,即B、C两结点.而n2指的是度为2结点的个数,现在需要的是它的度数,即2n2.再考虑所有节点后,再算上根结点本身,所以再加1.