试题出自试卷《02331《数据结构》真题及答案解析（2020.10）》

问题1选项
A.哈夫曼树是叶结点权值之和最小的二叉树
B.哈夫曼树是带权路径长度WPL最小的二叉树
C.n个带有权值的结点可以构造出唯一一棵哈夫曼树
D.哈夫曼树是有n个叶结点的二叉树中高度最低的二叉树

B

【考点】本题考查树和二叉树-哈夫曼树及其应用-最优二叉树的概念
【解析】在许多应用中，常常将树中的结点附上一个具有某种意义的实数，我们称此实数为该结点的权。而从树根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树中所有叶子结点的带权路径长度之和称为树的带权路径长度。在权值为w1，w2，……，wn的n个叶结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。故本题选B。
【希赛点拨】由哈夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树，这是第一步；将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树，这是第二步；每合并一次就产生一个新结点，森林中相应减少一棵树。显然要进行n-1次合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支支结点。由此可知，最终求得的哈夫曼树中一共有2n-1个结点。