无码av不卡高清在线观看,亚洲综合无码一区二区加勒比按摩,69式69式69式毛片毛片毛片大全

本文目錄一覽

1，Huffman編碼的算法
2，Huffman是什么來的
3，什么是霍夫曼編碼
4，Huffman樹的應用
5，什么是哈夫曼算法
6，到底什么是哈夫曼樹啊求例子

1，Huffman編碼的算法

a:11 b:10 c:110 d:011 e:111

Huffman編碼的算法

2，Huffman是什么來的

人名：哈夫曼

我記得在《數據結構》里看到過，huffman編碼。是利用人名huffman叫的。

哈夫曼在百度查它是人名也是一種事物和一種理論方法請采納謝謝祝：家庭健康包括你

Huffman是什么來的

3，什么是霍夫曼編碼

霍夫曼（Huffman）編碼原理霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統計編碼。屬于無損壓縮編碼。霍夫曼編碼的碼長是變化的，對于出現頻率高的信息，編碼的長度較短；而對于出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。步驟進行：l）將信號源的符號按照出現概率遞減的順序排列。2）將兩個最小出現概率進行合并相加，得到的結果作為新符號的出現概率。 3）重復進行步驟1和2直到概率相加的結果等于1為止。4）在合并運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。5）記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。例：設信號源為 s＝｛s1, s2, s3, s4, s5｝對應的概率為p＝｛0.25，0.22，0.20, 0.18，0.15｝。根據字符出現的概率來構造平均長度最短的異字頭碼字?；粑绰幋a通常采用兩次掃描的辦法，第一次掃描得到統計結果，第二次掃描進行編碼。霍夫曼編碼具有一些明顯的特點：1) 編出來的碼都是異字頭碼，保證了碼的唯一可譯性。2) 由于編碼長度可變。因此譯碼時間較長，使得霍夫曼編碼的壓縮與還原相當費時。3) 編碼長度不統一，硬件實現有難度。4) 對不同信號源的編碼效率不同，當信號源的符號概率為2的負冪次方時，達到100％的編碼效率；若信號源符號的概率相等，則編碼效率最低。5) 由于"0"與"1"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。

什么是霍夫曼編碼

4，Huffman樹的應用

哈夫曼樹在一般的數據結構的書中，樹的那章后面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。首先介紹什么是哈夫曼樹。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)?？梢宰C明哈夫曼樹的WPL是最小的。哈夫曼在上世紀五十年代初就提出這種編碼時，根據字符出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（注：碼字即為符號經哈夫曼編碼后得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）然而怎樣構造一棵哈夫曼樹呢？最具有一般規(guī)律的構造方法就是哈夫曼算法。一般的數據結構的書中都可以找到其描述：一、對給定的n個權值二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。三、從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。用C語言實現上述算法，可用靜態(tài)的二叉樹或動態(tài)的二叉樹。若用動態(tài)的二叉樹可用以下數據結構： struct tree float weight; /*權值*/ union char leaf; /*葉結點信息字符*/ struct tree *left; /*樹的左結點*/ }; struct tree *right; /*樹的右結點*/ }; struct forest struct tree *ti; /* F中的樹*/ struct forest *next; /* 下一個結點*/ }; 例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。構造好哈夫曼樹后，就可根據哈夫曼樹進行編碼。例如：上面的字符根據其出現的概率作為權值構造一棵哈夫曼樹后，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼，即任一個字符的編碼都不是另一個字符的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對于編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規(guī)則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規(guī)定。這種編碼方法是靜態(tài)的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字符出現的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示范圍為0--2^32-1，這已足夠表示大文件中字符出現的頻率了）以便解壓時創(chuàng)建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼后得到的碼字存儲起來。靜態(tài)哈夫曼編碼方法有一些缺點：一、對于過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網絡，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁盤讀寫訪問會降低數據編碼的速度。因此，后來有人提出了一種動態(tài)的哈夫曼編碼方法。動態(tài)哈夫曼編碼使用一棵動態(tài)變化的哈夫曼樹，對第t+1個字符的編碼是根據原始數據中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態(tài)哈夫曼編碼可實時進行。動態(tài)哈夫曼編碼比靜態(tài)哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與算法的書籍。前面提到的JPEG中用到了哈夫曼編碼，并不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟后得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

5，什么是哈夫曼算法

題目的闡述：　　　以ｎ進制編碼方式對一個英文字串中的字符進行編碼，每個不同的字符其編碼不同．使得由新的編碼替代原串后總碼長最小，且輸入０，１，２，．．．，ｎ－１構成的數字串后，依照該編碼方式可以正確的對譯出唯一的英文原串．　　如：?。睿剑场∮⑽脑疄椤。幔猓猓悖猓幔洌洌幔悖? 　　其對應的一種編碼方式為　　ａ：００　?。猓海埃? 　　ｃ：０２０　?。洌海埃玻? 　　ｅ：０２２　　原串對譯后的編碼為０００１０１０２００１０００２１０２１０００２００２２　　其碼長為２７　　若輸入編碼串　　　?。埃保埃玻埃埃玻玻埃? 　　則對應的英文原串為?。猓悖澹? 分　析：　　假設英文原串中的字符存放于字符集ｓ中，‖ｓ‖＝?。?，每個字符在字串中出現的概率為ｗ［ｉ］，ｌ［ｉ］為字符ｉ的編碼長．　　依題意得，對ｓ集合中的不同字符進行ｎ進制編碼后要求　　　?。保┬伦执拇a長最短　　　　　　　　　?。鳎穑欤健疲鳎郏椋荩欤郏椋? （ｉ∈１．．ｘ）　　　　　　　　使得在ｗｐｌ是所有編碼方式中的最小值　　　?。玻┚幋a無二義性　　　　　　　　任意一字符編碼都不為其它字符編碼的前綴　　此題以哈夫曼樹來解答是非常適宜的．ｎ為此哈夫曼樹的分叉數，ｓ字符集里的元素即為此　　ｎ叉哈夫曼樹的葉子，概率ｗ［ｉ］即為葉子結點的權重，從根結點到各葉子結點的路徑長即為該葉子結點的編碼長ｌ［ｉ］．由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法，即權重越大的結點越靠近該樹的根，這樣，出現頻率越大的字符其編碼就越短．　　　　但具體應該怎樣建立起此ｎ叉哈夫曼樹呢？我們首先以ｎ＝２為例?。? 　?。螅剑?，ｂ，ｃ，ｄ｝　　ｗ＝［３，１，２，１］　　　首先從ｗ中選出兩個最小權，１，１，將其刪去，并以２（即１＋１）替代　　　?。鳎剑郏?，２，２］；　　再從新的ｗ中取出兩個最小權，２，２，將其刪去，并以４（即２＋２）替代　　　?。鳎剑郏常矗?；　　依此類推，直到ｗ中只一個值時合并結束，此時?。鳎剑郏罚? 　　以上兩兩合并的過程即為二叉哈夫曼樹的建立過程，每一次的合并即是將兩棵子樹歸于一個根結點下，于是可以建立二叉樹如下：　　　　　　　　　　　　　　　　　　　　　　　　m 　　　　　　　　　　　　　　　　　　　　　?。?　　?１　　　　　　　　　　　　　　　　　　　　　　m　　　m 　　　　　　　　　　　　　　　　　　　　?。帷　。?　　?１　　　　　　　　　　　　　　　　　　　　　　　m　　　　m 　　　　　　　　　　　　　　　　　　　　　　?。恪　。?　　?１　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　m　　　　　m 　　　　　　　　　　　　　　　　　　　　　　　　　ｂ　　　　　?。洹? 　ｍｉｎ－ｗｐｌ＝３＊１＋１＊３＋２＊２＋１＊３＝１３　從某一根結點出發(fā)走向其左子樹標記為０，走向其右子樹標記為１，則可以得到以下編碼 ?。?，ｂ，ｃ，ｄ對應的編碼為　　?。幔海? 　　　ｂ：１１０　　?。悖海保? 　　　ｄ：１１１ ?。睿剑硶r又是怎樣一種情況呢？　　設?。螅剑?，ｂ，ｃ，ｄ，ｅ｝　　　?。鳎剑郏?，４，２，５，３｝　　則按權重排序可得　　　?。螅剑?，ｂ，ｅ，ｃ，ａ｝　　　　　　　　?。鳎剑郏罚?，４，３，２］　　那么此哈夫曼樹的樹形應為怎樣呢？　　是以下的左圖，還是右圖，或是兩者均不是　　　　　　　　　　　m　　　　　　　　　　　　　　　　　　　m 　　　　　　　　?　　a　　　?　　　　　　　　　　　　　　　?　? 　　　　　　　m　　　m　　　l　　　　　　　　　　　　　　l　　m 　　　　　　?　?　　?　?　?。恪　　　　　　　　　　　　　　。帷?　?　　　　　　　　　　　　　l　　l　l　　l　　　　　　　　　　　　　　　　　　l　　m 　　　　?。帷　。洹。狻　。濉　　　　　　　　　　　　　　　　　。洹?　? 　　　　　　　　　　　　　　　　l　　　m 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　?。狻　?　? 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　l　l 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　?。濉。? 　顯然，要帶權路徑長ｗｐｌ最短，那么，此樹的高度就應盡可能的小，由此可知將此樹建成豐滿ｎ叉樹是最合理的，于是我們盡量使樹每一層都為ｎ個分枝．　　對于這道題的情況，我們具體來分析．　　按照哈夫曼樹的思想，首先從ｗ中取出權最小的三個值，即２，３，４，并以９（２＋３＋４）來代替，得到新的ｗ＝［９，７，５］；再將這三個值合并成９＋７＋５＝２１這個結點．于是得到三叉哈夫曼樹如下：　　　　　　　　　　　　　　　　　　　　　　　　　　m 　　　　　　　　　　　?　　a　　? 　　　　　　　　　　l　　　l　　　m 　　　　　　　　　?。洹　　。狻?　a　? 　　　　　　　　　　　　　　　　l　l　l 　　　　　　　　　　　　　　　?。濉。恪。? 　?。鳎穑欤剑保罚保担玻玻玻常玻矗剑常? 　　以０．．ｎ－１依次標記每個根結點的ｎ個分枝，則可以得到每個字符相對應的編碼：　　　?。幔海玻? 　　　?。猓海? 　　　?。悖海玻? 　　　　ｄ：０　　　?。澹海玻? 　　我們發(fā)現對于這種情況恰巧每層均為ｎ個分枝，但事實上并非所有的ｎ叉哈夫曼樹都可得到每層ｎ個分枝．例于當ｎ＝３，‖ｓ‖＝６時就不可能構成一棵每層都為三個分枝的三叉樹．如何來處理這種情況呢？　　最簡單的處理方式就是添加若干出現概率為０的空字符填補在ｎ叉樹的最下一層，這些權為０的虛結點并無實際意義但卻非常方全便于這棵ｎ叉樹的建立．空字符的添加個數ａｄｄ的計算如下：　?。健蟆。恚铮洹。ǎ睿保? 　?。幔洌洌剑啊　　。ǎ剑保　　? 　?。幔洌洌剑薄　　。ǎ剑埃? 　?。幔洌洌剑睿。ǎ荆保　? 　　虛結點的加入使得權重最小的ｎ－ａｄｄ個字符構成了距根結點最遠的分枝，使其它字符構成的ｎ叉樹保持了豐滿的ｎ叉結構．　　例：?。睿剑场? 　　　　?。螅剑幔?，ｃ，ｄ，ｅ，ｆ｝　　　　?。鳎剑郏保?，３，４，５，６｝　　則　ｙ：＝６?。恚铮洹。ǎ常保剑? 　　　　ａｄｄ＝１　　于是構成ｎ叉樹如下：　-為虛結點　　　　　　　　　　　　　　　　?　　　　　　　　　　　　　　?　　a　　? 　　　　　　　　　　　　l　　　l　　　　m 　　　　　　　　　　　?。妗　　。濉?　　a　　? 　　　　　　　　　　　　　　　　　　l　　l　　　m 　　　　　　　　　　　　　　　　　?。洹　。恪?　a　? 　　　　　　　　　　　　　　　　　　　　　　?。狻。帷? 　?。鳎穑欤剑保叮保担玻矗玻常常玻常保常埃剑常? 　　對應編碼為：　　　　ａ：２２１　　　?。猓海玻玻? 　　　?。悖海玻? 　　　　ｄ：２０　　　?。澹海? 　　　?。妫海?/section>

6，到底什么是哈夫曼樹啊求例子

哈夫曼樹是給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。例子：1、將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；2、在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；3、從森林中刪除選取的兩棵樹，并將新樹加入森林；4、重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。擴展資料：按照哈夫曼編碼構思程序流程：1、切割的順序是從上往下，直至數組中的元素全部出現在葉節(jié)點；2、我們思路正好相反，從數組中找出最小的兩個元素作為最下面的葉節(jié)點，在向備選數組中存入這兩個葉節(jié)點的和（這個新的和加入累加運算，這個和也就是所求的最小值的一部分，原因如上圖）。3、以本題為例，備選數組中現有元素為4、上述2.3布重復執(zhí)行直至備選數組中只有一個元素，此時累加結束，返回累加值即可5、求數組中的最小值，可以用小根堆進行提取最為方便；此題用到了貪心的思路，即用相同的策略重復執(zhí)行，直至我們得到所需的結果。參考資料來源:搜狗百科——哈夫曼樹

我們先看一個應用例子：假如你跟別人聊天，輸入了“AFTER DATA EAR ARE ART AREA”，要發(fā)給對方，在電腦的世界里，最終都是要將相關的字符轉換為0 1來表示的二進制來傳輸，這里用到的字符集為“A，E，R，T，F，D”，各字母出現的次數為為了獲得傳送報文的最短長度，可用字符集中的每個字符作為葉子結點生成一棵編碼二叉樹，可將每個字符的出現頻率作為字符結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下。于是我們構造這顆二叉樹的時候，應該先選擇最小權值的點來構造樹，新樹的權值為左右子樹的權值之和，然后新的權值放回到原來的權值序列中，再次選擇兩個權值最小的點來構造樹，如此循環(huán)最后只剩下一棵樹為止。我們以字符集為“A，E，R，T，F，D”，各字母出現的次數為首先選取兩個最小權值的點構造樹，新的權值放回到序列中，變?yōu)? / \1 1再次選擇兩個權值最小的點構造樹，序列變?yōu)槿缦拢? / \ 2 3 / \ 1 1按照上面的規(guī)則直到只有一顆樹為止 / \ / \ 2 3 4 5 / \1 1------------------------ / \ / \ 4 5 5 8 / \ 2 3 / \ 1 1------------------------ 22 / \ 9 13 / \ / \E4 R5 5 A8 / \ 2 T3 / \ F1 D1上面的的樹便是哈夫曼樹了（給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹）這顆樹每一個“/” 默認為0， “\”為1，就可以得到葉子結點的編碼：如上面F：1000 D：1001 A：11

這么明確的算法，肯定唯一，數如下： 1.00 / \ /0 \1 0.44 0.56 / \ / \ /0 \1 /0 \1 0.21 0.23 0.27 0.29 / \ /0 \1 0.13 0.16 / \ /0 \1 0.07 0.09編碼：0.07:11100.09:11110.13:1100.21:000.23:010.27:10沒有誰是誰的前綴，ok. 針對補充問題：不行，生成哈夫曼樹時總是取最小的兩個權值作為葉子。。針對補充問題002：上面那棵樹，從下往上看，所有權值中最小的兩個是0.07跟0.09，相加等0.16；原來的權值表成了：0.13，0.16(代替了0.07跟0.09),0.21，0.23，0.27；現在最小的兩個是0.13，0.16，相加得到0.29；之前的權值表又成了：0.21，0.23，0.27，0.29(代替了0.13跟0.16)；現在最小的兩個是0.21，0.23，相加得到0.44；之前的權值表又成了:0.27，0.29，0.44；接下來是一樣的。

一、哈夫曼樹的介紹Huffman Tree，中文名是哈夫曼樹或霍夫曼樹，它是最優(yōu)二叉樹。定義：給定n個權值作為n個葉子結點，構造一棵二叉樹，若樹的帶權路徑長度達到最小，則這棵樹被稱為哈夫曼樹。這個定義里面涉及到了幾個陌生的概念，下面就是一顆哈夫曼樹，我們來看圖解答。(1) 路徑和路徑長度定義：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規(guī)定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。例子：100和80的路徑長度是1，50和30的路徑長度是2，20和10的路徑長度是3。(2) 結點的權及帶權路徑長度定義：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。例子：節(jié)點20的路徑長度是3，它的帶權路徑長度= 路徑長度 * 權 = 3 * 20 = 60。(3) 樹的帶權路徑長度定義：樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL。例子：示例中，樹的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。比較下面兩棵樹上面的兩棵樹都是以左邊的樹WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右邊的樹WPL=290左邊的樹WPL > 右邊的樹的WPL。你也可以計算除上面兩種示例之外的情況，但實際上右邊的樹就是二、哈夫曼樹的圖文解析假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，哈夫曼樹的構造規(guī)則為：1. 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)； 2. 在森林中選出根結點的權值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和； 3. 從森林中刪除選取的兩棵樹，并將新樹加入森林； 4. 重復(02)、(03)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。以第1步：創(chuàng)建森林，森林包括5棵樹，這5棵樹的權值分別是5,6,7,8,15。第2步：在森林中，選擇根節(jié)點權值最小的兩棵樹(5和6)來進行合并，將它們作為一顆新樹的左右孩子(誰左誰右無關緊要，這里，我們選擇較小的作為左孩子)，并且新樹的權值是左右孩子的權值之和。即，新樹的權值是11。然后，將"樹5"和"樹6"從森林中刪除，并將新的樹(樹11)添加到森林中。第3步：在森林中，選擇根節(jié)點權值最小的兩棵樹(7和8)來進行合并。得到的新樹的權值是15。然后，將"樹7"和"樹8"從森林中刪除，并將新的樹(樹15)添加到森林中。第4步：在森林中，選擇根節(jié)點權值最小的兩棵樹(11和15)來進行合并。得到的新樹的權值是26。然后，將"樹11"和"樹15"從森林中刪除，并將新的樹(樹26)添加到森林中。第5步：在森林中，選擇根節(jié)點權值最小的兩棵樹(15和26)來進行合并。得到的新樹的權值是41。然后，將"樹15"和"樹26"從森林中刪除，并將新的樹(樹41)添加到森林中。此時，森林中只有一棵樹(樹41)。這棵樹就是我們需要的哈夫曼樹！三、哈夫曼樹的基本操作哈夫曼樹的重點是如何構造哈夫曼樹。本文構造哈夫曼時，用到了以前介紹過的"(二叉堆)最小堆"。下面對哈夫曼樹進行講解。1. 基本定義[html]view plaincopyprintHuffmanNode是哈夫曼樹的節(jié)點類。[html]view plaincopyprintHuffman是哈夫曼樹對應的類，它包含了哈夫曼樹的根節(jié)點和哈夫曼樹的相關操作。2. 構造哈夫曼樹[html]view plaincopyprint首先創(chuàng)建最小堆，然后進入for循環(huán)。每次循環(huán)時：(1) 首先，將最小堆中的最小節(jié)點拷貝一份并賦值給left，然后重塑最小堆(將最小節(jié)點和后面的節(jié)點交換位置，接著將"交換位置后的最小節(jié)點"之前的全部元素重新構造成最小堆)； (2) 接著，再將最小堆中的最小節(jié)點拷貝一份并將其賦值right，然后再次重塑最小堆； (3) 然后，新建節(jié)點parent，并將它作為left和right的父節(jié)點； (4) 接著，將parent的數據復制給最小堆中的指定節(jié)點。四、哈夫曼樹的完整源碼1. 哈夫曼樹的節(jié)點類(HuffmanNode.java)[html]view plaincopyprint2. 哈夫曼樹的實現文件(Huffman.java)[html]view plaincopyprint3. 哈夫曼樹對應的最小堆(MinHeap.java)[html]view plaincopyprint4. 哈夫曼樹的測試程序(HuffmanTest.java)[html]view plaincopyprint五個字符：a,b,c,d,e,它們出現的的頻率為8，14，10，4，18構造相應的哈夫曼樹，求出每個字符的哈夫曼編碼：哈夫曼樹：54/ \22 32/ \ / \c10 12 b14 e18/ \d4 a8哈夫曼編碼：a:011 b:10 c:00 d:010 e:11今天做題的時候，遇到了一個關于哈夫曼樹的題，由于一直不是很明白哈夫曼樹的構造過程，所以找了很多資料都不是特別清楚的，直到我遇到了這篇文章，哈哈，在此分享給大家哦！注意：哈夫曼樹并不唯一，但帶權路徑長度一定是相同的。（1）8個結點的權值大小如下：（2）從19，21，2，3，6，7，10，32中選擇兩個權小結點。選中2，3。同時算出這兩個結點的和5。（3）從19，21，6，7，10，32，5中選出兩個權小結點。選中5，6。同時計算出它們的和11。（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（5）從19，21，32，11，17中選出兩個權小結點。選中11，17。同時計算出它們的和28。（6）從19，21，32，28中選出兩個權小結點。選中19，21。同時計算出它們的和40。另起一顆二叉樹。（7）從32，28， 40中選出兩個權小結點。選中28，32。同時計算出它們的和60。（8）從 40， 60中選出兩個權小結點。選中40，60。同時計算出它們的和100。好了，此時哈夫曼樹已經構建好了。這是原作者的鏈接哦，我覺得還不錯呢，大家可以去看看的！注意：哈夫曼樹并不唯一，但帶權路徑長度一定是相同的。（1）8個結點的權值大小如下：（2）從19，21，2，3，6，7，10，32中選擇兩個權小結點。選中2，3。同時算出這兩個結點的和5。（3）從19，21，6，7，10，32，5中選出兩個權小結點。選中5，6。同時計算出它們的和11。（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。（BTW：這時選出的兩個數字都不是已經構造好的二叉樹里面的結點，所以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那么這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那么就并列生長。）（5）從19，21，32，11，17中選出兩個權小結點。選中11，17。同時計算出它們的和28。（6）從19，21，32，28中選出兩個權小結點。選中19，21。同時計算出它們的和40。另起一顆二叉樹。（7）從32，28， 40中選出兩個權小結點。選中28，32。同時計算出它們的和60。（8）從 40， 60中選出兩個權小結點。選中40，60。同時計算出它們的和100。好了，此時哈夫曼樹已經構建好了。