Netjava project 压缩的实现（1）——哈夫曼树

我们都用过压缩软件，今天我们要讲的就是压缩软件的一种方法——哈夫曼树！

哈夫曼树其实是二叉树的一种。
我们给定一些权值作为二叉树的叶子节点，来构建一个二叉树，若带权路径长度达到最小，这样的二叉树成为最优二叉树，也就是我们说的哈夫曼树。
我们今天不仅要构建一个哈夫曼树，还要实现压缩一个字符串，让字符串以更短的方式表现出来。

?

准备工作：进行节点和编码类的设置。
Node类：

public class Node implements Comparable {private int data;// 节点的数据private Node left;// 左节点private Node right;// 右节点private String sign;// 字符标志/** * 构造方法 *  * @param data要输入的数据 */public Node(int data) {this.data = data;}/** * 构造方法 *  * @param data要输入的数据 * @param left左节点 * @param right右节点 */public Node(int data, Node left, Node right) {this.data = data;this.left = left;this.right = right;}/** * 重写比较方法 */public int compareTo(Object o) {double temp = this.data - ((Node) o).data;return temp > 0 ? 1 : temp == 0 ? 0 : -1;// 若原节点比比较节点大，返回1，相等返回0，小于返回-1}public int getData() {return data;}public void setData(int data) {this.data = data;}public Node getLeft() {return left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return right;}public void setRight(Node right) {this.right = right;}public String getSign() {return sign;}public void setSign(String sign) {this.sign = sign;}}

?

Code类：

?

public class Code {private String sign;// 编码长度private String node;// 编码private int length;// 长度public Code() {}public String getSign() {return sign;}public void setSign(String sign) {this.sign = sign;}public String getNode() {return node;}public void setNode(String node) {this.node = node;}public int getLength() {return length;}public void setLength(int length) {this.length = length;}}

?

下面我们开始实现字符串压缩：

1、统计：
我们知道文件是由字符一个个组成的，那我们首要的工作就是统计各个字符的个数。

/** * 数字符串中字符个数 *  * @param str字符串 */private void CharCount(char[] ch) {int len = ch.length;// 获取字符串长度// 对字符串进行循环for (int i = 0; i < len; i++) {boolean bol = true;// 创建临时变量bol，讨论字符以前是否出现过for (int j = 0; j < i; j++) {// 遍历i位置以前的字符，如果出现过，设置bol为否if (ch[i] == ch[j])bol = false;}int counts = 0;// 定义数字符的变量if (bol) // 如果以前没有出现过{counts++;// 这个字符的数量加一for (int k = i + 1; k < len; k++) {// 对这个字符的后面进行循环，如果出现了，count就加一if (ch[k] == ch[i])counts++;}}// 如果数出来的数量不为0，记录字符和它的数量if (counts != 0) {count[num] = new Code();count[num].setLength(counts);count[num].setNode(ch[i] + "");num++;}}}

?

2、排序：
统计完各个字符的个数，我们要对字符进行排序：

ArrayList<Node> nodelist = new ArrayList<Node>();// 建立队列// 循环将字符串中的个数输入队列for (int i = 0; i < num; i++) {Node temp = new Node(count[i].getLength());temp.setSign(count[i].getNode());nodelist.add(temp);// 将节点加入队列中}Collections.sort(node);// 对队列排序

?

3、构建哈夫曼树
下面我们开始构建哈夫曼树。
构建的流程是这样的：我们首先进行排序，寻找权值最小的两个叶子节点，将他们的值相加，然后将相加的值构成新的叶子节点放在最后，然后将原来两个节点移除，就这样一直进行，直至最后只剩一个节点，这个节点就为根节点。
知道原理，我们就可以利用队列来构建哈夫曼树啦~

/** * 构建哈夫曼树 *  * @param node要输入的节点队列 * @return 根节点 */public Node bulid(List<Node> node) {Collections.sort(node);// 对队列排序// 进行循环，如果队列的长度大于1while (node.size() > 1) {CreatAndReplace(node);// 调用替代方法}return node.get(0);// 返回根节点}/** * 替代方法 *  * @param node节点队列 */public void CreatAndReplace(List<Node> node) {Node left = node.get(0);// 获取第一个节点给左节点Node right = node.get(1);// 获取第二个节点给右节点Node root = new Node(left.getData() + right.getData());// 新建一个节点，数据是左右节点之和root.setLeft(left);// 设置新节点的左节点root.setRight(right);// 设置新节点的右节点node.remove(0);// 移除第一个节点node.remove(0);// 移除第二个节点node.add(root);// 将根节点加入到队列中去Collections.sort(node);// 对节点进行排序}

?

4、遍历，输出码表
得到二叉树后，我们以向左用0表示，向右用1表示，依次类推，可以得到码表。

/** * 得到编码的方法 *  * @param root根节点 * @param s字符串 */public void getCode(Node root, String s) {if (root.getLeft() == null && root.getRight() == null) {code[codenum] = new Code();// 新建一个编码对象code[codenum].setSign(root.getSign());// 将标志设置为节点的标志code[codenum].setNode(s);// 将s设置为编码codenum++;System.out.print("节点" + root.getSign() + "编码" + s + "       ");}if (root.getLeft() != null) {// 如果在左边，编码加上0getCode(root.getLeft(), s + "0");}if (root.getRight() != null) {// 如果在右边，编码加上1getCode(root.getRight(), s + "1");}}

?

5、根据码表生成01串编码
根据码表和对应的字符，我们可以用码表上的01串来表示字符啦！

/** * 输出树 *  * @param root根节点 */private static void printTree(Node node) {Node left = null;// 创建左节点Node right = null;// 创建右节点if (node != null) // 如果跟不为空{left = node.getLeft();// 设置left为根的左节点right = node.getRight();// 设置右节点为node的右节点System.out.print(node.getData());// 打印node的数据System.out.print("(" + (left != null ? left.getData() : " ") + ","+ (right != null ? right.getData() : " ") + ")    ");}if (left != null)// 如果左节点不为空，打印左子树的printTree(left);if (right != null)// 如果右节点不为空，打印右子树的printTree(right);}//我们在主函数中调用getCode(root, "");// 得到每个节点的编码String strcode = "";for (int i = 0; i < ch.length; i++) {for (int j = 0; j < num; j++) {if (code[j].getSign().equals(ch[i] + "")) {strcode += code[j].getNode();}}}System.out.println("\n" + strcode);

?

6、根据01串编码还原字符串
根据01串和码表，我们可以将字符还原回来：

char[] chtemp = strcode.toCharArray();String temp = "";// 反压缩for (int i = 0; i < strcode.length(); i++) {temp = temp + chtemp[i];for (int j = 0; j < num; j++) {if (temp.equals(code[j].getNode())) {System.out.print(code[j].getSign());temp = "";}}}

?