數(shù)據(jù)結(jié)構(gòu)—基礎(chǔ)知識(shí)：哈夫曼樹

哈夫曼樹的基本概念

哈夫曼（Huffman）樹又稱最優(yōu)樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹，在實(shí)際中有廣泛的用途。哈夫曼樹的定義，涉及路徑、路徑長(zhǎng)度、權(quán)等概念，下面先給出這些概念的定義，然后再介紹哈夫曼樹

1. 路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。
2. 路徑長(zhǎng)度：路徑上的分支數(shù)目稱作路徑長(zhǎng)度。
3. 樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。
4. 權(quán)：賦予某個(gè)實(shí)體的一個(gè)量，是對(duì)實(shí)體的某個(gè)或某些屬性的數(shù)值化描述。在數(shù)據(jù)結(jié)構(gòu)中，實(shí)體有結(jié)點(diǎn)（元素）和邊（關(guān)系）兩大類，所以對(duì)應(yīng)有結(jié)點(diǎn)權(quán)利邊權(quán)結(jié)點(diǎn)權(quán)或邊權(quán)具體代表什么意義，由具體情況決定。如果在一棵樹中的結(jié)點(diǎn)上帶有權(quán)值，則對(duì)應(yīng)的就有帶權(quán)樹等概念。
5. 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。
6. 樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記作WPL。
7. 哈夫曼樹：設(shè)有m個(gè)權(quán)值{w1，w2，…wm},可以構(gòu)造一棵含n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)的權(quán)為w，則其中帶權(quán)路徑長(zhǎng)度WPL最小的一叉樹稱做最優(yōu)二叉樹或哈夫曼樹。

例如，下圖中所示的3棵二叉樹，都含4個(gè)葉子結(jié)點(diǎn)a、b、c、d，分別帶權(quán)7、5、2、4，他們的帶權(quán)路徑長(zhǎng)度分別為

哈夫曼樹的構(gòu)造算法

哈夫曼樹的構(gòu)造過(guò)程

1. 根據(jù)給定的n個(gè)權(quán)值{w1，w?，…，wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，這n棵二叉樹構(gòu)成一個(gè)森林F。
2. 在森林F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。（選用兩小造新樹）
3. 在森林F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加人F中。（刪除兩小添新人）
4. 重復(fù)(2)和(3),直到F只含一棵樹為止。這棵樹便是哈夫曼樹。（重復(fù)(2)(3)剩單根）

在構(gòu)造哈夫曼樹時(shí)，首先選擇權(quán)小的，這樣保證權(quán)大的離根較近，這樣一來(lái)，在計(jì)算樹的帶權(quán)路徑長(zhǎng)度時(shí)，自然會(huì)得到最小帶權(quán)路徑長(zhǎng)度，這種生成算法是一種典型的貪心法。

注：哈夫曼樹的結(jié)點(diǎn)的度數(shù)為0或2，沒有度為1的結(jié)點(diǎn)。

哈夫曼算法的實(shí)現(xiàn)

//-------哈夫曼樹的存儲(chǔ)表示-------
typedef struct{
    int weight;//結(jié)點(diǎn)的權(quán)值
    int parent,lchild,rchild;//結(jié)點(diǎn)的雙親、左孩子、右孩子的下標(biāo)
}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹

包含n棵樹的森林經(jīng)過(guò)n-1次合并才能形成哈夫曼樹，共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)

算法：構(gòu)造哈夫曼樹

【算法步驟】

1. 初始化：首先動(dòng)態(tài)申請(qǐng)2n個(gè)單元;然后循環(huán) 2n-1次，從1號(hào)單元開始，依次將1至2n-1所有單元中的雙親、左孩子、右孩子的下標(biāo)都初始化為0；最后再循環(huán)n次，輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值。
2. 創(chuàng)建樹:循環(huán)n-1次，通過(guò)n-1次的選擇、刪除與合并來(lái)創(chuàng)建哈夫曼樹。選擇是從當(dāng)前森林中選擇雙親為0且權(quán)值最小的兩個(gè)樹根結(jié)點(diǎn)s1和 s2；刪除是指將結(jié)點(diǎn)s1 和s2白的雙親改為非 0；合并就是將s1 和 s2的權(quán)值和作為一個(gè)新結(jié)點(diǎn)的權(quán)值依次存入到數(shù)組的第n+1之后的單元中，同時(shí)記錄這個(gè)新結(jié)點(diǎn)左孩子的下標(biāo)為s1，右孩子的下標(biāo)為 s2。

void CreateHuffmanTree(HuffmanTree &HT,int n)
{
    if(n<=1) return;
    m=2*n-1;
    HT=new HTNode[m+1];//0號(hào)單元未用，所以需要?jiǎng)討B(tài)分配m+1個(gè)單元，HT[m]表示根結(jié)點(diǎn)
    for(i=1;i<=m,++1)//將1~m號(hào)單元中的雙親、左孩子，右孩子的下標(biāo)都初始化為0
    {
        HT[i].parnt=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for(i=1;i<=n,++1)//輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值
        cin>>HT[i].weight;
/*-----------初始化工作結(jié)束，下面開始創(chuàng)建哈夫曼樹-----------*/
    for(i=n+1;i<=n;++1)
    {//通過(guò)n-1次的選擇、刪除、合并來(lái)創(chuàng)建哈夫曼樹
        Select(HT,i-1,s1,s2);
        //在HT[k]（1≤k≤i-1）中選擇兩個(gè)其雙親域0且權(quán)值最小的結(jié)點(diǎn)，并返回它們?cè)贖T中的序號(hào)s1和s2（最小結(jié)點(diǎn)下標(biāo)）
        HT[s1].parent=i;HT[s2].parent=i;//修改HT[s1][s2]的parent值
        HT[i].lchild=s1;HT[i].rchild=s2;//s1,s2分別作為i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;//i的權(quán)值為左右孩子之和
    }
}

已知w=（5，29，7，8，14，23，3，11），構(gòu)造一棵哈夫曼樹，計(jì)算樹的帶權(quán)路徑長(zhǎng)度，并給出構(gòu)造過(guò)程中存儲(chǔ)結(jié)構(gòu)HT的初始狀態(tài)和終結(jié)狀態(tài)。

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-833809.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)—基礎(chǔ)知識(shí)：哈夫曼樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！