计算机三级
如果对于给定的一组数值，所构造出的二叉树的带权路径长度最小，则该树称为【 】。
题目
如果对于给定的一组数值，所构造出的二叉树的带权路径长度最小，则该树称为【 】。
参考答案和解析
哈夫曼树或最优二叉树 解析：扩充二叉树：当二叉树里出现空的子树时，就增加新的特殊的结点——外部结点。对于原来的二叉树中度为1的分支结点，在它下面增加一个外部结点：对于原来二叉树的树叶，在它下面增加两个外部结点。哈夫曼树：利用哈夫曼算法构造的具有最小带权外部路径长度的扩充二叉树，即所构造的二叉树对于给定的权值，带权路径长度最小。由哈夫曼树的构成，我们得知，题意所给条件完全符合哈夫曼树。
相似问题和答案
第1题：
2、哈夫曼树是树的带权路径长度最小的二叉树
第2题：
如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。
A平衡二叉树
B完全二叉树
C二叉树
D哈夫曼树
D
略
第3题：
对于给出一组权w={5，6，8，12)，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为______。
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。
第4题：
A、二叉树
B、平衡二叉树
C、哈夫曼树
D、完全二叉树
第5题：
A.平衡二叉树
B.完全二叉树
C.二叉树
D.哈夫曼树
第6题：
对于一组给定权值所构造的霍夫曼树的形状有可能不同，它们的带权外部路径长度__________。
相同
对于同一组给定的叶结点所构造的霍夫曼树，树的形状可能不同，但带权外部路径的长度值却是相同的，并且一定是最小值。
第7题：
如果对于给定的一组数值，所构造出的--X树的带权路径长度最小，则该树称为【 】。
哈夫曼树(或最优二叉树) 解析：扩充二叉树概念：当二叉树里出现空的子树时，就增加新的特殊的结点——外部结点。对于原来的二叉树中度为1的分支结点，在它下面增加一个外部结点；对于原来二叉树的树叶，在它下面增加两个外部结点。哈夫曼树构成：利用哈夫曼算法构造的具有最小带权外部路径长度的扩充二叉树，即所构造的二叉树对于给定的权值，带权路径长度最小。由哈夫曼树的构成我们得知，题意所给条件完全符合哈夫曼树。
第8题：
对于给出一组权W={2，4，5，9}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为__________。
37
按照霍夫曼树构造的方法构造一棵带权的扩充二叉树，此扩充二叉树的带权外部路径长度为9×1+5×2+(2+4)×3=37。
第9题：
对于给出的一组权 w = ，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 （ ） 。
61