哈夫曼树相关名词
先看一棵哈夫曼树: (哈夫曼树推理是通过叶子节点，所以理解的时候需要忽略非叶子节点，很多文章在这点上有误导)
网络异常，图片无法展示
|
路径与路径长度: 从树中一个节点到另一个节点之间的分支构成了两个节点之间的路径，路径上的分支数目称作路径长度。若规定根节点位于第一层，则根节点到第H层的节点的路径长度为H-1。如到40 的路径长度为1；30的路径长度为2；20的路径长度为3。节点的权: 将树中的节点赋予一个某种含义的数值作为该节点的权值，该值称为节点的权；带权路径长度: 从根节点到某个节点之间的路径长度与该节点的权的乘积。例如上图节点10的路径长度为3,它的带权路径长度为10 * 3 = 30；树的带权路径长度: 树的带权路径长度为所有叶子节点的带权路径长度之和，称为WPL。上图的WPL = 1x40+2x30+3x10+3x20 = 190，而哈夫曼树就是树的带权路径最小的二叉树。
哈夫曼树的构建
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为:
- 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
- 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
- 从森林中删除选取的两棵树，并将新树加入森林；
- 重复上面两步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
上图中，它的叶子节点为{10，20，30，40}，以这4个权值构建哈夫曼树的过程为:
哈夫曼编码
为{10，20，30，40}这四个权值构建了哈夫曼编码后，我们可以由如下规则获得它们的哈夫曼编码:
从根节点到每一个叶子节点的路径上，左分支记为0，右分支记为1，将这些0与1连起来即为叶子节点的哈夫曼编码。如下图:
| (字母)权值 | 编码 |
| 10 | 100 |
| 20 | 101 |
| 30 | 11 |
| 40 | 0 |
| 由此可见，出现频率越高的字母(也即权值越大)，其编码越短。这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 |
具体流程如下:
哈夫曼树的实现
哈夫曼树的重点是如何构造哈夫曼树。本文构造哈夫曼时，用到了"(二叉堆)最小堆"。下面对哈夫曼树进行讲解。
- 哈夫曼树节点
public class HuffmanNode implements Comparable, Cloneable { protected int key; // 权值 protected HuffmanNode left; // 左孩子 protected HuffmanNode right; // 右孩子 protected HuffmanNode parent; // 父结点 protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) { this.key = key; this.left = left; this.right = right; this.parent = parent; } @Override public Object clone() { Object obj=null; try { obj = (HuffmanNode)super.clone();//Object 中的clone()识别出你要复制的是哪一个对象。 } catch(CloneNotSupportedException e) { System.out.println(e.toString()); } return obj; } @Override public int compareTo(Object obj) { return this.key - ((HuffmanNode)obj).key; } }
- 哈夫曼树
import java.util.List; import java.util.ArrayList; import java.util.Collections; public class Huffman { private HuffmanNode mRoot; // 根结点 /* * 创建Huffman树 * * @param 权值数组 */ public Huffman(int a[]) { HuffmanNode parent = null; MinHeap heap; // 建立数组a对应的最小堆 heap = new MinHeap(a); for(int i=0; i<a.length-1; i++) { HuffmanNode left = heap.dumpFromMinimum(); // 最小节点是左孩子 HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子 // 新建parent节点，左右孩子分别是left/right； // parent的大小是左右孩子之和 parent = new HuffmanNode(left.key+right.key, left, right, null); left.parent = parent; right.parent = parent; // 将parent节点数据拷贝到"最小堆"中 heap.insert(parent); } mRoot = parent; // 销毁最小堆 heap.destroy(); } /* * 前序遍历"Huffman树" */ private void preOrder(HuffmanNode tree) { if(tree != null) { System.out.print(tree.key+" "); preOrder(tree.left); preOrder(tree.right); } } public void preOrder() { preOrder(mRoot); } /* * 中序遍历"Huffman树" */ private void inOrder(HuffmanNode tree) { if(tree != null) { inOrder(tree.left); System.out.print(tree.key+" "); inOrder(tree.right); } } public void inOrder() { inOrder(mRoot); } /* * 后序遍历"Huffman树" */ private void postOrder(HuffmanNode tree) { if(tree != null) { postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+" "); } } public void postOrder() { postOrder(mRoot); } /* * 销毁Huffman树 */ private void destroy(HuffmanNode tree) { if (tree==null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; } public void destroy() { destroy(mRoot); mRoot = null; } /* * 打印"Huffman树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(HuffmanNode tree, int key, int direction) { if(tree != null) { if(direction==0) // tree是根节点 System.out.printf("%2d is root\n", tree.key); else // tree是分支节点 System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left"); print(tree.left, tree.key, -1); print(tree.right,tree.key, 1); } } public void print() { if (mRoot != null) print(mRoot, mRoot.key, 0); } }
