单选题如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。A 平衡二叉树B 完全二叉树C 二叉树D 哈夫曼树

正确答案：哈夫曼树(或最优二叉树)
哈夫曼树(或最优二叉树) 解析：扩充二叉树概念：当二叉树里出现空的子树时，就增加新的特殊的结点——外部结点。对于原来的二叉树中度为1的分支结点，在它下面增加一个外部结点；对于原来二叉树的树叶，在它下面增加两个外部结点。哈夫曼树构成：利用哈夫曼算法构造的具有最小带权外部路径长度的扩充二叉树，即所构造的二叉树对于给定的权值，带权路径长度最小。由哈夫曼树的构成我们得知，题意所给条件完全符合哈夫曼树。

正确答案：112
112 解析：首先选出7和11构造为内部结点，权值为18，再与18构造一个内部结点36，最后与22构造根结点58。带权外部路径长度为(7+11)*3+18*2+22=112。

正确答案：

正确答案：C
解析：本题考查带权哈夫曼树的构造及求带权路径长度。树的路径长度是从树根到树中每一结点的路径长度之和，结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶结点的带权路径长度之和，称为树的带权路径长度。在权为w1，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，…，wn，则哈夫曼树的构造规则为：(1)将w1，w2，…，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林。重复第(2)步和第(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。根据哈夫曼树的构造规则，不难得到题目中给出叶子结点对应的哈夫曼树，得到哈夫曼树后我们再计算带权路径长度=3×(3+4)+2×(5+6+8)=59。

参考答案：正确

正确答案：
相同
对于同一组给定的叶结点所构造的霍夫曼树，树的形状可能不同，但带权外部路径的长度值却是相同的，并且一定是最小值。

参考答案：C

正确答案：
37
按照霍夫曼树构造的方法构造一棵带权的扩充二叉树，此扩充二叉树的带权外部路径长度为9×1+5×2+(2+4)×3=37。

正确答案：哈夫曼树或最优二叉树
哈夫曼树或最优二叉树 解析：扩充二叉树：当二叉树里出现空的子树时，就增加新的特殊的结点——外部结点。对于原来的二叉树中度为1的分支结点，在它下面增加一个外部结点：对于原来二叉树的树叶，在它下面增加两个外部结点。哈夫曼树：利用哈夫曼算法构造的具有最小带权外部路径长度的扩充二叉树，即所构造的二叉树对于给定的权值，带权路径长度最小。由哈夫曼树的构成，我们得知，题意所给条件完全符合哈夫曼树。