数据结构学习记录——哈夫曼树（什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码）-阿里云开发者社区

数据结构学习记录——哈夫曼树（什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码）

2024-06-06 16

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构学习记录——哈夫曼树（什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码）

什么是哈夫曼树

我们先举个例子：

要将百分制的考试成绩转化成五分制的成绩

if(score < 60)
    grade = 1;
else if(score < 70)
    grade = 2;
else if(score < 80)
    grade = 3;
else if(score < 90)
    grade = 4;
else
    grade = 5;

这种情况其实是一棵判定树：

这种方式要看各成绩段的学生分布，如果60以下的同学比较多，那么判断的次数就会很少；但是如果90多的同学比较多的情况下，那么要判断4次的情况就会很多，整体的判断效率不高。

我们考虑学生成绩分布的概率：

分数段	0-59	60-69	70-79	80-89	90-100
比例	0.05	0.15	0.40	0.30	0.10

那么判断效率就为：

现在我们想要让判断的效率更高一点，修改一下判定树：

写成代码就为：

if(score < 80)
{
    if(score < 70)
    {
        if(score < 60)
        {
            grade = 1;
        }
        else
        {
            grade = 2;
        }
    }
    else
    {
        grade = 3;
    }
}
else if(score < 90)
{
    grade = 4;
}
else
{   
    grade = 5;
}

如何根据结点不同的查找频率构造更有效的搜索树？

就涉及到了我们要讲的哈夫曼树

哈夫曼树的定义

带权路径长度（WPL）：设二叉树有n个叶子结点，每个叶子结点带有权值，从根结点到每个叶子结点的长度为，则每个叶子结点的带权路径长度之和就为：

最优二叉树或哈夫曼树：WPL最小的二叉树。

例：有五个叶子结点，它们的权值为{1,2,3,4,5}，用此权值序列可以构造出形状不同的多个二叉树。

哈夫曼树的构造

给出一个权值序列，构造出一棵哈夫曼树。

例：{1,2,3,4,5}

每次把权值最小的两棵二叉树合并，具体：

图解操作

哈夫曼树的构造是比较简单的，要找出两个最小值，就可以运用我们前面学过的最小堆来找了，这比从小到大排好序的效率会更高。下面我们来看一下代码的实现。

代码实现

typedef struct TreeNode *HuffmanTree;
struct TreeNode
{
    int Weight;
    HuffmanTree Left,Right;
}
 
HuffmanTree Huffman(MinHeap H)
{    /*假设H->Size个权值已经存在H->Elements[]->Weight里*/
    int i;
    HuffmanTree T;
    BuildMinHeap(H);/*将H->Elements[]按权值调整为最小堆*/
    for (i=1;i<H->Size;i++)
    {
        /*做H->Size-1次合并*/
        T=malloc( sizeof( struct TreeNode));/*建立新结点*/ 
        T->Left=DeleteMin(H);
        /*从最小堆中删除一个结点，作为新T的左子结点*/
        T->Riqht=DeleteMin(H);
        /*从最小堆中删除一个结点，作为新T的右子结点*/
        T->Weight=T->Left->Weiqht + T->Right->Weight;
            /*计算新权值*/
        Insert(H，T);/*将新T插入最小堆*/
    }
    T=DeleteMin(H);
    return T;  
}