Question

数据结构问题C语言的

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

Answer 1

权值升序排列，下同
=>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.最小的两个权值7，8组一棵树，根节点权值为7+8=15
=>10* 10 15* 15 20 30
4.最小的两个权值10*，10组一棵树，根节点权值为10+10=20
=>15* 15 20* 20 30
5.最小的两个权值15*，15组一棵树，根节点权值为15+15=30
=>20* 20 30* 30
6.最小的两个权值20*，20组一棵树，根节点权值为20+20=40
=>30* 30 40*
7.最小的两个权值30*，30组一棵树，根节点权值为30+30=60
=>40* 60*
7.最小的两个权值40*，60*组一棵树，根节点权值为40+60=100
=>100* （一棵树，编码完成）
________/\
_______/__\
______/____\
_____/\_____/\
____/\_20__/\_30
___/\_10__/\_15
__/\_5___7_8
_2_3

WPL
=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)
=2*5+3*5+5*4+7*4+8*4+10*3+15*3+20*2+30*2
=280

左孩子前进0，右孩子前进1
A：001
B：01
C：0001
D：101
E：1001
F：00000
G：00001
H：1000
I：11

Answer 2

根据题中数据使用频率，采用哈弗曼编码，构成的二叉树如下：
哈弗曼编码思想核心就是将使用频率越高的数据编码长度越短，是一种变长（即各字符码值长度不一定相等）编码方式。构造平均长度最短的编码。
_________________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

Answer 3

树我学过,但学不好,现在重新学,抱歉,目前帮不了你

Answer 4

我知道你不是神