建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
到底什么是哈夫曼樹(shù)啊，求例子
哈夫曼樹(shù)是給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman Tree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。
為封丘等地區(qū)用戶(hù)提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及封丘網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、封丘網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專(zhuān)業(yè)、用心的態(tài)度為用戶(hù)提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶(hù)的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！
例子：
1、將w1、w2、…，wn看成是有n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；
2、 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；
3、從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；
4、重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。
擴(kuò)展資料：
按照哈夫曼編碼構(gòu)思程序流程：
1、切割的順序是從上往下，直至數(shù)組中的元素全部出現(xiàn)在葉節(jié)點(diǎn)；
2、我們思路正好相反，從數(shù)組中找出最小的兩個(gè)元素作為最下面的葉節(jié)點(diǎn)，在向備選數(shù)組中存入這兩個(gè)葉節(jié)點(diǎn)的和（這個(gè)新的和加入累加運(yùn)算，這個(gè)和也就是所求的最小值的一部分，原因如上圖）。
3、以本題為例，備選數(shù)組中現(xiàn)有元素為{30，30}，再次取出兩個(gè)最小元素進(jìn)行求和，得到新的元素，回歸備選數(shù)組并記入累加。
4、上述2.3布重復(fù)執(zhí)行直至備選數(shù)組中只有一個(gè)元素，此時(shí)累加結(jié)束，返回累加值即可
5、求數(shù)組中的最小值，可以用小根堆進(jìn)行提取最為方便；此題用到了貪心的思路，即用相同的策略重復(fù)執(zhí)行，直至我們得到所需的結(jié)果。
參考資料來(lái)源:百度百科——哈夫曼樹(shù)
哈夫曼樹(shù)編碼的應(yīng)用（Java語(yǔ)言）
1）編寫(xiě)函數(shù)實(shí)現(xiàn)選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法
2）編寫(xiě)函數(shù)實(shí)現(xiàn)統(tǒng)計(jì)字符串中字符的種類(lèi)以及各類(lèi)字符的個(gè)數(shù)。
3）編寫(xiě)函數(shù)構(gòu)造赫夫曼樹(shù)。
4）編寫(xiě)函數(shù)實(shí)現(xiàn)由赫夫曼樹(shù)求赫夫曼編碼表。
5）編寫(xiě)函數(shù)實(shí)現(xiàn)將正文轉(zhuǎn)換為相應(yīng)的編碼文件。
6）編寫(xiě)函數(shù)實(shí)現(xiàn)將編碼文件進(jìn)行譯碼。
7）編寫(xiě)主控函數(shù)，完成本實(shí)驗(yàn)的功能。
哈夫曼編碼與譯碼 java
class HaffmanNode //哈夫曼樹(shù)的結(jié)點(diǎn)類(lèi)
{
int weight; //權(quán)值
int parent,left,right; //父母結(jié)點(diǎn)和左右孩子下標(biāo)
public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}
public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定權(quán)值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼樹(shù)的結(jié)點(diǎn)數(shù)組:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼編碼:");
for (int i=0; icode.length; i++)
System.out.println(code[i]);
}
}
哈夫曼編碼的譯碼過(guò)程的大致思路是什么？（不要代碼）
哈夫曼樹(shù)和字符編碼對(duì)應(yīng)你都弄完了，得到是如a :01 b :101對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系直接將像“asdsdfdfg”直接轉(zhuǎn)換為“01110101”這樣二進(jìn)制編碼。譯碼的時(shí)候，讀取二進(jìn)制編碼，先讀取一位，然后在關(guān)系表中查找該二進(jìn)制數(shù)對(duì)應(yīng)的字符，如果沒(méi)有找到，繼續(xù)讀取二位，然后繼續(xù)在關(guān)系表中查找該二位二進(jìn)制對(duì)應(yīng)的字符。如此循環(huán)，知道找到字符位置，然后將二進(jìn)制數(shù)替換為相應(yīng)的字符，知道所有的數(shù)都替換完為止。
文章名稱(chēng)：java哈夫曼樹(shù)代碼思路 哈夫曼樹(shù)編程
標(biāo)題URL：http://fisionsoft.com.cn/article/dopgdid.html
