Netjava Lesson 16 重温旧识——哈夫曼树

2013.09.24

 

今天我们来重温一下以前学习的关于哈夫曼树的构建。

 

回顾一下，我们给定了一些节点，每个节点都有对应的数值，现在我们要用这些节点生成二叉树，而且要求加权路径最小，即权值乘以节点对应的数值，然后再求和，我们要求的是这个最小。比如我们现在有64个节点，要是按照平时，我们会将64个节点一字排开，然后两两生成父节点，然后父节点再生父节点，直至生成以二叉树。但是这样的话我们显然可以看出加权路径不是最优的，因为大数值点和小数值点在一个水平上。我们如果要实现加权路径最小，那么我们就更希望小数值节点在下面，而大数值节点在上面。哈夫曼树的构建正是基于这一原理，实现了对字符串的压缩，进而可以去实现对于文件的压缩。

 

在进行压缩前，我们先定义一个节点类：

public class Node {
	Node left;//左节点
	Node right;//右节点
	char ch;//节点对应的字符
	int num;//数值
}

 

还有就是编码类：

public class Code {
	private char ch;// 字符
	private int num;// 出现次数
	private String str;// 对应编码
}

 

当然基础类还会有构造方法和get，set方法，我们这里就不一一阐述了。

 

然后我们就要来构建哈夫曼树：
首先我们定义两个队列：

ArrayList<Code> code = new ArrayList<Code>();
ArrayList<Node> node = new ArrayList<Node>();

code用于存放编码，node用于存放节点。

 

下面我们就要开始进行哈夫曼树的构建了：
1、我们要开始字符串的统计，并将字符和其出现次数生成编码存到编码队列里：

	public void countString(String str) {
		char[] ch = str.toCharArray();
		for (int i = 0; i < ch.length; i++) {
			boolean bol = true;
			for (int j = 0; j < code.size(); j++) {
				if (ch[i] == code.get(j).getCh()) {
					code.get(j).setNum(code.get(j).getNum() + 1);
					bol = false;
				}
			}
			if (bol) {
				code.add(new Code(ch[i]));
			}
		}
	}

 

2、创建哈夫曼树：

	public void creatTree() {
		for (int i = 0; i < code.size(); i++) {
			node.add(new Node(code.get(i).getCh(), code.get(i).getNum()));// 将叶子节点输入
		}
		sortNode();// 进行编码排序
		while (node.size() > 1) {
			Node temp = new Node(node.get(0), node.get(1), node.get(0).getNum()
					+ node.get(1).getNum());
			node.remove(0);
			node.remove(0);
			node.add(temp);
			sortNode();
		}
	}

 

 其中用到sortNode方法，是用来对节点对应的数值进行一个排序：

	private void sortNode() {
		for (int i = 0; i < node.size(); i++) {
			for (int j = i; j < node.size(); j++) {
				if (node.get(i).getNum() > node.get(j).getNum()) {
					Node node1 = node.get(i);
					Node node2 = node.get(j);
					node.set(i, node2);
					node.set(j, node1);
				}
			}
		}
	}

 

3、根据节点生成码表：

	public void creatCodeList() {
		String str = new String();
		codeList(node.get(0), str);
		for (int i = 0; i < code.size(); i++) {
			System.out.println(code.get(i).getCh() + "   "
					+ code.get(i).getStr());
		}
	}

 

这里我们用递归来生成码表，写了codeList方法：

	private void codeList(Node node, String str) {
		if (node.left == null && node.right == null) {
			for (int i = 0; i < code.size(); i++) {
				if (code.get(i).getCh() == node.getCh()) {
					code.get(i).setStr(str);
				}
			}
		}
		if (node.left != null) {
			codeList(node.left, str + "0");
		}
		if (node.right != null) {
			codeList(node.right, str + "1");
		}
	}

 

4、根据码表生成最终编码：

	public String printCodeList(String s) {
		char[] ch = s.toCharArray();
		String str = new String();
		for (int i = 0; i < ch.length; i++) {
			for (int k = 0; k < code.size(); k++) {
				if (code.get(k).getCh() == ch[i]) {
					str += code.get(k).getStr();
					break;
				}
			}
		}
		System.out.println(str);
		return str;
	}

 

5、根据码表和生成的编码还原编码：

	public String restoreCodeList(String codeStr) {
		String str = new String();
		for (int i = 0; i < codeStr.length(); i++) {
			for (int j = i; j <= codeStr.length(); j++) {
				String temp = codeStr.substring(i, j);
				for (int k = 0; k < code.size(); k++) {
					if (code.get(k).getStr().equals(temp)) {
						str += code.get(k).getCh();
						i = j;
					}
				}
			}
		}
		System.out.println(str);
		return str;
	}

 

这样，哈夫曼树的构建就完成了，下一次我们就会讲如何利用哈夫曼树实现文件的压缩，敬请期待~