点击蓝字
带你一起上岸
羊驼小课堂
数据结构DAY14
对n（n≥2）个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中，
错误的是______。
A.3
该树一定是一棵完全二叉树
B.4
树中一定没有度为1的结点
C
树中两个权值最小的结点一定是兄弟结点
D
树中任一非叶结点的权值一定不小于下一层任一结点的权值
点击空白处查看答案
选A
考查哈弗曼树的特性。
哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为１的结点，B正确；
构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；
哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
视频解析
点击边框调出视频工具条计算机考研羊驼