赫夫曼树问题22

来源：百度知道 编辑：UC知道 时间：2024/05/14 10:05:15
假定用于通信的电文由8个字母A,B,C,D,E,F,G,H组成,各字母在电文中出现的概率为5%,25%,4%,7%,9%,12%,30%,8%,试为这8个字母设计赫夫编码
(回答详细者拿分!谢谢)

总的方法：将权值最小的2个节点组成二叉树
如：最开始时权值最小的是A：5%和C：4%，将其组成二叉树，此时这两个节点相当于合并成为一个节点，其权值是9%，
。。。（9%）。。。。
。。。新节点1。。。。
。。。/。。\。。。。
。。A。。。。C。。。
。（5%）。（4%）。。
然后在重复上一过程，{新节点1,B,D,E,F,G,H}概率分别为：9%,25%,7%,9%,12%,30%,8%,里面选择最小的2个节点，是D:7%和H:8%
将其组成新节点，其权值是15%,以此类推，最后得出二叉树：
。。。。。。。。。。。。100%。。。。。。。。。。。。。。。。
。。。。。。。。。。。0/。。\1。。。。。。。。。。。。。。
。。。。。。。。。。43%。。57%。。。。。。。。。。。。。。
。。。。。。。。。0/。\1。0/。\1。。。。。。。。。。。。
。。。。。。。。。18%。B。G。。27%。。。。。。。。。。。
。。。。。。。。0/。\1。。。。0/。\1。。。。。。。。。。
。。。。。。。9%。。。E。。。F。。15%。。。。。。。。。。
。。。。。。0/。\1。。。。。。。0/。\1。。。。。。。
。。。。。A。。。C。。。。。。。D。。。E。。。。。。。
所以
A:0000;B:01;C:0001;D:1110;E:1111;F:110;G:10

概率按权值排序（大-小）：
GBFEHDAC
将权最小的两个组成一个二叉树
AC的左右两支，根节点为权值
然后依次挑选权值小的构造二叉树的左子树节点，与刚才构造的二叉树构造成一个新的二叉树，根节点时左右两支的权值,右分支每条边赋值1，左分支赋值0(这里用...是为了对齐)
G -| 0
B -| 10
F -| 110
E -| 1110
H -| 11110
D -| 111110
A -| 1111110