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