题7
题目
Q:以下对于哈夫曼树的说法中, 错误的是
A. 对应一组权值构造出来的哈夫曼树一般不是唯一的
B. 哈夫曼树具有最小的带权路径长度
C. 哈夫曼树中没有度为 1 的结点
D. 哈夫曼树中除了度为 1 的结点, 还有度为 2 的结点和叶结点
分析
A:注意把哈夫曼树和完全二叉树区分开来
解
D
哈夫曼树通常是指带权路径长度达到最小的扩充二叉树, 在其构造过程中每次选根的权值最小的两棵树, 一棵作为左子树, 一棵作为右子树, 生成新的二叉树, 新的二叉树根的权值应为其左右两棵子树根结点权值的和。
至于谁做左子树, 谁做右子树, 没有限制, 所以构造的哈夫曼树是不唯一的。
哈夫曼树只有度为 0 和 2 的结点, 度为 0 的结点是外结点, 带有权值, 没有度为 1 的结点。