基于数组实现的Huffman树和Huffman编码

一、Huffman树简介

1、定义

树的带权路径长度，就是树中所有的叶节点的权值乘上其到根节点的路径长度。

        在含有n 个带权叶子结点的二叉树中，其中带权路径长度（Weighted Path Length, WPL）最小的二叉树称为哈夫曼树， 也称最优二叉树。如图，c树的WPL=35最小，经验证其为哈夫曼树。

c树的WPL = 7*1 + 5*2 + 2*3 + 4*3 = 35

2、特点

假设有n个带权的节点

1）每个初始结点最终都成为叶结点，也就是这n个节点全都初始化为root节点。

2）构造过程中共新建了n-1个结点 （双分支结点），因此哈夫曼树的结点总数为2n- 1 。

3）每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为1 的结点。

举例：数组的长度已定，为2n - 1

二、算法实现思路和代码

实现思路

以 a 7 b 5 c 2 d 4为例：

1、定义节点类：

2、构建huffman树

1、先初始化n个节点：他们的parent、lchild和rchild全为-1，且它们在数组中的索引分别为0、1、2、3

2、将这n个节点两个两个的合并：每次选两个权值weight最小且parent等于-1的节点（要写一个selectMin方法获取最小的节点）

第一步：选两个权值weight最小且parent等于-1的节点

第二步：合并他们，则父节点的权重等于这两个子节点的权重的个，父节点的左右孩子分别为这两个子节点的索引，父节点的data值设置为null，对应代码：

ht[i] = new Node<>(null,ht[s1].weight + ht[s2].weight,-1,s1,s2);

第三步：设置子节点的parent为父节点在数组中的索引，对应代码：

ht[s1].parent = ht[s2].parent = i;

重复该步骤

节点上面为数组的下标

第一次：

第二次：

第三次：

构建完成。

3、完整代码

Node类：

public class Node<T>{T data;//存放字符double weight;//权重int parent;//父节点int lchild;//左孩子int rchild;//右孩子public Node(T data, double weight, int parent, int lchild, int rchild) {this.data = data;this.weight = weight;this.parent = parent;this.lchild = lchild;this.rchild = rchild;}
}

HuffmanTree类：

public class HuffmanTree <T>{Node<T>[] ht;//n个元素对应的节点的个数，2*n + 1String[] hc;//对应的字符编码int n;//n个权值public HuffmanTree(int n) {this.ht = new Node[2*n - 1];this.hc = new String[n];this.n = n;}//在0-  m-1中选择权值最小的节点public int selectMin(int m){int k = 0,i;//第一个parent不等于-1的（根节点）for (i = 0;i < m; i++) {if (ht[i].parent == -1){//找到根k = i;break;}}for (i += 1;i < m; i++) {if (ht[i].parent == -1 && ht[i].weight < ht[k].weight){k = i;}}ht[k].parent = -2;return k;}public void createTree(){int i,s1,s2;Scanner scanner = new Scanner(System.in);System.out.println("请输入" + this.n + "个元素的权值，用空格分割:");//创建n个叶子节点for (i = 0; i < n; i++) {T d = (T)scanner.next();//数据域double w = scanner.nextDouble();//权值ht[i] = new Node<>(d, w, -1, -1, -1);}//构造huffman树for (;i < this.ht.length; i++) {//选择权值最小的两个节点,这两个节点的parent为-1s1 = selectMin(i);s2 = selectMin(i);ht[s1].parent = ht[s2].parent = i;ht[i] = new Node<>(null,ht[s1].weight + ht[s2].weight,-1,s1,s2);}}public void displayTree(){for (int i = 0; i < ht.length; i++) {System.out.println("元素：" + ht[i].data + "，权值：" + ht[i].weight + "，父元素：" + ht[i].parent + ",左孩子：" + ht[i].lchild + "，右孩子：" + ht[i].rchild);}}}

三、Huffman编码

对于一颗Huffman树，向左为0，向右为1

每个编码的长度不会超过n-1，char[] cd = new char[n - 1];

public String(char[] value,int offset,int count):分配一个新的 String，它包含取自字符数组参数一个子数组的字符。offset  参数是子数组第一个字符的索引，count 参数指定子数组的长度。该子数组的内容已被复制；后续对字符数组的修改不会影响新创建的字符串。

过程：

代码：

 public void createCode(){for (int i = 0; i < n; i++) {//按顺序生成元素的codechar[] cd = new char[n - 1];int start = n - 2;//从后往前填充cd数组//从最下一层开始向上遍历，直到根节点，现在就根节点的parent=-1，其他的都不是-1for (int c = i, f = ht[c].parent; f != -1; c = f, f = ht[c].parent) {//找到当前节点是父节点的左孩子还是右孩子if (ht[f].lchild == c) {//左孩子cd[start--] = '0';} else {//右孩子cd[start--] = '1';}}hc[i] = new String(cd,start + 1,n - start - 2);}}

四、对电文进行解码和编码

1、编码

直接和ht数组的data比较，相同的话就拼接hc对应的code

 //将要发送的电文进行编码后返回public String textCode(String text){String codeStr = "";for (int i = 0; i < text.length(); i++) {//转换成String进行比较String s = String.valueOf(text.charAt(i));for (int j = 0; j < hc.length; j++) {if (ht[j].data.equals(s)){codeStr += hc[j];break;}}}return codeStr;}

2、解码

 //解码的操作public String textDecode(String text){String decodeStr = "";for (int i = 0; i < text.length();  i++) {int p = this.ht.length - 1;//从根开始进行遍历//遍历到叶子节点，叶子节点的lchild和rchild都是-1while(ht[p].lchild != -1 && ht[p].rchild != -1){char ch = text.charAt(i);//可能会数组越界if (ch == '0'){p = ht[p].lchild;}else{p = ht[p].rchild;}i++;}decodeStr += ht[p].data;i--;//循环结束后，i已经加1了，所以要减1,回退到上一个字符，不然会数组越界}return decodeStr;}

五、主类测试输出

public class Main {public static void main(String[] args) {System.out.println("请输入元素的个数：");Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();HuffmanTree<Character> huffmanTree = new HuffmanTree<>(n);huffmanTree.createTree();huffmanTree.displayTree();huffmanTree.createCode();huffmanTree.displayCode();String afterdataearareartarea = huffmanTree.textCode("abcd");System.out.println(afterdataearareartarea);String s = huffmanTree.textDecode(afterdataearareartarea);System.out.println(s);}
}

输出结果：

请输入元素的个数：
4
请输入4个元素的权值，用空格分割:a 7 b 5 c 2 d 4
元素：a，权值：7.0，父元素：6,左孩子：-1，右孩子：-1
元素：b，权值：5.0，父元素：5,左孩子：-1，右孩子：-1
元素：c，权值：2.0，父元素：4,左孩子：-1，右孩子：-1
元素：d，权值：4.0，父元素：4,左孩子：-1，右孩子：-1
元素：null，权值：6.0，父元素：5,左孩子：2，右孩子：3
元素：null，权值：11.0，父元素：6,左孩子：1，右孩子：4
元素：null，权值：18.0，父元素：-1,左孩子：0，右孩子：5
a元素的编码是：0
b元素的编码是：10
c元素的编码是：110
d元素的编码是：111
010110111
abcd