我们都用过压缩软件，今天我们要讲的就是压缩软件的一种方法——哈夫曼树！
哈夫曼树其实是hashu.html" target="_blank">二叉树的一种。
我们给定一些权值作为二叉树的叶子节点，来构建一个二叉树，若带权路径长度达到最小，这样的二叉树成为最优二叉树，也就是我们说的哈夫曼树。
我们今天不仅要构建一个哈夫曼树，还要实现压缩一个字符串，让字符串以更短的方式表现出来。
?
准备工作：进行节点和编码类的设置。
Node类：
class="java">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);// 对队列排序
// 进行循环，如果队列的长度大于1
while (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) {
// 如果在左边，编码加上0
getCode(root.getLeft(), s + "0");
}
if (root.getRight() != null) {
// 如果在右边，编码加上1
getCode(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 = "";
}
}
}
?
相关文章
