问题
单项选择题
下面关于哈夫曼树的叙述中,正确的是()。
A.哈夫曼树一定是完全二叉树
B.哈夫曼树一定是平衡二叉树
C.哈夫曼树中权值最小的两个结点互为兄弟结点
D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
答案
参考答案:C
解析:
[要点解析] 哈夫曼树即最优二叉树,是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和,记为:
[*]
其中,n为带权叶子节点的数日,Wk为叶子节点的权值,lk为叶子节点到根的路径长度。则哈夫曼树是指权值为w1,w2…,wn的n个l1‘子节点的二叉树中带权路径长度最小的二叉树。
哈夫曼树与完全二叉树、平衡二叉树之间没有必然的联系。选项A、B中的说法是错误的。在哈夫曼树的构建中,由哈夫曼树的构造算法可知,哈夫曼树中权值最小的两个结点互为兄弟结点,根结点的权值为其左、右子树根结点的权值之和。