Huffman树：
- 路径带权
- 所有叶子结点的路经长*权的和—WPL，最小。
- 即权最大的叶子结点最浅
构造：从一堆带权值的树（一开始是左右都为空的叶子节点）开始：
- 取权最小的两个组成树，新树的权为二者之和
- 新树加入，两旧树删去
- 重复1、2，知道只剩一棵树
性质：最优判定树：概率最大的路径最短，总判定时间最小
Huffman编码：
- 从带权字符集，构建树：叶子结点集合，按前面的算法，合并成新的树
- 从huffman树，输出其中的编码
- 回溯：从每个叶子结点开始，找父母，看自己在父母的那一边，左是0右是1，记录下来
- 向下：从根节点开始，往下走，每经过一个节点
- 标记：未走／左分支已走／左右分支均已走，按标记决定下一步走向
- 记录编码于数组cd中：往左走添0，往右添1
- 遇到叶子结点，输出当前cd
- 两个分支均已走过的节点，退回父节点，cd退一字符
网友评论