数组实现哈夫曼树及哈夫曼编码

基本介绍:http://baike.baidu.com/link?url=DDUm7qBwh4XVGlhskrXjpQZx6mu74iy-54mkIBMUIME8o22OKvbi61yHxOz0Ljm5YekqESS70n3rTKSHqPu3Z_

简单的图示介绍:
哈夫曼树及哈夫曼编码

用数组实现的哈夫曼树及哈夫曼编码:

#include <cstdio>
#define N 5
#define M 2*N-1
#define MaxInt 666666
//建成的哈夫曼树存放在HTree数组中
//且通过数组元素下标来确定父节点,左节点,右节点
struct 
{
    int weight;//权
    int left;//左节点
    int right;//右节点
    int parent;//父节点
}HTree[M];


//对一篇文章编码,我们假设已经得到了每个字符(c)及它们的出现权重(weight)
struct 
{
    char c;
    int weight;
    int bit[100];//存储每个字符编码的逆序
    int code[100];//存储每个字符的编码
    int len;//存储每个字符的编码的长度
}cc[N]={{'a',1,{0},{0},0},{'b',2,{0},{0},0},{'c',3,{0},{0},0},{'d',4,{0},{0},0},{'e',5,{0},{0},0}};


//初始化成森林
void InitHTree()
{
    int i;
    for(i=0;i<M;i++)
    {
        if(i<N)
        HTree[i].weight=cc[i].weight;
        else
        HTree[i].weight=0;
        HTree[i].left=HTree[i].right=HTree[i].parent=-1;//数组元素以0为第一元素,故将其初始化为-1
    }
}


//建哈夫曼树
void BuidHTree()
{
    int i,j,x,y;
    int min;
    for(i=0;i<N-1;i++)
    {
        min=MaxInt;
        //找最小的两个元素x,y
        for(j=0;j<M;j++)
        {
            if(HTree[j].parent==-1&&HTree[j].weight>0&&min>HTree[j].weight)
            {
                min=HTree[j].weight;
                x=j;
            }
        }
        min=MaxInt;
        for(j=0;j<M;j++)
        {
            if(HTree[j].parent==-1&&HTree[j].weight>0&&j!=x&&min>HTree[j].weight)
            {
                min=HTree[j].weight;
                y=j;
            }
        }
        HTree[x].parent=HTree[y].parent=i+N;//父节点为HTree[i+N]
        HTree[i+N].left=x;
        HTree[i+N].right=y;
        HTree[i+N].weight=HTree[x].weight+HTree[y].weight;
    }
}

//哈夫曼编码:每一个字符都得到一个二进制编码
void HuffCode()
{
    int i,j;
    int pos,child,parent;
    for(i=0;i<N;i++)
    {
        pos=0;
        child=i;
        parent=HTree[i].parent;
        while(parent!=-1)
        {
            if(HTree[parent].left==child)
            cc[i].bit[pos]=0;
            else
            cc[i].bit[pos]=1;
            pos++;
            child=parent;
            parent=HTree[parent].parent;
        }
        cc[i].len=pos;

        //将逆序的结果存到正序中
        pos--;
        for(j=0;j<cc[i].len;j++,pos--)
        cc[i].code[j]=cc[i].bit[pos];
    }
}

int main()
{
    int i,j;
    //初始化森林
    InitHTree();
    //建哈夫曼树
    BuidHTree();
    //测试建树结果
    for(i=0;i<M;i++)
    printf("%d ",HTree[i].weight);
    printf("\n");
    //哈夫曼编码
    HuffCode();
    //测试编码结果:每一个字符都得到一个特定的二进制编码
    for(i=0;i<N;i++)
    {
        printf("%c:",cc[i].c);
        for(j=0;j<cc[i].len;j++)
        printf("%d ",cc[i].code[j]);
        printf("\n");
    }
    return 0;
}

原文地址:http://www.hewie.cn/blog/Home/Article/article/article_id/3.html