什么是哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
简介
在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+...+WnLn），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。
基本术语
1. 路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2. 结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
**3. ** 树的带权路径长度'
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
构造
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
实现代码：
import java.util.*;
public class Huffman {
public static void main(String[] args) {
int[] arr = {10, 5, 1, 2, 9, 15, 6, 3, 4};
long start = System.currentTimeMillis();
System.out.println("没优化前：");
TreeNode root = CreateHuffman(arr);
System.out.println("前序遍历结果：");
PreTraver(root);
long end = System.currentTimeMillis();
System.out.println("共耗时：" + (end - start) + "ms");
System.out.println("----------------------------------");
start = System.currentTimeMillis();
System.out.println("优化后：");
TreeNode rootByPQ = creatHuffmanByPriorityQueue(arr);
System.out.println("前序遍历结果：");
PreTraver(rootByPQ);
end = System.currentTimeMillis();
System.out.println("共耗时：" + (end - start) + "ms");
}
/**
* 未经过优化
* @param arr
* @return
*/
public static TreeNode CreateHuffman(int[] arr) {
List<TreeNode> treeNodes = new ArrayList<TreeNode>();
for (int i = 0; i < arr.length; i++) {
treeNodes.add(new TreeNode(arr[i], null, null));
}
//如果treenodes长度为1，则哈夫曼树创建好了，只剩下根结点
while (treeNodes.size() > 1) {
//使用Collections集合对treenodes进行排序
Collections.sort(treeNodes, new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.getNo() - o2.getNo();
}
});
//排序之后，取出头两个进行创建结点
TreeNode left = treeNodes.get(0);
TreeNode right = treeNodes.get(1);
TreeNode parent = new TreeNode(left.getNo() + right.getNo(), null, null);
//根结点创建好之后，将左右结点接上去,并将根结点加入集合
parent.setLeft(left);
parent.setRight(right);
treeNodes.add(parent);
//之后将头两个节点删除
treeNodes.remove(left);
treeNodes.remove(right);
}
return treeNodes.get(0);
}
/**
* 经过优先队列优化
* @param arr
* @return
*/
public static TreeNode creatHuffmanByPriorityQueue(int[] arr) {
//构造结点依次加入优先队列
Queue<TreeNode> pq = new PriorityQueue<TreeNode>(new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.getNo() - o2.getNo();
}
});
for (int i = 0; i < arr.length; i++) {
pq.offer(new TreeNode(arr[i], null, null));
}
//当队列中只剩一个元素时，Huffman树就创建完成了
while(pq.size() > 1){
//从优先队列中取出值最小的两个结点
TreeNode left = pq.poll();
TreeNode right = pq.poll();
//创建父结点
TreeNode parent = new TreeNode(left.getNo() + right.getNo(),null,null);
//为父结点添加左右孩子
parent.setLeft(left);
parent.setRight(right);
//加入优先队列
pq.offer(parent);
}
return pq.poll();
}
public static void PreTraver(TreeNode root) {
if (root != null) {
System.out.print(root.getNo() + " ");
PreTraver(root.getLeft());
PreTraver(root.getRight());
}
}
}
/**
* Huffman树的结点
*/
class TreeNode {
private int no; //编号
private TreeNode left; //左结点
private TreeNode right; //右节点
public TreeNode(int no, TreeNode left, TreeNode right) {
this.no = no;
this.left = left;
this.right = right;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
示例结果：
评论