关于二叉树的性质

Question

对任何一颗二叉树，如果其叶结点有N个，度为2的非叶结点有M个，则有N=M+1。此话正确与否？何解？

Answer 1

元芳，CSDN新论坛上线！你怎么看？

Answer 2

此话正确。证明如下：
（1）设一棵非空的二叉树有n个节点，度数为1的节点的个数为N1,因为二叉树中所有节点的度都不大于2，所以有：n = N1+N+M(1式)(叶节点个数+度数为1的节点个数+度数为2的节点的个数)；
（2）二叉树中，除了根节点以外，其余每一个节点有且仅有一个前驱，假设边的总数为B,则有B = n-1（2式）（可以任意画一颗二叉树验证一下）；
（3）二叉树中的边都是由度为1或者度为2的节点发出的，故有：B = N1 + 2N（3式）。
由上面的三个式子得：N = M + 1.

Answer 3

楼上不错，不过第三式手误了，=> B = N1 + 2M