....差點忘記寫博客了...

?

?

哈夫曼樹 .. 其實就是只利用葉子結點來存儲要用信息的樹,只不過它在構造的時候就擁有了一個迷人的特性... 就是WPL(帶權路徑長度)是最小的.. 而且還能用這個樹的來為葉子結點中的信息進行編碼, 得出來的各個編碼一定不會相同,并且不會產生混淆的情況..

?

通過哈夫曼樹的特點.實現了根據一個隊列來創建一棵哈夫曼樹的方法.

    /**
	 * 得到隨機產生的隊列
	 */
	public void setQueue() {
		Random rd = new Random();
		System.out.println("隨機產生的隊列為:");
		for (int i = 0; i < 10; i++) {
			int k = rd.nextInt(20);
			TreeNode tn = new TreeNode(k);
			queue.add(tn);
			System.out.print(k + " ");
		}
		System.out.println();
	}

	// 得到隊列
	public PriorityQueue<TreeNode> getQueue() {
		return queue;
	}

	// 建樹,while (queue.size()>=2)
	public TreeNode CreatTree(PriorityQueue<TreeNode> queue) {
		TreeNode lc = queue.poll();
		TreeNode rc = queue.poll();
		// 兩個最小的結點通過這個結點連接起來
		TreeNode tr = new TreeNode((Integer) lc.getData()
				+ (Integer) rc.getData());
		tr.setLchild(lc);
		tr.setRchild(rc);
		lc.setParent(tr);
		rc.setParent(tr);
		// 將其父結點放入隊列.
		queue.add(tr);
		return tr;// 將根結點返回.當返回到最后一個根結點時就構成了一棵樹
	}

  

?到此.. 哈夫曼樹就建成了. 接下來就是哈夫曼編碼了.這個的實現我用到了遞歸,并且是每個葉結點往回找

?

    /**
	 * 為每個葉結點編碼,返回字符串
	 * 
	 * @param leaf每次傳入一個葉結點
	 * @return以字符串形式返回每個葉結點的哈夫曼編碼
	 */
	public String ToCode(TreeNode leaf) {
		String s = "";
		// 葉結點存在雙親結點.
		if (leaf.getParent() != null) {
			if (leaf.getParent().getLchild() == leaf) {
				// 向父結點遞歸
				s = ToCode(leaf.getParent()) + 0;
				return s;// 葉結點為左孩子時,在遞歸得到的編碼后面加個0;
			} else if (leaf.getParent().getRchild() == leaf) {
				// 向父結點遞歸
				s = ToCode(leaf.getParent()) + 1;
				return s;// 葉結點為右孩子時,在遞歸得到的編碼后面加個1;
			}
		}
		return s;
	}
  

?

?通過這個方法.. 實現對哈夫曼樹中葉子結點進行哈夫曼編碼的

?

?

?

補充個.. 今天讀取文件中的字節時..發現0出現的次數是最多的 ... 讀了個162M的文件..?0的個數比其他的數出現的次數多了10萬次 ....
?

哈夫曼樹(最優二叉樹)