快捷導(dǎo)航

解讀赫夫曼樹(shù)編碼的問(wèn)題

更新時(shí)間：2013年05月07日 11:29:20 作者：

本篇文章對(duì)赫夫曼樹(shù)編碼的問(wèn)題進(jìn)行了分析說(shuō)明，需要的朋友參考下

定義:

　　結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。假設(shè)有n個(gè)權(quán)值，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi，則其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱(chēng)做最優(yōu)二叉樹(shù)或赫夫曼樹(shù)。

構(gòu)造赫夫曼樹(shù)的方法：

（1）根據(jù)給定的n個(gè)權(quán)值{w1,w2,w3......}構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,T3,T4......}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。

（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。

（3）在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。

（4）重復(fù)（2）和（3），直到F只含一棵樹(shù)為止。這棵樹(shù)便是赫夫曼樹(shù)。

代碼實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

#include<iostream>
#include<assert.h>
using namespace std;

struct HuffmanNode
{
    unsigned int weight;
    unsigned int parent,leftChild,rightChild;
    HuffmanNode()
    {
        weight=0;parent=0;leftChild=0;rightChild=0;
    }
};

void Select(const HuffmanNode* & nodelist,const int length,int & a, int &b)
{
    int min=1000000,min2=1000000;
    for(int i=0;i<length;i++)
    {
        if(min>nodelist[i].weight&&nodelist[i].parent==0)
        {
            min=nodelist[i].weight;
            a=i;
        }
    }
    for(int j=0;j<length;j++)
    {
        if(j!=a&&min2>nodelist[j].weight&&nodelist[j].parent==0)
        {
            min2=nodelist[j].weight;
            b=j;
        }
    }
}

char ** HuffmanCoding(const int *w, const int n)
{
    assert(w!=NULL);
    int i,min1,min2;
    int m = 2*n-1;
    HuffmanNode * nodelist = new HuffmanNode[m]();
    for(i=0;i<n;i++)
    {
        nodelist[i].weight=w[i];
        nodelist[i].parent=0;
    }
    for(i=n;i<m;i++)
    {
        Select(nodelist,i,min1,min2);
        nodelist[min1].parent=i;
        nodelist[min2].parent=i;
        nodelist[i].weight=nodelist[min1].weight+nodelist[min2].weight;
        nodelist[i].rightChild=min2;
        nodelist[i].leftChild=min1;
        nodelist[i].parent=0;
    }
    char temp [20];
    char ** code = new char * [n];
    for(i=0;i<n;i++)
    {
        int j=i;
        int index=0;
        while(j!=m-1)
        {
            if(j==nodelist[nodelist[j].parent].leftChild) temp[index++]='0';
            else temp[index++]='1';
            j=nodelist[j].parent;
        }
        temp[index]='\0';
        code[i] = new char[index+1];
        strcpy(code[i],temp);
    }
    delete nodelist;
    return code;
}

int main()
{
    const int size=6;
    char word[size]={'A','B','C','D','E','F'};//編碼字符
    int w[size]={4,3,2,1,7,8};//權(quán)重
    char ** code;
    code=HuffmanCoding(w,size);
    assert(code!=NULL);
    for(int i=0;i<size;i++)
    {
        cout<<word[i]<<" is coded as "<<code[i]<<endl;
    }
    //注意二級(jí)指針的釋放問(wèn)題
    for(int j=0;j<size;j++)
    {
        delete []code[j];
    }
    delete []code;
    return 0;
}