问题 单项选择题

下面关于哈夫曼树的叙述中,正确的是()。

A.哈夫曼树一定是完全二叉树

B.哈夫曼树一定是平衡二叉树

C.哈夫曼树中权值最小的两个结点互为兄弟结点

D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点

答案

参考答案:C

解析:

[要点解析] 哈夫曼树即最优二叉树,是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和,记为:

[*]

其中,n为带权叶子节点的数日,Wk为叶子节点的权值,lk为叶子节点到根的路径长度。则哈夫曼树是指权值为w1,w2…,wn的n个l1‘子节点的二叉树中带权路径长度最小的二叉树。

哈夫曼树与完全二叉树、平衡二叉树之间没有必然的联系。选项A、B中的说法是错误的。在哈夫曼树的构建中,由哈夫曼树的构造算法可知,哈夫曼树中权值最小的两个结点互为兄弟结点,根结点的权值为其左、右子树根结点的权值之和。

填空题
问答题 简答题