huffmantree.java

基于哈夫曼树的压缩解压程序源代码

package logical;

public class HuffmanTree {

	final int leafnum = 256;

	final int hufnum = 2 * leafnum - 1;

	final long max = 99999999;

	Node root;
	
	long[] w = new long[256]; // Store the weight of the Node

	int nodeNum; // Store the num of the total leaves

	private Node[] tree = new Node[hufnum];

	HuffmanTree(long[] weight) {
		// Initialization
		this.w = weight;
		this.tree = getTree();
		root = tree[tree.length -1];
	}

	public Node[] getTree() {

		nodeNum = 0;
		for (int i = 0; i < 256; i++) {

			// if the weight of the bytes is not 0,then creat a tree node
			if (w[i] != 0) {
				nodeNum++;
				tree[nodeNum - 1] = new Node();
				tree[nodeNum - 1].name = i;
				tree[nodeNum - 1].weight = w[i];
			}
		}

		// Creat huffman tree
		for (int i = nodeNum; i < (2 * nodeNum - 1); i++) {
			tree[i] = new Node();
			int p1, p2;
			long least1, least2; // Find the 2 least Node and creat a new
									// Node
			p1 = 0;
			p2 = 0;
			least1 = max;
			least2 = max;
			for (int j = 0; j < i; j++) {
				if (tree[j].parent == null) {
					if (tree[j].weight < least1) {
						least2 = least1;
						least1 = tree[j].weight;
						p2 = p1;
						p1 = j;
					} else if (tree[j].weight < least2) {
						least2 = tree[j].weight;
						p2 = j;
					}

				}
			}
			tree[i].weight = tree[p1].weight + tree[p2].weight;
			tree[p1].parent = tree[i];
			tree[p2].parent = tree[i];
			tree[i].lchild = tree[p1];
			tree[i].rchild = tree[p2];

		}
		tree[2 * nodeNum - 2].parent = null; // The root Node

		// Use Node array temp to change the length of tree
		Node[] temp = new Node[2 * nodeNum - 1];
		for (int z = 0; z < temp.length; z++) {
			temp[z] = tree[z];
		}
		tree = temp;
		return tree;
	}

	public String[] getCode() {

		String[] code = new String[256];
		StringBuffer buf;
		for (int j = 0; j < code.length; j++) {
			code[j] = "";
		}

		// Get the code from the Node up to the root
		int i;
		Node c, p;
		for (i = 0; i < nodeNum; i++) {
			buf = new StringBuffer();
			c = tree[i];
			p = tree[i].parent;
			while (p != null) {
				if (p.lchild == c) // if the node is the leafchild of its
									// parent
					buf.append('0');
				else
					// if the node is the right child of its parent
					buf.append('1');
				c = p;
				p = p.parent;
			}
			code[tree[i].name] = buf.reverse().toString();
		}

		return code;
	}

}