已知字符集{a,b,c,d}的权值集合为{7,5,1,2},构造哈夫曼树,并求出字符集的哈夫
发布网友
发布时间：2022-05-30 17:43
共3个回答
热心网友
时间：2023-10-23 20:49
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；从森林中删除选取的两棵树，并将新树加入森林。
树的路径长度是从树根到每一结点的路径长度之和；
WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。
A-B合并（权5）
A-B再和C合并（权10）
D-E合并（权16）
（A-B）-C再和F合并（权21）
最后((A-B)-C)-F再和D-E合并（权37）
总之是找两个最小的结点合并，生成的新节点权为两个结点权之和。
平均路径长度为（2×3+3×3+5×2+7×1+9×1+12×1）/6=53/6约等于8.8
各字符Huffman编码可以为：A-0000 B-0001 C- 001 D-10 E-11 F-01
扩展资料：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
参考资料来源：百度百科-哈夫曼树
热心网友
时间：2023-10-23 20:49
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；从森林中删除选取的两棵树，并将新树加入森林。
树的路径长度是从树根到每一结点的路径长度之和；
WPL＝（W1＊L1＋W2＊L2＋W3＊L3＋．．．＋Wn＊Ln），N个权值Wi（i＝1，2，．．．n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i＝1，2，．．．n）。可以证明哈夫曼树的WPL是最小的。
扩展资料：
（1）结合w1，W2，…视Wn为有N棵树的森林（每棵树只有一个节点）；
（2）选择森林中两个根节点权值最小的树进行合并，作为新树的左右子树，新树的根权值为其左右子树权值之和；
（3）将选定的两棵树从森林中删除，并将新树添加到森林中；
（4）重复步骤(2)、(3)，直到森林中只剩下一棵树，即获得的Huffman树。
热心网友
时间：2023-10-23 20:50
