哈夫曼树对应的是一种哈夫曼编码，这种编码主要应用于文件压缩领域。
- 编码会遇到问题
- 哈夫曼树以及哈夫曼编码
- 落地到代码
编码会遇到的问题
编码：将一段字符编码为二进制。
ABAACDC- A: 0
- B: 1
- C: 10
- D: 11
0100101110编码完成了，但是解码会遇到很大的问题。以前三位010为例：
- AC
- ABA
究其原因是因为一个字符的编码成为了另一个字符编码的前缀。
- B：1 但是 C 和 D 它们的编码都是 1 开头的。
BC --> 110 --> DA因此，在进行编码的时候，不能让一个字符的编码成为另外一个字符的前缀。
另外一种方案：等长编码：
- A：0000
- B：0001
- C：0010
- D：0011
ABAACDC0000000100000000001000110010这种方式虽然能够解决解码歧义的问题，但是编码出来的结果太长了。
哈夫曼树
使用哈夫曼树形成的哈夫曼编码：
- 不会有歧义（不会有任何一个字符的编码是另外一个字符的前缀）
- 编出来的码是最短的
哈夫曼编码核心思想：出现频率越高的字符，编码应该越短，出现频率低的字符，编码长一点也没关系。
ABAACDC- A: 3
- B: 1
- C: 2
- D: 1
接下来就需要根据频率来构建二叉树结构。
从出现频率低的字符开始：
接下来再取一个节点：C，将 C 放置在和 2 同一级。
最后取 A，和 4 同一层：
至此，整颗二叉树就构建完成，这颗二叉树就是哈夫曼树。
构建哈夫曼树是为了得到哈夫曼编码：
将整颗树左边的边记为 0，右边的边记为 1:
- A： 1
- B：010
- C：00
- D：011
课堂练习
将下面的字符串生成哈夫曼树以及哈夫曼编码：
CEABEACDA统计各个字符出现的次数：
- A：3
- B：1
- C：2
- D：1
- E：2
A(3)、B(1)、C(2)、D(1)、E(2)首先取 B(1) 和 D(1)：
A(3)、C(2)、E(2)、BD(2)接下来继续取，C 和 E 都是相同，随便取一个：
A(3)、E(2)、BDC(4)接下来是一个关键：A 和 E 分别对应 3 和 2，比当前的顶层节点 BDC 的 4 要小，因此取这两个节点进行合并
BDC(4)、AE(5)最终合并出来的哈夫曼树为：
- A：10
- B：010
- C：00
- D：011
- E：11
哈夫曼编码不是唯一。在构建哈夫曼树的时候，节点放的位置不同，最终得到的哈夫曼树就会有所不同，自然哈夫曼编码也就不一样。但是最终的哈夫曼编码一定满足前面所说的特点：
- 不会有歧义
- 频率高的编码越短
代码实现
/** * 哈夫曼节点类 */class HuffmanNode { constructor(char, freq, left = null, right = null) { this.char = char // 字符 this.freq = freq // 频率 this.left = left // 左子节点 this.right = right // 右子节点 }}
/** * str - 待编码的字符串 * return - 返回一个对象，对象的键是对应的字符，对象的值是该字符所出现的次数 * { 'a': 5, 'b': 2, ...} */function getFrequencyMap(str) { const freq = {}
// 遍历字符串的每一个字符 for (const ch of str) { freq[ch] = (freq[ch] || 0) + 1 }
return freq}
/** * str - 待编码的字符串 * return - 构建的哈夫曼树所对应的根节点 */function buildHuffmanTree(str) { // 1. 先得到字符串里面每一个字符出现的频率 const freqMap = getFrequencyMap(str)
// 这里得到的就是键所构成的数组，例如 ['A', 'B', 'C', ...] const uniqueChars = Object.keys(freqMap) // 做一下边界处理 if (uniqueChars.length === 0) return null if (uniqueChars.length === 1) { // 说明整个字符串里面只有一种字符，类似于 'AAAAAAAAAA...' // 那么这里我们就可以直接指定编码为 0 return new HuffmanNode(uniqueChars[0], freqMap[uniqueChars[0]]) }
// 代码来到这里，说明有多个字符 // 首先将所有出现了的字符生成哈夫曼节点对象 // 注意这里是一种字符就会生成一个哈夫曼节点对象 let nodes = uniqueChars.map((ch) => new HuffmanNode(ch, freqMap[ch]))
// 接下来就是哈夫曼节点两两进行合并 while (nodes.length > 1) { nodes.sort((a, b) => a.freq - b.freq) // 首先按照频率进行排序 const left = nodes.shift() // 取出一个频率最小的作为左子节点 const right = nodes.shift() // 再取出一个频率最小的作为右子节点
// 合并出新的子节点 const newNode = new HuffmanNode(null, left.freq + right.freq, left, right)
// 放回到数组里面 nodes.push(newNode) }
// 跳出上面的while循环，说明node数组的长度没有大于1，整个数组只剩1个节点 // 这个节点就是整颗哈夫曼树的根节点 return nodes[0]}
/** * root - 哈夫曼树的根节点 * return - 返回对应的哈夫曼编码表 { a: '00', b : '11'} */function buildHuffmanCodes(root) { const codes = {} // 存储生成的哈夫曼编码表
// 用于深度遍历哈夫曼树的辅助方法 function traverse(node, prefix) { if (!node) return
if (node.char !== null) { // 说明是叶子节点，需要保存对应的编码 codes[node.char] = prefix return }
// 代码来到这儿，说明不是叶子节点 // 继续深度遍历 traverse(node.left, prefix + '0') // 深度遍历左分支，并且因为是左分支，前缀加0 traverse(node.right, prefix + '1') // 深度遍历右分支，并且因为是右分支，前缀加1 } traverse(root, '') return codes}
/** * str - 待编码的字符串 * codes - 对应的哈夫曼编码表，例如 { A: '0', C: '10', B: '110', D: '111' } */function huffmanEncode(str, codes) { let encodedResult = '' // 存储编码后的结果
for (const ch of str) { encodedResult += codes[ch] }
return encodedResult}
/** * encodedStr - 编码后的字符串，例如 0110001011110 * root - 哈夫曼树的根节点 */function huffmanDecode(encodedStr, root) { let decodedResult = '' // 存储解码后的结果
let currentNode = root // 暂存树的根节点
// 遍历编码后的字符串的每一位 for (const bit of encodedStr) { if (bit === '0') { // 根据哈夫曼的核心思想，0 处于左分支 currentNode = currentNode.left } else { // 1 处于右分支 currentNode = currentNode.right }
if (currentNode.char !== null) { // 进入此分支，说明进入到了叶子节点，叶子节点代表具体的字符 decodedResult += currentNode.char currentNode = root // 重新回到根节点，每一次解析出来一个字符，都需要重新回到根节点 } }
return decodedResult}-EOF-