设一棵树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点为

admin2013-05-15  29

问题 设一棵树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点为

选项 A、8
B、7
C、6
D、5

答案1

解析 设这棵树中叶子结点数为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。
转载请注明原文地址:https://kaotiyun.com/show/ioop777K
0

最新回复(0)