解决问题:
对一篇电报编码:Hello world 这里面除去符号,最多的字母是o,若要转换为01二进制尽量编码短;最少的字母h,编码长。
h 1; e 1; r 1; d 1; w 1; o 2; l 3;
-开始手动编码
--每次选取频次最小 左小右大 做孩子,加入一个父节点(值为孩子频次和)
编码:
- 树最多 2X元素长度 - 1个节点
- 为了1遍历 哈夫曼树 malloc 2X个node 内存
- 初始化 1 到 元素长度 节点 设置lchild rchild parent 为 null value = 对应频次
- 从 元素长度 + 1 开始遍历 因为后面才是新加父节点
- 每次选择 最小的2个元素
- 选择方法 遍历元素判断当前节点是否超过最大元素长度 与 是否有 parent 也就是已经被编码
- 获得两个元素指针后 当前元素的value = 两个元素相加
- 两个元素parent都指向当前元素
- 构建哈夫曼树完毕 获取编码
- 遍历 1 到 元素长度 即可
- 由于编码为倒序 递归parent 所以 len - start 获取 start = len - 1;
标签:编码,遍历,哈夫曼,parent,元素,频率,节点 From: https://www.cnblogs.com/su27/p/17830061.html