2. 考研
  3. 由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为( )。

由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为( )。

admin2019-05-10  21
问题 由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为(    )。
选项 A、23
B、37
C、44
D、46
答案C
解析 由权值为9、2、5、7的四个叶子构造的哈夫曼树可如下图所示。

该树的带权路径长度＝9×1＋7×2＋2×3＋5×3＝44。
  [归纳总结]对哈夫曼树特征的总结：
    (1)用n个权值(对应n个叶子结点)构造哈夫曼树，共需要n－1次合并，即哈夫曼树中非叶子结点的总数为n－1，总结点个数为2n－1。
    (2)哈夫曼树中没有度为1的结点，因为非叶子结点都是通过两个结点合并而来。但是，没有度为1的二叉树并不一定是哈夫曼树。
    (3)用n个权值(对应n个叶子结点)构造的哈夫曼树，形态并不是唯一的。
    建立哈夫曼树的过程中有以下三种常见的错误：
    (1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的)，而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。
    (2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。
    (3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。
转载请注明原文地址:https://kaotiyun.com/show/L2Ci777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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