2. 公务员
  3. 设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。

设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。

admin2013-12-15  74
问题 设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。
选项
答案带权路径长度最小的树是赫夫曼树。构造赫夫曼树的步骤如下： (1)根据给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn)，最初每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树为空。 (2)在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4)重复(2)和(3)，直到F只含一棵树为止。这棵树便是赫夫曼树。 本题中构造的赫夫曼树如下。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/u0al777K
本试题收录于： 计算机专业知识题库事业单位考试分类
0

计算机专业知识

事业单位考试

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