哪位好人帮我做下这题5、在一棵二叉树中,度数为2的结点数等于n2,度数为1的结点数等于n1,那么度数为0的结点数等于是.A.n1+1B.n1+2C.n2+1D.n2+2

Question

哪位好人帮我做下这题
5、在一棵二叉树中,度数为2的结点数等于n2,度数为1的结点数等于n1,那么度数为0的结点数等于是_______.
A.n1+1 B.n1+2 C.n2+1 D.n2+2

Answer 1

C
性质：对于一棵非空的二叉树,如果叶子结点数为n0,度数为2 的结点数为n2,则有:
n0＝n2＋1.
证明:
设n 为二叉树的结点总数,n1 为二叉树中度为1 的结点数,则有：
n＝n0＋n1＋n2 （6-1）
在二叉树中,除根结点外,其余结点都有唯一的一个进入分支.设B 为二叉树中的分支数,那么有：
B＝n－1 （6-2）
这些分支是由度为1 和度为2 的结点发出的,一个度为1 的结点发出一个分支,一个度为2 的结点发出两个分支,所以有：
B＝n1＋2n2 （6-3）
综合（6-1）、（6-2）、（6-3）式可以得到：
n0＝n2＋1