共计 4073 个字符，预计需要花费 11 分钟才能阅读完成。
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 中的二叉树的中序遍历后果是一样的。
