哈夫曼树构造以及代码实现
什么是哈夫曼树
构造一颗二叉树，该树的带权路径长度达到最小，称为最优二叉树，也称为哈夫曼树（Huffman Tree）
注：带权路径长度就是下文提到的树的编码长度
理解哈夫曼树
为了更深理解哈夫曼树的由来，我们先来举个例子一步一步引入哈弗曼树是如何解决编码问题的
假设有一串字符，包含abcdefg这几个字符，每个字符出现的频次不同，如图：
先来思考一下，给定一段字符串，如何对字符串进行编码可以使得字符串的编码存储空间最少？
假如一段文本中，有58个字符，那么，
用ASCII编码：58 x 8 = 464位
用等长3位编码：58 x 3 = 174位
用不等长编码：出现频次高的字符用的编码短些，出现频次低的编码长些
那么我们重新计算一下编码长度,如下图:
10x3+15x2+12x2+3x5+4x4+13x2+1x5=146位，算完以后，是不是占用存储空间小了很多，但这还不是最小的，那么有什么办法可以使得字符编码的存储空间最小呢？答：二叉树
二叉树进行编码
将二叉树的左右分支设置为0和1，可以将频次高低不同的字符进行字符编码,如图，是4个频次最高的字符
经过字符重新编码以后，
b 编码 0
f 编码 1
c 编码 10
a 编码 11
思考：不等长编码容易出现什么问题？
举例：1011是什么字符串的编码呢？
如图，1011可以代表以下这几种字符组合的可能，容易出现二义性，
那么，如何避免二义性？
答：字符只在叶子节点上就不会有二义性,如图：
这样10只能是f,11只能是b，具有唯一性
那么问题来了，我们怎么解决不等长问题的空间存储最小呢？终于说到哈夫曼树了
哈夫曼树的构造
- 每次把权值最小的两棵二叉树合并；
- 左节点权值比右节点小
构造步骤如图：
看步骤（6）中就是最终构造的哈夫曼树了，所有节点都在叶子节点上，
也是带权路径长度最小的了，用每个节点的值和距离根节点的深度相乘再将值加起来，就是我们上文例子中算出来的值10x3+15x2+12x2+3x5+4x4+13x2+1x5=146位
哈夫曼树构造-代码实现
/**
* 哈夫曼树
*/
public class HuffmanTree {
//节点
public static class Node<E> {
E data; //数据
int weight; //权重
Node leftChild; //左子节点
Node rightChild;//右子节点
public Node(E data, int weight) {
super();
this.data = data;
this.weight = weight;
}
public String toString() {
return "Node[" + weight + ",data=" + data + "]";
}
}
public static void main(String[] args) {
List<Node> nodes = new ArrayList<Node>();
//把节点加入至list中
nodes.add(new Node("a", 10));
nodes.add(new Node("b", 15));
nodes.add(new Node("c", 12));
nodes.add(new Node("d", 3));
nodes.add(new Node("e", 4));
nodes.add(new Node("f", 13));
nodes.add(new Node("g", 1));
//进行哈夫曼树的构造
Node root = HuffmanTree.createTree(nodes);
//打印哈夫曼树
printTree(root);
}
/**
* 构造哈夫曼树
*
* @param nodes
* 节点集合
* @return 构造出来的哈夫曼树的根节点
*/
private static Node createTree(List<Node> nodes) {
//如果节点node列表中海油2个和2个以上的节点
while(nodes.size()>1){
//什么是最小的，list表进行排序，增序的方式， 0,1，
sort(nodes);//排序方式是增序的
Node left = nodes.get(0);//权重最小的
Node right = nodes.get(1);//权重第二小的
//生成一个新的节点（父节点），父节点的权重为两个子节点的之和
Node parent = new Node(null,left.weight+right.weight);
//树的连接，让子节点与父节点进行连接
parent.leftChild = left;
parent.rightChild = right;
nodes.remove(0);//删除最小的
nodes.remove(0);//删除第二小的。
nodes.add(parent);
}
return nodes.get(0); //返回根节点
}
/**
* 冒泡排序，用于对节点进行排序（增序排序）
*
* @param nodes
*/
public static void sort(List<Node> nodes) {
if (nodes.size() <= 1)
return ;
/*循环数组长度的次数*/
for (int i = 0; i < nodes.size(); i++){
/*从第0个元素开始，依次和后面的元素进行比较
* j < array.length - 1 - i表示第[array.length - 1 - i]
* 个元素已经冒泡到了合适的位置，无需进行比较，可以减少比较次数*/
for (int j = 0; j < nodes.size() - 1 - i; j++){
/*如果第j个节点比后面的第j+1节点权重大，交换两者的位置*/
if (nodes.get(j + 1).weight < nodes.get(j).weight) {
Node temp = nodes.get(j + 1);
nodes.set(j+1,nodes.get(j));
nodes.set(j,temp);
}
}
}
return ;
}
/*
* 递归打印哈夫曼树(先左子树，后右子树打印)
*/
public static void printTree(Node root) {
System.out.println(root.toString());
if(root.leftChild !=null){
System.out.print("left:");
printTree(root.leftChild);
}
if(root.rightChild !=null){
System.out.print("right:");
printTree(root.rightChild);
}
}
}