文章目錄
- 前言
- 一、涉及到的知識點
- 二、例題講解
- 1、例題1
- 2、例題2
- 總結
前言
在資料結構樹的這章中，常常有題目，是這樣的“給定一組權值…，試設計相應的哈夫曼樹”，有的還要求其帶權路徑長度，還有的是給定字符以及其使用頻率，要求設計一個哈夫曼編碼，同時要求設計哈夫曼樹等等，
為此這種題的步驟解法，我將做詳細的講解，本文介紹兩種題型，分別是求哈夫曼樹以及設計哈夫曼編碼，希望對閱讀本博客以及有需要的小伙伴有用，如有錯誤不當之處，歡迎大佬們指正！
（😊😊😊）
提示：以下是本篇文章正文內容，下面案例可供參考，
一、涉及到的知識點
哈夫曼樹：給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹，可以說，哈夫曼樹是一種特殊的二叉樹，這種樹的所有的葉子結點都有權值，從而構造出帶權路徑長度最短的二叉樹，其中權值較大的結點離根較近，
路徑長度：樹中路徑上的分支數目，
樹的路徑長度：根結點到樹中每個結點的路徑長度之和，
葉子結點的權值：權值是人們根據需要為每個葉子結點賦予的一個數值，
葉子結點的帶權路徑長度：樹根到一個葉子結點之間的路徑長度與該結點權值的乘積，
樹的帶權路徑長度：樹中所有葉子結點的權值乘以該結點的路徑長度之和，公式如下：
其中，Wk為第k個葉子結點的權值，Lk是從根結點到第k個葉子結點的路徑長度，
哈夫曼編碼：樹中從根到每個葉子都有一條路徑， 對路徑上的各分枝約定指向左子樹根的分枝表示“ 0 ” 碼， 指向右子樹的分枝表示“ 1 ” 碼， 取每條路徑上的“ 0 ” 或“ 1 ” 的序列作為和各個葉子對應的字符的編碼， 這就是哈夫曼編碼，
好接下來，我們了解了基本知識后，來看看這兩道題簡單的鞏固一下
e.g.
1、求下圖中二叉樹的帶權路徑長度
解：結果如下：
WPL=2×2+3×2+4×2+6×2=30
2、寫出下圖哈夫曼樹中D和F的哈夫曼編碼（提示：哈夫曼樹的每個左分支設為0，右分支設為1）
解：D和F的哈夫曼編碼為
D:00
F:10
接下來，我們一起進入正題部分，兩道例題了解一下😎
二、例題講解
1、例題1
給定權值{5,10,12,15,30,40}，構造相應的哈夫曼樹（要求寫出構造步驟），并求出該樹的帶權路徑長度，（提示：哈夫曼樹的每個左分支設為0，右分支設為1，要求同層中葉子結點權值從左到右，從小到大），
解：注：只要將最小的兩個權值合并, 合并后的值再入列中(最小的兩個出列), 直至列中只有一個值結束，
按權值大小排列后得： {5,10,12,15,30,40}，
取5和10，得到5+10=15，
從{12，15，15，30，40}找兩個最小的12+15=27
{15，27，30，40}中取15+27=42
{30，40，42}中取30+40=70
{42，70}中取42+70=112
{112}停止，
因為要求同層中葉子結點權值從左到右，從小到大，即分別建立左右分支，不懂的小伙伴可以仔細看一下上述程序以及畫的圖，另題目要求在哈夫曼樹的每個左分支設為0，右分支設為1，
則哈夫曼樹如下:
帶權路徑長度：
（5+10+12+15）×3+（15+30+40）×2=166
提示：哈夫曼樹中黃熒游標標記處，畫圖中不用標出，為讀者方便理解特注，即算這些所標記的葉子，
具體步驟圖例：
2、例題2
已知一個電文字符集中有8個字符{A,B,C,D,E,F,G,H}，它們使用的頻率為{0.04，0.21，0.06，0.07，0.15，0.18，0.12，0.03}，設計一個哈夫曼編碼，（提示：哈夫曼樹的每個分支左分支設為0，右分支設為1，要求同層中葉子結點權值從左到右，從小到大），
解：將使用的頻率乘以100，得到它們的權值
乘以100，得：{4，21，6，7，15，18，12，3}，
按大小排序后，{3，4，6，7，12，15，18，21}
取3和4，得3+4=7，
從{6，7，7，12，15，18，21}中取6+7=13
{7，12，13，15，18，21}中取7+12=19
{13，15，18，19，21}中取13+15=28
{18，19，21，28}中取18+19=37
{21，28，37}中取21+28=49
{37，49}中取37+49=86
{86}停止
則哈夫曼樹如下:
由哈夫曼樹得到哈夫曼編碼為(由上至下編碼)：
A：0101
B: 10
C: 1100
D: 1101
E:111
F: 00
G:011
H:0100
總結
以上就是全部內容，本文簡單介紹了哈夫曼樹的一些基本知識和如何求哈夫曼樹以及如何設計哈夫曼編碼的方法，希望能給讀者帶來幫助，碼字不易，希望小伙伴們給個一鍵三連👍👍👍，這是給本博主的最大動力哦，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/230671.html
標籤：AI
下一篇：C語言編程＞第二周 ③ 古典問題：有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？