前言
哈夫曼树是数据压缩编码算法的基础，本文使用JavaScript语言实现了该算法。算法流程：输入待编码的字符串，算法去构造哈夫曼树，从而实现对字符串的二进制压缩编码。
对于哈夫曼树理论的学习，可去参见其他文章。本文仅包含实现的代码以及注释。
注释比较丰富，相信不难理解。
算法实现
树节点
既然是树数据结构，就要有树节点，下面是树节点定义
class Node {
constructor(value, char, left, right) {
this.val = value; // 字符出现次数
this.char = char; // 待编码字符
this.left = left;
this.right = right;
}
}一般来说，节点只需要val,left,right即可，这里加了一个char字段，表示该节点代表待编码字符串里面的哪个字符，当前节点是叶子节点的时候，会赋值这个字段。
核心代码
构造函数
class huffmanTree{
constructor(str){
// 第一步，统计字符出现频率
let hash = {};
for(let i = 0; i < str.length; i++){
hash[str[i]] = ~~hash[str[i]] + 1;
}
this.hash = hash;
// 第二步，构造哈夫曼树
this.huffmanTree = this.getHuffmanTree();
// 第三步，遍历哈夫曼树，得到编码表
let map = this.getHuffmanCode(this.huffmanTree);
// 查看编码表，即每个字符的二进制编码是什么
console.log(map);
// 第四部，根据编码对照表，返回最终的二进制编码
this.binaryStr = this.getBinaryStr(map, str);
}
}
下面我们逐一的看一下，（1）构造哈夫曼树的过程、（2）遍历哈弗曼树取得编码表的过程 以及 （3）返回最终二进制串的过程。
构造哈夫曼树
// 构造哈夫曼树
getHuffmanTree(){
// 以各个字符出现次数为node.val, 构造森林
let forest = []
for(let char in this.hash){
let node = new Node(this.hash[char], char);
forest.push(node);
}
let allNodes = []; // 存放被合并的节点，因为不能真的删除森林中任何一个节点，否则.left .right就找不到节点了
// 等到森林只剩一个节点时，表示合并过程结束，树就生成了
while(forest.length !== 1){
// 从森林中找到两个最小的树，合并之
forest.sort((a, b) => {
return a.val - b.val;
});
let node = new Node(forest[0].val + forest[1].val, '');
allNodes.push(forest[0]);
allNodes.push(forest[1]);
node.left = allNodes[allNodes.length - 2]; // 左子树放置词频低的
node.right = allNodes[allNodes.length - 1]; // 右子树放置词频高的
// 删除最小的两棵树
forest = forest.slice(2);
// 新增的树加入
forest.push(node);
}
// 生成的哈夫曼树，仅剩一个节点，即整棵树的根节点
return forest[0];
} 遍历哈夫曼树，返回编码表
// 遍历哈夫曼树，返回一个 原始字符 和 二进制编码 的对照表
getHuffmanCode(tree){
let hash = {}; // 对照表
let traversal = (node, curPath) => {
if (!node.length && !node.right) return;
if (node.left && !node.left.left && !node.left.right){
hash[node.left.char] = curPath + '0';
}
if (node.right && !node.right.left && !node.right.right){
hash[node.right.char] = curPath + '1';
}
// 往左遍历，路径加0
if(node.left){
traversal(node.left, curPath + '0');
}
// 往右遍历，路径加1
if(node.right){
traversal(node.right, curPath + '1');
}
};
traversal(tree, '');
return hash;
} 返回编码串
// 返回最终的压缩后的二进制串
getBinaryStr(map, originStr){
let result = '';
for(let i = 0; i < originStr.length; i++){
result += map[originStr[i]];
}
return result;
} 代码汇总
// 哈弗曼编码是将一个 字符串序列 用 二进制表示 的压缩算法
class huffmanTree{
constructor(str){
// 第一步，统计字符出现频率
let hash = {};
for(let i = 0; i < str.length; i++){
hash[str[i]] = ~~hash[str[i]] + 1;
}
this.hash = hash;
// 构造哈夫曼树
this.huffmanTree = this.getHuffmanTree();
let map = this.getHuffmanCode(this.huffmanTree);
// 查看对照表，即每个字符的二进制编码是什么
console.log(map);
// 最终的二进制编码
this.binaryStr = this.getBinaryStr(map, str);
}
// 构造哈夫曼树
getHuffmanTree(){
// 以各个字符出现次数为node.val, 构造森林
let forest = []
for(let char in this.hash){
let node = new Node(this.hash[char], char);
forest.push(node);
}
// 等到森林只剩一个节点时，表示合并过程结束，树就生成了
let allNodes = []; // 存放被合并的节点，因为不能真的删除森林中任何一个节点，否则.left .right就找不到节点了
while(forest.length !== 1){
// 从森林中找到两个最小的树，合并之
forest.sort((a, b) => {
return a.val - b.val;
});
let node = new Node(forest[0].val + forest[1].val, '');
allNodes.push(forest[0]);
allNodes.push(forest[1]);
node.left = allNodes[allNodes.length - 2]; // 左子树放置词频低的
node.right = allNodes[allNodes.length - 1]; // 右子树放置词频高的
// 删除最小的两棵树
forest = forest.slice(2);
// 新增的树加入
forest.push(node);
}
// 生成的哈夫曼树
return forest[0];
}
// 遍历哈夫曼树，返回一个 原始字符 和 二进制编码 的对照表
getHuffmanCode(tree){
let hash = {}; // 对照表
let traversal = (node, curPath) => {
if (!node.length && !node.right) return;
if (node.left && !node.left.left && !node.left.right){
hash[node.left.char] = curPath + '0';
}
if (node.right && !node.right.left && !node.right.right){
hash[node.right.char] = curPath + '1';
}
// 往左遍历，路径加0
if(node.left){
traversal(node.left, curPath + '0');
}
// 往右遍历，路径加1
if(node.right){
traversal(node.right, curPath + '1');
}
};
traversal(tree, '');
return hash;
}
// 返回最终的压缩后的二进制串
getBinaryStr(map, originStr){
let result = '';
for(let i = 0; i < originStr.length; i++){
result += map[originStr[i]];
}
return result;
}
}测试代码
let tree = new huffmanTree('ABBCCCDDDDEEEEE')
console.log(tree)编码对照表：{ C: '00', A: '010', B: '011', D: '10', E: '11' }
最终编码结果：010011011000000101010101111111111
结语
前端算法库：https://github.com/cunzaizhuyi
这里记录了我刷过的近500道LeetCode的题解，
希望对前端同行找工作面试、修炼算法内功有帮助。
原文：https://segmentfault.com/a/1190000021837224
js除了Math.floor方法，还可以通过位运算|，>>实现向下取整
我们都知道通过Math.floor()方法可实现数值的向下取整，得到小于或等于该数字的最大整数。除了Math.floor方法，还可以使用位运算|，>>来实现向下取整哦
es6 扩展运算符 三个点（...）
扩展运算符（ spread ）是三个点（...）。它好比 rest 参数的逆运算，将一个数组转为用逗号分隔的参数序列。
巧用JS位运算
位运算的方法在其它语言也是一样的，不局限于JS，所以本文提到的位运算也适用于其它语言。位运算是低级的运算操作，所以速度往往也是最快的
js中使用位运算，让执行效率更高
平常的数值运算，其本质都是先转换成二进制再进行运算的，而位运算是直接进行二进制运算，所以原则上位运算的执行效率是比较高的，由于位运算的博大精深，下面通过一些在js中使用位运算的实例
js各种取整方式及方法_四舍五入、向上取整、向下取整
js实现：四舍五入、向上取整、向下取整等方法。parseInt、Math.ceil、Math.round、Math.floor、toFixed等的使用
JavaScript循环计数器
JS经常会遇到延迟执行的动作，并且失败后自动尝试，尝试N次之后就不再尝试的需求，今天刚好又遇到，于是写个闭包，以后不断完善继续复用。检查并计数第一个参数用来标记是尝试哪个动作的，第二个参数是最大尝试次数
js 位运算符_js按位运算符及其妙用
大多数语言都提供了按位运算符，恰当的使用按位运算符有时候会取得的很好的效果。在我看来按位运算符应该有7个：& 按位与、| 按位或、^ 按位异或、~ 按位非
PHP取整、四舍五入取整、向上取整、向下取整、小数截取
PHP取整数函数常用的四种方法：1.直接取整，舍弃小数，保留整数：intval()； 2.四舍五入取整：round()； 3.向上取整，有小数就加1：ceil()； 4.向下取整：floor()。
JavaScript 中的相等操作符 ( 详解 [] == []、[] == ![]、{} == !{} )
ECMAScript 中的相等操作符由两个等于号 ( == ) 表示，如果两个操作数相等，则返回 true。相等操作符会先转换操作数（通常称为强制转型），然后比较它们的相等性。
关于js开发中保留小数位计算函数（以向上取整或向下取整的方式保留小数）
前端工作中经常遇到数字计算保留小数问题，由于不是四舍五入的方式不能使用toFixed函数，本文采用正则表达式匹配字符串的方式，解决对数字的向上或向下保留小数问题：
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!