PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、赫夫曼树
1、1 赫夫曼树的根本介绍 1、2 赫夫曼树的重要概念 1、3 赫夫曼树创立思路 1、4 赫夫曼树的代码实现1、赫夫曼树
1、1 赫夫曼树的根本介绍
给定 n 个权值作为 n 个叶子结点，结构一棵二叉树，若该树的带权门路长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树；赫夫曼树是带权门路长度最短的树，权值较大的结点离根较近。
“ 权值 ” 、“ 树的带权门路长度 ” 和 “ 赫夫曼树是带权门路长度最短的树，权值较大的结点离根较近 ” 这3句话如同了解不了？没关系，咱们先保留悬念，上面会剖析到。
1、2 赫夫曼树的重要概念
为了更好的阐明这些概念，咱们先画一棵一般的二叉树，如图1所示：
图片
门路：在一棵树中，从一个结点往下能够达到的孩子或孙子结点之间的通路；例如图1中的2节点到8节点的门路为 2 -> 4 -> 8 。
门路长度：通路中分支的数目，若规定根结点的层数为1，则从根结点到第 L 层结点的门路长度为 L-1；例如8节点所在的一层是第4层，那么8节点的门路长度为 4 - 1 。
节点的权值：将树中结点赋给一个有着某种含意的数值，这个数值称为该结点的权；例如9节点的的数值是9，那么节点的权值就是9 。
结点的带权门路长度：从根结点到该结点之间的门路长度与该结点的权的乘积；例如9节点的带权门路长度就等于3（4 - 1）乘以9 。
树的带权门路长度：所有叶子结点的带权门路长度之和，记为WPL (weighted path length)；例如图1中树的带权门路长度就为 8节点、9节点、5节点、6节点和7节点的带权门路长度之和。
赫夫曼树：就是 WPL 最小的一棵二叉树，也就是树的带权门路长度最小。
1、3 赫夫曼树创立思路
假如咱们有一个数列 arr = {13 , 7 , 8 , 3 , 29 , 6 , 2 }，将这个数列转换成一棵赫夫曼树，咱们该怎么做呢？
好，咱们来剖析赫夫曼树的创立步骤：
（1）将这个数列从小到大进行排序，将每一个数字，每个数字都是一个节点，每个节点又看成是一颗最简略的二叉树。
（2）取出根节点权值最小的两颗二叉树，组成一颗新的二叉树，该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和。
（3）如果组合完这颗新的二叉树后，没有其余树了，那么就失去一棵赫夫曼树，不用执行（4）步骤。
（4）如果组合完这颗新的二叉树后，还有其余树了，那么就将这颗新的二叉树的根节点的权和其余根节点的权进行组合一个数列，再回到（1）。
有了赫夫曼树的创立步骤，咱们就能够对 arr = {13 , 7 , 8 , 3 , 29 , 6 , 2 } 进行转换成赫夫曼树。
图片
（1）看图2，咱们把 arr = {13 , 7 , 8 , 3 , 29 , 6 , 2 } 这个数列进行了从小到大排序并把数字变成根节点，而后从最小的2个根节点（2节点和3节点）组合成一棵二叉树，并失去如图3所示的多棵二叉树。
图片
留神：红色的数字的节点是从 arr 这个数列中失去的，而红色的数字的节点是组合而成的新节点，以下呈现的图，也是一样的阐明。
（2）看图3，用根节点2和根节点3组合成一棵新的二叉树，并把5节点作为它们的根节点（该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和），而后又失去了一个新的数列并从小到大排序 arr = {5 ， 6 ， 7 ， 8 ， 13 ， 29}，又从 arr 数列当选最小的2个根节点组合成一棵二叉树，并失去如图4所示的多棵二叉树。
图片
（3）看图4，用根节点5和根节点6组合成一棵新的二叉树，并把11节点作为它们的根节点（该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和），而后又失去了一个新的数列并从小到大排序 arr = {7 ， 8 ， 11 ， 13， 29}，又从 arr 数列当选最小的2个根节点组合成一棵二叉树，并失去如图5所示的多棵二叉树。
图片
（4）看图5，用根节点7和根节点8组合成一棵新的二叉树，并把15节点作为它们的根节点（该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和），而后又失去了一个新的数列并从小到大排序 arr = {11 ， 13 ， 15 ， 29}，又从 arr 数列当选最小的2个根节点组合成一棵二叉树，并失去如图6所示的多棵二叉树。
图片
（5）看图6，用根节点11和根节点13组合成一棵新的二叉树，并把24节点作为它们的根节点（该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和），而后又失去了一个新的数列并从小到大排序 arr = {15 ， 24 ， 29}，又从 arr 数列当选最小的2个根节点组合成一棵二叉树，并失去如图7所示的多棵二叉树。
图片
（6）看图7，用根节点15和根节点24组合成一棵新的二叉树，并把39节点作为它们的根节点（该新的二叉树的根节点的权值是后面两颗二叉树根节点权值的和），而后又失去了一个新的数列并从小到大排序 arr = {29 ， 39}，又从 arr 数列当选最小的2个根节点组合成一棵二叉树，并失去如图8所示的一棵二叉树。
图片
到了这里，一开始用数列 arr = {13 , 7 , 8 , 3 , 29 , 6 , 2 } 创立的赫夫曼树曾经实现；“ 权值较大的结点离根较近 ” 怎么了解这句话呢？就拿图8的赫夫曼树举例，39节点是不是比15节点权值更大，那39节点绝对15节点来说是不是离根节点68比拟近，这回了解了吧。
1、4 赫夫曼树的代码实现
图8中的二叉树，中序遍历的后果是：29 68 7 15 8 39 2 5 3 11 6 24 13，无关中序遍历的文章能够看Java版的数据结构和算法（四）这篇，好了，当初咱们用代码实现一把，用数列 arr = {13 , 7 , 8 , 3 , 29 , 6 , 2 } 创立一棵赫夫曼树。
（1）创立一个节点类 Node :
/**
- Node 实现 Comparable 是为了让Node 对象继续排序 Collections 汇合排序
*/
public class Node implements Comparable<Node>{
private int value;
private Node left;
private Node right;
public Node(int value) {
super();this.value = value;}
public int getValue() {
return value;}
public Node getLeft() {
return left;}
public void setLeft(Node left) {
this.left = left;}
public Node getRight() {
return right;}
public void setRight(Node right) {
this.right = right;}
@Override
public int compareTo(Node arg0) {
return this.value - arg0.value;}
@Override
public String toString() {
return "Node [value=" + value + "]";}
}
（2）创立一个结构赫夫曼树的类 Test ：
public class Test {
Node root;
public static void main(String[] args) {
int[] arr = { 13, 7, 8, 3, 29, 6, 2 };Test test = new Test();test.root = test.createHuffmanTree(arr);test.midOrder();}
/**
- 构建一棵哈夫曼树
- @param arr
*/
private Node createHuffmanTree(int[] arr) {
List<Node> list = new ArrayList<Node>();for (int i = 0; i < arr.length; i++) { // 用数组的元素作为节点的权值，并把节点保留在 list 汇合中 list.add(new Node(arr[i]));}while (list.size() > 1) { // 排序，从小到大排序 Collections.sort(list); // System.out.println("list = " + list); /** * 这个肯定是权值最小的节点 */ Node minNode = list.get(0); /** * 除了 minNode 节点，该节点就是权值最小的节点，只是该节点比 minNode 节点大， 比其余节点都小 */ Node secondMinNode = list.get(1); /** * 构建一棵新的二叉树 */ Node parentNode = new Node(minNode.getValue() + secondMinNode.getValue()); parentNode.setLeft(minNode); parentNode.setRight(secondMinNode); /** * 从 list 汇合中删除2棵曾经构建成一棵二叉树的2个节点 */ list.remove(minNode); list.remove(secondMinNode); /** * 将新的二叉树的父节点退出到 list 汇合中 */ list.add(parentNode);}/** * 构建完哈夫曼树后，list 汇合中的第一个节点必定是根节点，除非该办法传入的数组arr是空的 */return list.get(0);}
// 中序遍历
private void midOrder() {
if (root != null) { System.out.println("二叉树的中序遍历~~"); midOrder(root);} else { System.out.println("这是一棵空树");}}
public void midOrder(Node node) {
// 递归向左子树进行前序遍历if (node.getLeft() != null) { midOrder(node.getLeft());}// 输入以后节点System.out.println(node);// 递归向右子树进行前序遍历if (node.getRight() != null) { midOrder(node.getRight());}}
}
程序运行如下所示：
图片
看见没有，结构实现赫夫曼树后，咱们再对赫夫曼树中序遍历，失去的后果和图8中的二叉树的中序遍历后果是一样的。