【树】哈夫曼树-频率大的短编码

发布时间 2023-11-13 21:07:11作者: 苏二七

解决问题:

对一篇电报编码: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;