已知字符abcd出现的次数分别为7.5.2.4则构造哈夫曼树中字符b对应编码为
时间: 2023-05-26 22:07:27 浏览: 263
0。
步骤如下:
1. 将所有字符节点按照出现次数从小到大排序。
2. 取出出现次数最小的两个字符节点,合并成一个新的节点,新节点的权值即为两个字符节点权值之和。将新节点插入到排序后的字符节点中。
3. 重复步骤2,直到所有字符节点都合并为一个根节点。
4. 构造编码:从根节点开始,走左子树编码为0,走右子树编码为1。最终得到b对应的编码为0。
具体构造过程如下:
1. 排序后的字符节点为c(2) d(4) a(7) b(5)。
2. 合并c和d,新节点权值为6,得到新节点集合:a(7) b(5) cd(6)。
3. 合并cd和a,新节点权值为13,得到新节点集合:b(5) cda(13)。
4. 合并b和cda,新节点权值为18,得到根节点。
5. 从根节点开始走到b,编码为0,得到b对应的编码为0。
阅读全文