哈佛曼树的定义： 带权路径长度最短的树。
每一个叶子节点有一个权重值，权重值 乘以 路径长度【路径长度指的是根节点到该节点的路径长度】 ，所有叶子节点的 带权路径长度 之和最小的树，称之为哈弗曼树，也称之为最优二叉树。
n为所有叶子节点的个数，w为该叶子节点的权重，length©为该叶子节点的路径长度，图来自于维基百科。
给定一组有特定权重值的节点，构造一棵哈弗曼树。 可以用最简单的想法来：权重最大的叶子节点离根节点最近，权重最小的叶子节点离根节点最远。
前景提要： 给定n个具有特定权重的叶子节点。
思路： 1，根据n个给定的权重值 {w1, w2, w3 … wn }，构造具有n棵只有根节点的二叉树组成的森林。F = { T1, T2, T3…Tn }, 其中Ti 为只有一个根节点并且权重值为wi的根节点（实际上也是一棵只有根节点的树）。 2，在F中选取权重值最小的两个节点，作为左右子树构造一棵新树，这棵树的根节点的权重值为左右子树的权重值之和。 3，将森林中的删除第二步合并的两棵树，将新树添加到森林F中。 4，重复第二，三步骤，直到森林中只有一棵树为止。
1，构造森林全是根。 2，选用两小造新树。 3，删除两小添新人。 4，重复2，3剩单根。
这个过程中：
每一次要合并两个节点，到一棵新的树里面，n个节点，要合并n-1次，直到最后只有 1棵树。
一共合并n-1次，会有新的节点n-1个，所以有n个叶子节点的哈夫曼树，一共有n + ( n- 1 )个 也就是 2n - 1节点。
并且这2n-1个节点中，有n个度为0的叶子节点，以及n-1个度为2的节点。
哈弗曼树的节点的度数【儿子节点】个数只会是0 或者 2，不存在度为1的节点。
二叉树的节点定义
function TreeNode(val, left, right) { this.val = (val===undefined ? 0 : val) this.left = (left===undefined ? null : left) this.right = (right===undefined ? null : right) }javascript 算法实现：
// 给定一组权重值 const contructHaffumanTree = (weightArr) => { if (!weightArr || weightArr.length <= 0) { return null } let n = weightArr.length // 先对权重进行排序，构造哈夫曼树从权重最小的节点开始 // 排序之后，依次从数组的头部获取即可。 // 排序算法有多种，这里使用js默认方法 const sortedWeightArr = weightArr.sort((num1, num2)=>num1 - num2) // 1， 构造森林 let forest = sortedWeightArr.map(v => new TreeNode(v)) // 2,3 选取最小权重的两个节点，构造新树添加到森林中，删掉以前的两棵树 // 合并n-1次，循环n-1次 直到森林中只有一棵树 for (let i = 1; i < n ; i++) { let minNode1 = forest.shift() let minNode2 = forest.shift() let newNode = new TreeNode() newNode.val = minNode1.val + minNode2.val newNode.left = minNode1 newNode.right = minNode2 forest.push(newNode); // 为了后续的循环直接获取数组头部的元素（权重值最小的两个节点），这里直接再排一次序 forest.sort((n1, n2) =>n1.val - n2.val) } // 4，森林里只有一颗树 return forest[0] } // test case contructHaffumanTree([7,5,2,4])资料： 构造哈夫曼树
