对 n(n≥2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
哈夫曼树不一定是完全二叉树，A选项...
用户登录可进行刷题及查看答案
哈夫曼树不一定是完全二叉树，A选项错误。
哈夫曼树中只有度为 0 或 2 的结点，一定没有度为 1 的结点，B选项正确。
构造哈夫曼树时，先选出两个权值最小的结点进行构造，所以树中两个权值最小的结点一定是兄弟结点，C选项正确。
用反证法，如果哈夫曼树中某一非叶结点的下一层存在某一结点的权值大于该非叶结点的权值，则可以将两种进行替换使得这棵树的带权路径长度变得更低，由于哈夫曼树是带权路径最小的二叉树，矛盾。D选项正确。
本题选A。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发