问题
单项选择题
在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为
A.4
B.5
C.6
D.7
答案
参考答案:C
解析:
[分析] 设这棵树中叶子结点数为n0,度数为 1的结点数为n1,度数为2的结点数为n2,度数为3的结点数为n3,总结点数为n,则
n=n0+n1+n2+n3 (1)
设树的总入度为m。由于在树中除了根结点外,其余每一个结点都有唯一的一个分支进入,则树的总结点数为
n=m+1 (2)
又由于树中这m个进入分支分别由非叶子结点射出,其中度数为1的结点射出1,度数为2的结点射出2,度数为3的结点射出3。而且射出分支总数与总的进入分支数相等,即
m=n1+2n2+3n3 (3)
由式(1)、(2)、(3)可以得到n0=n2+2n3+1=1+2×2+1=6。