?哈夫曼算法一般用來實現數據壓縮，以另外一種規則存儲數據，從而達到壓縮的功能。
?
????? 以下是我編寫的一個哈夫曼樹的例子：
?????
????? 程序描述 ：1.傳入一個字符串，將之分解，得到每個字符的個數，個數即為權值????
?????????????????????2.將每一個字符和他的權值傳入一個HFMNode對象中，?再將該對象傳入一個隊列中
???????????????????? 3.將隊列中的HFMNode對象按權值大小排序，每次取其中權值最小的兩個對象，生成一個二叉樹，
??????????????????????? 向array中刪除這兩個權值最小的節點，同時添加該兩對象的父節點
???????????????????? 4.編碼?? 按規則：從根節點開始，向左走一步編碼加+1，向右走一步編碼+0
?
?
???? 以下為源碼：
?
?哈夫曼節點的類
package tree;???????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
public class HFMNode {??????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? //節點一共有三種：????????????????????????????????????????????????????????????????????????????????????????
? //1.根節點????????? 根節點沒有父節點?????????????????????????????????????????????????????????????????????????
? //2.葉節點????????? 沒有子節點????????????????????????????????????????????????????????????????????????????
? //3.中間節點???? 有父節點和子節點?????????????????????????????????????????????????????????????????????????????
? private? HFMNode parent ;?????????????????????????????????????????????????????????????????????????
? private? HFMNode leftChild ;??????????????????????????????????????????????????????????????????????
? private? HFMNode rightChild;??????????????????????????????????????????????????????????????????????
? private? char s ;//節點所儲存的字符???????????????????????????????????????????????????????????????????????
? private? int weight=0 ;//所儲存節點的權值?????????????????????????????????????????????????????????????????
? private? String code="" ;//字符對應的哈夫曼編碼?????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setParent(HFMNode parent){????????????????????????????????????????????????????????????
?? this.parent = parent ;????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public HFMNode getParent(){???????????????????????????????????????????????????????????????????????
?? return this.parent ;??????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setLeftChild(HFMNode leftChild){??????????????????????????????????????????????????????
?? this.leftChild = leftChild ;??????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public HFMNode getLeftChild(){????????????????????????????????????????????????????????????????????
?? return this.leftChild ;???????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setRightChild(HFMNode rightChild){????????????????????????????????????????????????????
?? this.rightChild = rightChild ;????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public HFMNode getRightChild(){???????????????????????????????????????????????????????????????????
?? return this.rightChild ;??????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setWeight(int weight){????????????????????????????????????????????????????????????????
?? this.weight = weight ;????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public int getWeight(){???????????????????????????????????????????????????????????????????????????
?? return this.weight ;??????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setChar(char s){??????????????????????????????????????????????????????????????????????
?? this.s = s ;??????????????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public char getChar(){????????????????????????????????????????????????????????????????????????????
?? return this.s ;???????????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????
? public void setCode(String code){?????????????????????????????????????????????????????????????????
?? this.code = code ;????????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
? public String getCode(){??????????????????????????????????????????????????????????????????????????
?? return this.code ;????????????????????????????????????????????????????????????????????????????
? }?????????????????????????????????????????????????????????????????????????????????????????????????
}??
?
?
?
?
哈夫曼樹的類
?????
package tree;???????????????????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????????????????
import java.util.ArrayList;?????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????????????????
public class
ConstructHFM
{?????????????????????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????????????????????????????????????????
?private String data ;//傳入的字符串???????????????????????????????????????????????????????????????????????????????
?private ArrayList<HFMNode>
array
= new ArrayList<HFMNode>();????????????????????????????????????????????????
?private ArrayList<HFMNode>
nodeArray
= new ArrayList<HFMNode>();//儲存所有的節點 ??????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????????
?
public
ConstructHFM(String data)
{???????????????????????????????????????????????????????????????????????????
??this.data = data ;??????????????????????????????????????????????????????????????????????????????????????
?}????????????????????????????????????????????????????????????????????????????????????????????????????????????
???/**
??? *得到字符串的編碼
????*/???????????????????????????????????????????????????????????????????????????????????????????????
?
public
void getStringCode()
{????????????????????????????????????????????????????????????????????????????????
??this.setTreeNode();?????????????????????????????????????????????????????????????????????????????????????
??this.sortAndConsTree();?????????????????????????????????????????????????????????????????????????????????
??this.setEveryCharCode(array.get(0));????????????????????????????????????????????????????????????????????
??String allCode = this.getAllCode();?????????????????????????????????????????????????????????????????????
??System.out.println("*******************************************************");??? ???????????????????????
??System.out.println(data+"的哈夫曼編碼是："+allCode);????????????????????????????????????????????????????????????
?}???????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?/**?????????????????????????????????????????????????????????????????????????????????????????????????????????
? * 得到不同的字符總數，???????????????????????????????????????????????????????????????????????????????????????????????
? * 將每一個字符和他的權值傳入一個HFMNode對象中，???????????????????????????????????????????????????????????????????????????????
? * 將此對象添加入隊列中???????????????????????????????????????????????????????????????????????????????????????????????
? */?????????????????????????????????????????????????????????????????????????????????????????????????????????
?
public void setTreeNode()
{??????????????????????????????????????????????????????????????????????????????????
??char[] s = data.toCharArray();??????????????????????????????????????????????????????????????????????????
??int[] charCount = new int[s.length];//與字符數組相對應，記錄對應字符的個數????????????????????????????????????????????????
??for(int i=0 ;i<charCount.length ;i++){??????????????????????????????????????????????????????????????????
???charCount[i] = 1 ;??????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??//得到字符的數目，以及每個字符的個數?????????????????????????????????????????????????????????????????????????????????????
??for(int i=0 ; i<s.length ;i++){?????????????????????????????????????????????????????????????????????????
???for(int j=0 ; j<i ;j++){????????????????????????????????????????????????????????????????????????????
????if(s[i]==s[j]){?????????????????????????????????????????????????????????????????????????????????
?????charCount[j]++;?????????????????????????????????????????????????????????????????????????????
?????charCount[i]=0;?????????????????????????????????????????????????????????????????????????????
?????break;??????????????????????????????????????????????????????????????????????????????????????
????}???????????????????????????????????????????????????????????????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??//將字符傳入及節點對象????????????????????????????????????????????????????????????????????????????????????????????
??for(int i=0 ;i<s.length ;i++){??????????????????????????????????????????????????????????????????????????
???if(charCount[i]!=0){????????????????????????????????????????????????????????????????????????????????
????HFMNode? h = new HFMNode();?????????????????????????????????????????????????????????????????????
????h.setChar(s[i]) ;???????????????????????????????????????????????????????????????????????????????
????h.setWeight(charCount[i]);??????????????????????????????????????????????????????????????????????
????array.add(h);???????????????????????????????????????????????????????????????????????????????????
????nodeArray.add(h);???????????????????????????????????????????????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
?}???????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?/**?????????????????????????????????????????????????????????????????????????????????????????????????????????
? *? 將隊列array中的每個HFMNode對象按權值排序 ，????????????????????????????????????????????????????????????????????????????
? *? 取得最后兩個對象生成二叉樹，??????????????????????????????????????????????????????????????????????????????????????????
? *? 刪除這2個節點，添加其構成的父節點???????????????????????????????????????????????????????????????????????????????????????
? *? 且當array中只有一個元素時，該元素為根節點?????????????????????????????????????????????????????????????????????????????????
? */?????????????????????????????????????????????????????????????????????????????????????????????????????????
?
public void sortAndConsTree()
{??????????????????????????????????????????????????????????????????????????????
??while(array.size()>=2){//冒泡排序???????????????????????????????????????????????????????????????????????????
???for(int i=0;i<array.size();i++){????????????????????????????????????????????????????????????????????
????HFMNode tem = array.get(i) ;????????????????????????????????????????????????????????????????????
????for(int j=i+1;j<array.size();j++){??????????????????????????????????????????????????????????????
?????if(array.get(j).getWeight()>tem.getWeight()){???????????????????????????????????????????????
??????array.set(i, array.get(j));?????????????????????????????????????????????????????????????
??????array.set(j, tem);??????????????????????????????????????????????????????????????????????
??????tem = array.get(i);?????????????????????????????????????????????????????????????????????
?????}???????????????????????????????????????????????????????????????????????????????????????????
????}???????????????????????????????????????????????????????????????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
???????????????????????????????????????????????????????????????????????????????????????????????????????
???HFMNode parent = new HFMNode();?????????????????????????????????????????????????????????????????????
???int len = array.size();?????????????????????????????????????????????????????????????????????????????
???HFMNode last = array.get(len-1) ;???????????????????????????????????????????????????????????????????
???HFMNode lastSecond = array.get(len-2);??????????????????????????????????????????????????????????????
???parent.setLeftChild(last);??????????????????????????????????????????????????????????????????????????
???last.setParent(parent);?????????????????????????????????????????????????????????????????????????????
???parent.setRightChild(lastSecond);???????????????????????????????????????????????????????????????????
???lastSecond.setParent(parent);???????????????????????????????????????????????????????????????????????
???int? leftWeight =? last.getWeight() ;????????????????????????????????????????????????????????????????
???int? rightWeight = lastSecond.getWeight() ;?????????????????????????????????????????????????????????
???parent.setWeight(leftWeight + rightWeight);?????????????????????????????????????????????????????????
???array.remove(len-1);????????????????????????????????????????????????????????????????????????????????
???array.remove(len-2);????????????????????????????????????????????????????????????????????????????????
???array.add(parent);??????????????????????????????????????????????????????????????????????????????????
???nodeArray.add(parent);??????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
?}???????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?/**?????????????????????????????????????????????????????????????????????????????????????????????????????????
? * 打印每個字符的哈夫曼編碼?????????????????????????????????????????????????????????????????????????????????????????????
? * 從根節點開始，向左走一步編碼為1，向右為0????????????????????????????????????????????????????????????????????????????????????
? */?????????????????????????????????????????????????????????????????????????????????????????????????????????
?
public void setEveryCharCode
(HFMNode node){?????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??if(node.getLeftChild()!=null&&node.getRightChild()!=null){//判斷為葉節點??????????????????????????????????????
???node.getLeftChild().setCode(node.getCode() + 1);????????????????????????????????????????????????????
???node.getRightChild().setCode(node.getCode() + 0);???????????????????????????????????????????????????
???setEveryCharCode(node.getLeftChild());??????????????????????????????????????????????????????????????
???setEveryCharCode(node.getRightChild());?????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
?}???????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?/**?????????????????????????????????????????????????????????????????????????????????????????????????????????
? * 得到字符串的編碼?????????????????????????????????????????????????????????????????????????????????????????????????
? */?????????????????????????????????????????????????????????????????????????????????????????????????????????
?
public String? getAllCode()
{????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??//按權值順序打印所有葉節點的字符和編碼????????????????????????????????????????????????????????????????????????????????????
??for(int i=0;i<nodeArray.size();i++){????????????????????????????????????????????????????????????????????
???HFMNode tem = nodeArray.get(i);?????????????????????????????????????????????????????????????????????
???for(int j=i+1;j<nodeArray.size();j++){??????????????????????????????????????????????????????????????
????if(nodeArray.get(j).getWeight()>tem.getWeight()){???????????????????????????????????????????????
?????nodeArray.set(i, nodeArray.get(j));?????????????????????????????????????????????????????????
?????nodeArray.set(j, tem);??????????????????????????????????????????????????????????????????????
?????tem = nodeArray.get(i);?????????????????????????????????????????????????????????????????????
????}???????????????????????????????????????????????????????????????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??//打印所有的字符的HFM編碼?????????????????????????????????????????????????????????????????????????????????????????
??System.out.println("******************以下是傳入字符串的權值和哈夫曼編碼");??????????? ???????????????????????????????????
??for(int j=0 ;j<nodeArray.size();j++){???????????????????????????????????????????????????????????????????
???HFMNode h = nodeArray.get(j);???????????????????????????????????????????????????????????????????????
???if(h.getChar()!='\u0000'){//char型變量的默認值為'\u0000'????????????????????????????????????????????????????
????System.out.println(h.getChar()+"的權值："+h.getWeight()+"? 哈夫曼編碼："+h.getCode());????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??System.out.println("*******************以下是生成的哈夫曼樹的結構");?????? ???????????????????????????????????????????
??//打印生成HFM樹的結構???????????????????????????????????????????????????????????????????????????????????????????
??for(int k=0;k<nodeArray.size();k++){????????????????????????????????????????????????????????????????????
???HFMNode hfm = nodeArray.get(k);?????????????????????????????????????????????????????????????????????
???if(hfm.getParent()==null){??????????????????????????????????????????????????????????????????????????
????System.out.println("第"+k+"個節點為根節點，其權值為："+hfm.getWeight());??????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
???else if(hfm.getLeftChild()==null&&hfm.getRightChild()==null){???????????????????????????????????????
????System.out.println("第"+k+"個節點為葉節點??? 字符為："+hfm.getChar()+" 權值："+hfm.getWeight()+"? 哈夫曼編碼為："+hfm.getCode());
???}???????????????????????????????????????????????????????????????????????????????????????????????????
???else{???????????????????????????????????????????????????????????????????????????????????????????????
????System.out.println("第"+k+"個節點為中間節點，其權值為："+hfm.getWeight());?????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??String allCode="" ;?????????????????????????????????????????????????????????????????????????????????????
??char[] c = data.toCharArray();??????????????????????????????????????????????????????????????????????????
??????????????????????????????????????????????????????????????????????????????????????????????????????????
??for(int i=0;i<c.length;i++){????????????????????????????????????????????????????????????????????????????
???for(int j=0;j<nodeArray.size();j++){//nodeArray中儲存有所有的節點,包括根節點和中間節點?????????????????????????????????
????if(c[i]==nodeArray.get(j).getChar()){???????????????????????????????????????????????????????????
?????allCode+=nodeArray.get(j).getCode();????????????????????????????????????????????????????????
?????break ;?????????????????????????????????????????????????????????????????????????????????????
????}???????????????????????????????????????????????????????????????????????????????????????????????
???}???????????????????????????????????????????????????????????????????????????????????????????????????
??}???????????????????????????????????????????????????????????????????????????????????????????????????????
??return allCode ;????????????????????????????????????????????????????????????????????????????????????????
?}???????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????
?public ArrayList<HFMNode> getArray(){???????????????????????????????????????????????????????????????????????
??return this.array ;?????????????????????????????????????????????????????????????????????????????????????
?}????????????????????????????????????????????????????????????????????????????????????????????????????????????
}??????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
?
?
測試類
????
??? 測試描述 ：??傳入一個字符串? String s = "abbcccddddeeeeeffffff"
????????????????????打印個字符的權值和哈夫曼編碼，以及生成哈夫曼樹的結構
package tree;
public class TestApp {
?public static void main(String[] args){
??String s = "abbcccddddeeeeeffffff" ;
??ConstructHFM? h = new ConstructHFM(s);
??h.getStringCode();
?}
}
測試結果
******************以下是傳入字符串的權值和哈夫曼編碼
f的權值：6? 哈夫曼編碼：01
e的權值：5? 哈夫曼編碼：10
d的權值：4? 哈夫曼編碼：11
c的權值：3? 哈夫曼編碼：000
b的權值：2? 哈夫曼編碼：0010
a的權值：1? 哈夫曼編碼：0011
*******************以下是生成的哈夫曼樹的結構
第0個節點為根節點，其權值為：21
第1個節點為中間節點，其權值為：12
第2個節點為中間節點，其權值為：9
第3個節點為中間節點，其權值為：6
第4個節點為葉節點??? 字符為：f 權值：6? 哈夫曼編碼為：01
第5個節點為葉節點??? 字符為：e 權值：5? 哈夫曼編碼為：10
第6個節點為葉節點??? 字符為：d 權值：4? 哈夫曼編碼為：11
第7個節點為葉節點??? 字符為：c 權值：3? 哈夫曼編碼為：000
第8個節點為中間節點，其權值為：3
第9個節點為葉節點??? 字符為：b 權值：2? 哈夫曼編碼為：0010
第10個節點為葉節點??? 字符為：a 權值：1? 哈夫曼編碼為：0011
*******************************************************
abbcccddddeeeeeffffff的哈夫曼編碼是：001100100010000000000111111111010101010010101010101
?
??
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
