哈夫曼树是美国数学家Huffman发现的一种数据结构，该数据结构用在哈夫曼编码中，哈夫曼编码是一种压缩算法，本文主要针对的是哈夫曼树这种数据结构，哈夫曼编码将在下篇博文中涉及。
在正式开始了解哈夫曼树之前有几个概念需要了解：
1、路径长度：从树种一个节点到另一个节点间的分支构成两个节点之间的路径，路径上的分支数目就是路径长度，所以路径长度是针对两个节点间距离的一种描述，如下图所示，根节点到D节点的路径长度为4
2、如上图所示，如果考虑每条路径的权重，根节点到节点D的路径长度为4*30 = 120，即无权路径长度*该节点权重值
假设n个节点的权值为{w1,w2,...wn}，这些节点对应的无权；路径长度为{l1,l2,...,ln}，该树的带权路径长度WPL则为根节点到其他所有节点带权路径长度之和，即WPL=∑ wk*lk,k从1到n
3、WPL最小时对应的二叉树被称为哈夫曼树，也叫做最优二叉树。
有了上面的基础知识介绍，下面给出一种java实现：
代码语言：javascript复制public class HuffmanTreeDemo {
@Test
public void test(){
Queue<Node> q = new PriorityQueue<>();
//先按照节点的权重进行降序排列
q.add(new Node('A',20,null,null));
q.add(new Node('G',10,null,null));
q.add(new Node('s',34,null,null));
q.add(new Node('K',16,null,null));
q.add(new Node('x',8,null,null));
q.add(new Node('q',5,null,null));
//至少保证有两个节点，因为在组成树时需要两个
while (q.size() >1){
Node n1 = q.poll();
Node n2 = q.poll();
Node n = new Node(' ',n1.getWeight() n2.getWeight(),n1,n2);
//将新形成的节点插入到队列中
q.add(n);
}
//最后一个节点就是根节点
Node root = q.poll();
//打印哈夫曼树
printHuffman(root);
}
/**
* 采用前序遍历
* @param node
*/
private void printHuffman(Node node){
if(node == null){
return;
}
println(node.getWeight());
printHuffman(node.getLeft());
printHuffman(node.getRight());
}
}
//节点
@Getter
public class Node implements Comparable<Node>{
private char ch;
private int weight;
private final Node left;
private final Node right;
public Node(char ch,int weight,Node left,Node right){
this.ch = ch;
this.weight = weight;
this.left = left;
this.right = right;
}
public boolean isLeaf(){
return left == null && right == null;
}
@Override
public int compareTo(Node node){
return this.weight - node.weight;
}
}拿上面这些数据来说明构造哈夫曼树的整个过程，如6个数，按照权重值进行排序后为5,8,10,16,20,34
然后根据排序抽出这些数据中最小的两个数，以这两个数作为左右子树构造新的父节点，该例子来说就是拿5和8两个节点，构造新的父节点13，然后将5,8,从待排序数组中删除，将新生成的13插入到队列中形成新的数组10,13,16,20,34，依次类推。
