Question

数据结构的题！！！

已知字符A、B、C、D、E、F、G的权值分别为3，5，6，8，10，12，18 要求：
（1）建立哈夫曼树
（2）计算出它的带权路径长度WPL
（3）写出七个字符的哈夫曼编码

Answer 1

(1)建立的哈夫曼树：

62
/ \
26 36
/ \ / \
F(12) 14 G(18) 18
/ \ / \
C(6) D(8) 8 E (10)
/ \
A(3) B(5)
(2) 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL，G F叶子结点路径长度为2，C D E为3，A B为4
WPL= （12+ 18）*2 + （6+8+10）*3 + (3+5)*4 = 164
(3) 根左边为0，右边为1，哈夫曼编码是
A:1100 B:1101 C: 010 D:011 E111 F:00 G:10