....差點忘記寫博客了...
?
?
哈夫曼樹 .. 其實就是只利用葉子結點來存儲要用信息的樹,只不過它在構造的時候就擁有了一個迷人的特性... 就是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萬次 ....
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
