最優(yōu)二叉樹哈夫曼樹-展示頁
2025-06-28 06:37本頁面
【正文】 (d) (e) 具有相同葉子結(jié)點和不同帶權(quán)路徑長度的二叉樹由此可見，由相同權(quán)值的一組葉子結(jié)點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠離根結(jié)點。例如，給出4個葉結(jié)點，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個二叉樹。它的帶權(quán)路徑長度值WPL＝22＋42＋52＋32＝28。設(shè)二叉樹具有n個帶權(quán)值的葉結(jié)點，那么從根結(jié)點到各個葉結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為： n∑k=1 WPL＝ Wk 那么什么是二叉樹的帶權(quán)路徑長度呢？ 在前面我們介紹過路徑和結(jié)點的路徑長度的概念，而二叉樹的路徑長度則是指由根結(jié)點到所有葉結(jié)點的路徑長度之和。為了找出比較次數(shù)最少的判斷框，將涉及到樹的路徑長度問題。我們可以把這個判斷過程表示為 ： 兩種判斷二叉樹示意圖那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢？讓我們對上述判斷框做一具體的分析。 鐵球分類現(xiàn)有一批球磨機上的鐵球，需要將它分成四類：直徑不大于20的屬于第一類。假設(shè)郵政局的包裹自動測試系統(tǒng)能夠測出包裹的重量，如何設(shè)計一棵二叉樹將包裹根據(jù)重量及運距進行分類從而確定郵資。最優(yōu)二叉樹——哈夫曼樹【重點與難點】1． 帶權(quán)二叉樹與哈夫曼樹基本概念；2． 構(gòu)造哈夫曼樹；3． 哈夫曼編碼及其算法實現(xiàn)?！疽搿吭趯嶋H應(yīng)用中，常常要考慮一個問題：如何設(shè)計一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。國內(nèi)快遞包裹資費 單位：元（2004年1月1日起執(zhí)行）運距（公里）首重1000克5000克以內(nèi)續(xù)重每500克5001克以上續(xù)重每500克=500=1000 500=1500 1000=2000 1500=2500 2000=3000 2500=4000 3000=5000 4000=6000 50006000 國家郵政局制定的快遞包裹參考標(biāo)準(zhǔn)，但不同的二叉樹判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。直徑大于20而不大于50的屬于第二類；直徑大于50而不大于100的屬于第三類；其余的屬于第四類；假定這批球中屬于第一、二、三、四類鐵球的個數(shù)之比例是1:2:3:4。假設(shè)有1000個鐵球，則各類鐵球的個數(shù)分別為：100、200、300、400；：左圖右圖序號比較式比較次數(shù)序號比較式比較次數(shù)1a=2010001a10010002a=509002a506003a=1007003a=20300合計2600合計1900 兩種判斷二叉樹比較次數(shù)過上述分析可知。 最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。如果二叉樹中的葉結(jié)點都具有一定的權(quán)值，則可將這一概念加以推廣。Lk 其中Wk為第k個葉結(jié)點的權(quán)值，Lk 為第k個葉結(jié)點的路徑長度。 在給定一組具有確定權(quán)值的葉結(jié)點，可以構(gòu)造出不同的帶權(quán)二叉樹。這些形狀不同的二叉樹的帶權(quán)路徑長度將各不相同。哈夫曼（Haffman）依據(jù)這一特點于1952年提出了一種方法，這種方法的基本思想是： （1）由給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個葉結(jié)點的二叉樹，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}； （2）在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和； （3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1