数据结构问题C语言的

来源：百度知道 编辑：UC知道 时间：2024/06/21 16:36:11
假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求：
（1）设计一棵哈夫曼树；
（2）计算其带权路径长度WPL；
（3）写出每个字符的哈夫曼编码

根据题中数据使用频率，采用哈弗曼编码，构成的二叉树如下：
哈弗曼编码思想核心就是将使用频率越高的数据编码长度越短，是一种变长（即各字符码值长度不一定相等）编码方式。构造平均长度最短的编码。
_________________100
________________/____\
______________40______60
_____________/__\____/__\
________ (B)20___20__30___30___(左侧30也即叶子结点的是I)
_______________/__\_____/__\
__________(A)10___10___15___15___(左侧15是D)
_________________/__\______/__\
_____________(C)5___5_____7(H)_8(E)
___________________/__\
_______________(F)2____3(G)
根节点编码为1；将树中左孩子结点编码为0，右孩子结点编码为1，依次编码直至到叶结点。
则各字符编码值分别为：
B：100
I：110
A：1010
D：1110
C：10110
H：11110
E：11111
F：101110
G：101111
树的带全路径长度(等于各叶节点的带权路径长度之和)：
=(2+3)x5+(7+8+5)x4+(15+10)x3+(20+30)x2
=25+80+75+100
=280

权值升序排列，下同
=>2 3 5 7 8 10 15 20 30
1.最小的两个权值2，3组一棵树，根节点权值为2+3=5
=>5* 5 7 8 10 15 20 30
2.最小的两个权值5，5组一棵树，根节点权值为5+5=10
=>7 8 10* 10 15 20 30
3.最小的