2. 计算机
  3. 若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。

若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。

admin2015-06-03  61
问题 若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。
选项 A、5
B、6
C、7
D、8
答案C
解析 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。
    假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，…， wn，则哈夫曼树的构造规则如下。
    (1)将w1，w2，…，wn看成是有n棵树的森林(每棵树仅有一个结点)。
    (2)在森林中选出两个根结点的权值最小的树，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和。
    (3)从森林中删除选取的两棵树，并将新树加入森林。
    (4)重复第(2)和第(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。
    从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支结点。设二叉树的0度结点(即叶子结点)个数为n0，2度结点个数为n2，则树的总结点数n=n0+n2。
又因为二叉树有性质：对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。所以n=n2+1+n2。即13=n2+1+n2，n2=6，n0=7。
转载请注明原文地址:https://kaotiyun.com/show/G3RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)