构造哈夫曼树和生成哈夫曼编码

发布时间:2024-02-22 08:00

一、什么是哈夫曼树?

哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明:

\"\"

它们的带权路径长度分别为:

图a: WPL=5*2+7*2+2*2+13*2=54

图b: WPL=5*3+2*3+7*2+13*1=48

可见,图b的带权路径长度较小,可以证明图b就是哈夫曼树(也称为最优二叉树)。

二、如何构建哈夫曼树

一般按下面步骤构建:

1,将所有左,右子树都为空的作为根节点。

2,在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。

3,从森林中删除这两棵树,同时把新树加入到森林中。

4,重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程:

\"\"

三、哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径,对路径上的各分支约定指向左子树的分支表示\"0\"码,指向右子树的分支表示\"1\"码,取每条路径上的\"0\"或\"1\"的序列作为各个叶子节点对应的字符编码,即是哈夫曼编码。

上图例子来说:

A,B,C,D对应的哈夫曼编码分别为:111,10,110,0

用图说明如下:

\"构造哈夫曼树和生成哈夫曼编码_第1张图片\"

记住,设计电文总长最短的二进制前缀编码,就是以n个字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。

四、算法实现

/**
*    实验题目:
*        构造哈夫曼树和生成哈夫曼编码
*    实验目的:
*        领会哈夫曼的构造过程以及哈夫曼编码的生成过程
*    实验内容:
*        设计程序,构造一颗哈夫曼树,输出对应的哈夫曼
*    编码和平均查找长度。并用如下数据进行验证:
*    单词以及出现的频度
*    The  of  a   to  and  in  that  he  is  at  on   for  His  are  be
*    1192 677 541 518 462  450 242   195 190 181 174  157  138  124  123
*    备注:二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)
*/

#include
#include

#define N   (50)        // 树中叶子结点数最大值
#define M   (2 * N - 1) // 树中结点总数最大值

typedef struct
{
    char data[5]; // 结点值
    int weight; // 权重
    int parent; // 双亲结点
    int lchild; // 左孩子结点
    int rchild; // 右孩子结点
}HTNode; // 声明哈夫曼树结点类型

typedef struct
{
    char cd[N]; // 存放哈夫曼编码
    int start;
}HCode; // 声明哈夫曼编码类型

/*-------------由含有n个叶子结点的ht构造完整的哈夫曼树-----------------*/
static void create_huffman_tree(HTNode ht[], int n)
{
    int i;
    int k;
    int lnode;
    int rnode;
    int min1;
    int min2;

    // 所有结点的相关域设置初值为-1
    for(i = 0; i < 2 * n - 1; i++)
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    for(i = n; i < 2 * n - 1; i++) // 构造哈夫曼树的分支结点
    {
        min1 = min2 = 32767;
        lnode = rnode = -1;
        for(k = 0; k <= i - 1; k++) // 查找最小和次小的结点
        {
            if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找
            {
                if(ht[k].weight < min1)
                {
                    min2 = min1;
                    rnode = lnode;
                    min1 = ht[k].weight;
                    lnode = k;
                }
                else if(ht[k].weight < min2)
                {
                    min2 = ht[k].weight;
                    rnode = k;
                }
            }
        }
        ht[lnode].parent = i; // 合并两个最小和次小的结点
        ht[rnode].parent = i;
        ht[i].weight = ht[lnode].weight + ht[rnode].weight; // 计算双亲结点的权重
        ht[i].lchild = lnode; // 设置双亲结点的左孩子
        ht[i].rchild = rnode; // 设置双亲结点的右孩子
    }
}

/*-------------由哈夫曼树ht构造哈夫曼编码hcd-----------------*/
static void create_huffman_code(HTNode ht[], HCode hcd[], int n)
{
    int i;
    int f;
    int c;
    HCode hc;

    for(i = 0; i < n; i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
    {
        hc.start = n;
        c = i;
        f = ht[i].parent;
        while(f != -1) // 循环直到树根结点
        {
            if(ht[f].lchild == c) // 处理左孩子结点
                hc.cd[hc.start--] = \'0\';
            else // 处理右孩子结点
                hc.cd[hc.start--] = \'1\';
            c = f;
            f = ht[f].parent;
        }
        hc.start++; // start指向哈夫曼编码最开始字符
        hcd[i] = hc;
    }
}

/*-------------输出哈夫曼编码-----------------*/
static void display_huffman_code(HTNode ht[], HCode hcd[], int n)
{
    int i;
    int k;
    int sum = 0;
    int m = 0;
    int j;

    printf(\"输出哈夫曼编码:\\n\");
    for(i = 0; i < n; i++)
    {
        j = 0;
        printf(\"      %s:\\t\", ht[i].data);
        for(k = hcd[i].start; k <= n; k++)
        {
            printf(\"%c\", hcd[i].cd[k]);
            j++;
        }
        m += ht[i].weight;
        sum += ht[i].weight * j;
        printf(\"\\n\");
    }

    printf(\"\\n平均长度 = %g\\n\", 1.0 * sum / m);
}

int main(void)
{
    int n = 15;
    int i;
    HTNode ht[M];
    HCode hcd[N];
    char *str[] = {\"The\", \"of\", \"a\", \"to\", \"and\", \"in\", \"that\", \"he\", \"is\", \"at\", \"on\", \"for\", \"His\", \"are\", \"be\"};
    int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};

    for(i = 0; i < n; i++)
    {
        strcpy(ht[i].data, str[i]);
        ht[i].weight = fnum[i];
    }
    create_huffman_tree(ht, n); // 创建哈夫曼树
    create_huffman_code(ht, hcd, n); // 构造哈夫曼编码
    display_huffman_code(ht, hcd, n); // 输出哈夫曼编码

    return 0;
}
测试结果:

输出哈夫曼编码:
     The:      01
     of:       101
     a:        001
     to:       000
     and:      1110
     in:       1101
     that:     11110
     he:       11001
     is:       11000
     at:       10011
     on:       10010
     for:      10001
     His:      10000
     are:      111111
     be:       111110

平均长度 = 3.56208

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号