题8

题8

题目

下列关于哈夫曼树的说法中, 错误的是 ( ).
I. 哈夫曼树的结点总数不能是偶数
II. 哈夫曼树中度为 1 的结点数等于度为 2 和 0 的结点数之差
III. 哈夫曼树的带权路径长度等于其所有分支结点的权值之和
A. 仅 III
B. I 和 II
C. 仅 II
D. I、II 和 III

分析

哈夫曼树中没有度为1的结点，题7中做到过
每次都是两个结点合并作为新的子树的结点，下面是一个哈夫曼树的示范

解

C
个初始结点构造的哈夫曼树共新建 个双分支结点,因此哈夫曼树的结点总数是 , 是个奇数, I 错误。
哈夫曼树中没有度为 1 的结点, II 错误。
哈夫曼的带权路径长度有两种计算方法:
①所有叶结点的带权路径长度之和;
②所有分支结点的权值之和, III 正确。