資料結構 哈夫曼樹

2022-09-23 00:28:33 字數 1321 閱讀 8493

基本概念

路徑:在一棵樹中,從任意一個結點到達另一個結點的通路

路徑長度:該路徑所需經過的邊的個數

帶權路徑長度:從根結點到達該節點的路徑長度再乘以該結點權值的結果

帶權路徑長度和:樹所有的葉子結點的帶權路徑長度和

哈夫曼樹:給定n個帶權值結點,以它們為葉子結點構造的一棵帶權路徑和最小的二叉樹

哈夫曼樹的求法

將所有結點放入集合 k。

若集合 k 中剩餘結點大於 2 個,則取出其中權值最小的兩個結點,構造他們同時為某個新節點的左右兒子,該新節點是他們共同的雙親結點,設定它的權值為其兩個兒子結點的權值和。並將該父親結點放入集合 k。重複步驟 2 或 3。

若集合 k 中僅剩餘一個結點,該結點即為構造出的哈夫曼樹數的根結點,所有構造得到的中間結點(即哈夫曼樹上非葉子結點)的權值和即為該哈夫曼樹的帶權路徑和

題目描述:哈夫曼樹,第一行輸入一個數n,表示葉結點的個數。需要用這些葉結點生成哈夫曼樹,根據哈夫曼樹的概念,這些結點有權值,即weight,題目需要輸出所有結點的值與權值的乘積之和。

輸入:輸入有多組資料。每組第一行輸入一個數n,接著輸入n個葉節點(葉節點權值不超過100,2<=n<=1000)。

輸出:輸出權值。

樣例輸入:

5 1 2 2 5 9

樣例輸出:

37

為了方便快捷高效率的求得集合k中權值最小的兩個元素,我們需要使用堆資料結構。它可以以o(logn)的複雜度取得n個元素中的最小元素。為了繞過對堆的實現,我們使用標準模板庫中的相應的標準模板--優先佇列。

建立一個儲存元素為int的堆q,預設為大頂堆,即取得整個堆中的最大元素:

priority_queueq;

如果需要取得堆中的最小元素,則可以使用如下語句定義小頂堆:

priority_queue,greater>q;

優先佇列與佇列一樣在標準模板庫queue中。

#include#include

using

namespace

std;

priority_queue

,greater >q;//

建立一個小頂堆

intmain()

int ans=0

;

while(q.size()>1)

printf(

"%d\n

",ans);

}return0;

}

哈夫曼樹和哈夫曼編碼

當樹中的節點被賦予一個表示某種意義的數值,我們稱之為該節點的權。從樹的根節點到任意節點的路徑長度 經過的邊數 與該節點上權值的乘積稱為該節點...

哈夫曼編碼

哈夫曼編碼 編碼 普通的編碼都是定長的,比如常用的ascii編碼 每個字元都是8個bit 變長編碼 變長編碼比固定編碼好一些,即對頻率高的字...

哈夫曼編碼

霍夫曼編碼 huffman coding 是一種編碼方法,霍夫曼編碼是可變字長編碼 vlc 的一種。 霍夫曼編碼使用變長編碼表對源符號 如檔案中的一個字母 進行編碼,其中變長編碼表是通過一種評估 符號出現機率的方法得到的,出現機率高的字母使用較短的編碼,反之出現機率低的則使用較長的編碼,這便使編碼之...