前几篇文章咱们学习二叉树、程序二叉树、线索化二叉树、堆，接下来咱们持续学习有对于树的下一个利用构造：哈夫曼树
一、什么是哈夫曼树
根本介绍
1.给定n个权值作为n个叶子结点，结构一棵二叉树，若该树的带权门路长度1(wpl)达到最小，称这样的二叉树为最优叉树。也称为哈夫曼树(HuffmanTree)，还有的书翻译为霍夫曼树。
wpl：weight pathI ength
2.哈夫曼树是带权门路长度最短的树，权值较大的结点离根较近。
问题剖析
那么这时就有新的问题呈现！须要咱们解决了
1.什么是门路呢？门路长度是什么？
2.什么是权和带权门路长度是什么？
3.带权门路长度最短的树，那么树的带权门路长度是什么？
什么是门路和门路长度？
在一棵树中，从一个结点往下能够达到的孩子或孙子结点之间的通路，称为门路。
通路中分支的数目称为门路长度。若规定根结点的层数为 1，则从根结点到第L层结点的门路长度为L-1。
什么是结点的权和带权门路长度？
若将树中结点赋给一个有着某种含意的数值，则这个数值称为该结点的权。
结点的带权门路长度为：从根结点到该结点之间的门路长度与该结点的权的乘积。
什么是树的带权门路长度？
树的带权门路长度规定为：所有叶子结点的带权门路长度之和，记为WPL(weighted path length)，权值越大的结点离根结点越近的二叉树才是最优二叉树。
通过不同的WPL意识哈弗曼树
若该树的带权门路长度1(wpl)达到最小，称这样的二叉树为最优叉树。也称为哈夫曼树(HuffmanTree)
哈夫曼树是带权门路长度最短的树，权值较大的结点离根较近
如上图所示咱们发现两头的树其实就是哈夫曼树(HuffmanTree)，并且满足权值较大的结点离根较近
权值越大的叶子节点越凑近根节点，权值越小的叶子节点越远离根节点。
二、通过示例意识哈夫曼树
将一个权重数列{13, 7, 8,3,29,6,1}，求转成一颗赫夫曼树.
思路图解剖析
1.将数列{13, 7, 8, 3, 29, 6, 1}，进行从小到大排序
2.新数列的每个数看成最简略根节点的二叉树
3.取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和
4.将新二叉树以跟节点的权重值再次从小到大排序，一直反复步骤
咱们发现每次都须要依据节点权重值进行大小排序，那么咱们能不能使得对象节点自身就具备比拟的性能呢？
答案是有的：咱们的自定义对象Node实现Comparable接口
同时当咱们发现排序后，数列的前两个就是最小的权值。
那么依据图所示咱们来上节点的代码把
//创立节点类 //为了让Node 对象继续排序Conllections汇合排序 //让Node 实现Comparable接口 class Node implements Comparable<Node>{ int value;//结点权值 Node left;//指向左节点 Node right;//指向右节点 public Node(int value) { this.value = value; } @Override public String toString() { return "Node[" +"value=" + value +']'; } @Override public int compareTo(Node o) { //示意从小到大进行排序 //从大到小进行排序 - (this.value - o.value)； return this.value - o.value; } }外围代码剖析
public static void createHuffmanTree(int[] arr ){ /** * 操作思路 * 1.遍历arr数组 * 2.将arr数组里的元素形成Node节点 * 3.将Node 放入ArrayList中 * 4.进行从小到大排序 */ List<Node> nodes = new ArrayList<Node>(); for (int itme:arr) { nodes.add(new Node(itme)); } //进行排序，ArrayList里的sort排序Node 须要实现Comparable接口 Collections.sort(nodes); System.out.println(nodes); }咱们先来测试看看第一步：将数列形成节点并进行从小到大排序
public static void main(String[] args) { int arr[] = {13,7,8,3,29,6,1}; createHuffmanTree(arr); }运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]如上所示，第一步看来还是胜利了的，那么接下来进行第二步
进行第二步：取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和
public static void createHuffmanTree(int[] arr ){ //省略第一步：将数列形成节点并进行从小到大排序代码 /** * 操作思路 * 1.取出两个权值最小的节点二叉树 * 2.依据两个权值最小的二叉树构建成一个新的二叉树 * 3.删除原先两个权值最小的节点二叉树 * 4.将新的二叉树放入队列，并构建新的队列 * 5.新的队列进行从小到大排序 */ //取出第一个权值最小的二叉树 Node leftNode = nodes.get(0); //取出第二个权值最小的二叉树 Node rightNode = nodes.get(1); //依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯 Node parentNode = new Node(leftNode.value + rightNode.value); parentNode.left = leftNode; parentNode.right = rightNode; //删除原先两个权值最小的节点二叉树 nodes.remove(leftNode); nodes.remove(rightNode); //将新的二叉树放入队列，并构建新的队列 nodes.add(parentNode); Collections.sort(nodes); System.out.println("第一次解决后："+nodes);}运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]第一次解决后：[Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]细节法则小结
1.新的二叉树增加后、就会删除原两个权值最小的二叉树
2.解决完后须要从新排序从小到大
3.如思路剖析图所示反复步骤操作后队列里只剩下一个节点
整合外围代码
public static Node createHuffmanTree(int[] arr ){ /** * 操作思路 * 1.遍历arr数组 * 2.将arr数组里的元素形成Node节点 * 3.将Node 放入ArrayList中 * 4.进行从小到大排序 */ List<Node> nodes = new ArrayList<Node>(); for (int itme:arr) { nodes.add(new Node(itme)); } while(nodes.size() >1){ //进行排序从小到大 Collections.sort(nodes); System.out.println(nodes); /** * 操作思路 * 1.取出两个权值最小的节点二叉 * 2.依据两个权值最小的二叉树构建成一个新的二叉树 * 3.删除原先两个权值最小的节点二叉树 * 4.将新的二叉树放入队列，并构建新的队列 * 5.新的队列进行从小到大排序 */ //取出第一个权值最小的二叉树 Node leftNode = nodes.get(0); //取出第二个权值最小的二叉树 Node rightNode = nodes.get(1); //依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯 Node parentNode = new Node(leftNode.value + rightNode.value); parentNode.left = leftNode; parentNode.right = rightNode; //删除原先两个权值最小的节点二叉树 nodes.remove(leftNode); nodes.remove(rightNode); //将新的二叉树放入队列，并构建新的队列 nodes.add(parentNode); } //因为队列只剩下最初一个节点所以间接返回即可 return nodes.get(0); }接下来让咱们验证一下是否如图所示胜利绘制成哈夫曼树
应用前序遍历打印留在队列的root 节点，还记得前序遍历吗？
前序遍历特点：前序是先输入父节点，再遍历左子树和右子树
class Node implements Comparable<Node>{ //省略Node 逻辑代码 //增加前序遍历代码 public void preOrder(){ System.out.println(this); if(this.left!=null){ this.left.preOrder(); } if(this.right!=null){ this.right.preOrder(); } } }//增加根节点遍历办法public static void preOrder(Node root){ if(root!=null){ root.preOrder(); }else{ System.out.println("该哈弗曼树为空！无奈遍历"); } }咱们的数列{13, 7, 8,3,29,6,1}，组装成哈弗曼树后的前序遍历，思考一下是什么呢？
public static void main(String[] args) { int arr[] = {13,7,8,3,29,6,1}; Node root = createHuffmanTree(arr); preOrder(root);}运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]][Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]][Node[value=7], Node[value=8], Node[value=10], Node[value=13], Node[value=29]][Node[value=10], Node[value=13], Node[value=15], Node[value=29]][Node[value=15], Node[value=23], Node[value=29]][Node[value=29], Node[value=38]]Node[value=67]Node[value=29]Node[value=38]Node[value=15]Node[value=7]Node[value=8]Node[value=23]Node[value=10]Node[value=4]Node[value=1]Node[value=3]Node[value=6]Node[value=13]