对于一组给定权值所构造的霍夫曼树的形状有可能不同，它们的带权外部路径长度__________。
题目
对于一组给定权值所构造的霍夫曼树的形状有可能不同，它们的带权外部路径长度__________。
相似考题
参考答案和解析
正确答案：
相同
对于同一组给定的叶结点所构造的霍夫曼树，树的形状可能不同，但带权外部路径的长度值却是相同的，并且一定是最小值。
相同
对于同一组给定的叶结点所构造的霍夫曼树，树的形状可能不同，但带权外部路径的长度值却是相同的，并且一定是最小值。
更多“对于一组给定权值所构造的霍夫曼树的形状有可能不同,它们的带权外部路径长度__________ ”相关问题
-
第1题：
对于给出的一组权w={7，11，18，22}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 ______。
正确答案：112
112 解析：首先选出7和11构造为内部结点，权值为18，再与18构造一个内部结点36，最后与22构造根结点58。带权外部路径长度为(7+11)*3+18*2+22=112。 -
第2题：
如果对于给定的一组数值，所构造出的二叉树的带权路径长度最小，则该树称为【 】。
正确答案：哈夫曼树或最优二叉树
哈夫曼树或最优二叉树 解析：扩充二叉树：当二叉树里出现空的子树时，就增加新的特殊的结点——外部结点。对于原来的二叉树中度为1的分支结点，在它下面增加一个外部结点：对于原来二叉树的树叶，在它下面增加两个外部结点。哈夫曼树：利用哈夫曼算法构造的具有最小带权外部路径长度的扩充二叉树，即所构造的二叉树对于给定的权值，带权路径长度最小。由哈夫曼树的构成，我们得知，题意所给条件完全符合哈夫曼树。 -
第3题：
对于给出的一组权w=｛5, 6，8，12｝，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 【】 。
正确答案：61
（5+6）*3+8*2+12=61. -
第4题：
对于给出一组权w={5，6，8，12)，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为______。
正确答案：61
61 解析：霍夫曼算法给出了求扩充二叉树的具有最小带权外部路经的方法：首先找出两个最小的wi值，不妨设为w1、w2，然后对m-1个权(w1+w2，w3，…)来求解这个问题，并且将这个解中的结点(w1+w2)用下图来代替，如此下去，直到所有的w都成为外部结点。
对本题中的W={5，6，8，12}，我们不妨写出其序列：
因此其扩展二叉树参见下图。
因此我们可以计算出扩充二叉树的具有最小带权外部路长度12*1+8*2+5*3+6*3=61。 -
第5题：
对于给出的一组权W={2，3，4，7，8，9}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为【 】。
正确答案：80
80 解析：用霍夫曼算法求具有最小带权外部路径长度的扩充二叉树的办法是：首先找出两个最小的wi值，不妨设为w1和w2，然后对m-1个权w1+w2，w3，…，wm来求解这个问题，并且将这个解中的结点用权值代替，如此进行下去，直到所有的w都成为外部结点的权。根据条件构造哈夫曼树如下：树的带权路径长度为WPL=7×2+8×2+4×3+2×4+3×4+9×2=80。