JavaScript数据结构12——构造一个赫夫曼树

不得不说，当不同数据访问的概率是有规律的时候，可以使用赫夫曼树来提高性能

//二叉树节点
function Node(data) {
  this.data = data;
}
 
Array.prototype.createHufuTree = function() {
  var nodes = [];
  /*初始化结点*/
  for (var i = 0; i < this.length; i++) {
    nodes.push(new Node(this[i]));
  }
  while (nodes.length > 1) {
    nodes.sort(function(a, b) {
      return a.data - b.data;
    });
    var one = nodes.shift();
    var two = nodes.shift();
    var sum = one.data + two.data;
    /*构造结点*/
    var root = new Node(sum);
    console.info('one:'+one.data);
    console.info('two:'+two.data);
    if(one.data<=two.data){
      root.left = one;
      root.right = two;
    }else{
      root.right = one;
      root.left = two;
    }
    nodes.unshift(root);
  }
  return nodes[0];
}
 
/*测试用例*/
var datasarray = [5,10,15,30,40];
var res = datasarray.createHufuTree();
console.info(JSON.stringify(res));

打印

one:5
two:10
one:15
two:15
one:30
two:30
one:40
two:60
{"data":100,"left":{"data":40},"right":{"data":60,"left":{"data":30,"left":{"data":15,"left":{"data":5},"right":{"data":10}},"right":{"data":15}},"right":{"data":30}}}
[Finished in 0.1s]