数据结构之哈夫曼树与哈夫曼编码

这篇具有很好参考价值的文章主要介绍了数据结构之哈夫曼树与哈夫曼编码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、背景

编码是信息处理的基础（重新表示信息）。

普通的编码是等长编码，例如7位的ASCIL编码，对出现频率不同的字符都使用相同的编码长度。但其在传输和存储等情况下编码效率不高。

可使用不等长编码，来压缩编码：高频字符编码长度更短，低频字符编码长度更长。

[例] 将百分制的考试成绩转换成五分制的成绩

按顺序分别编码。

按频率分别编码（高频短编码，类似于香农熵衡量随机变量的编码长度下界）。

这种贪心思想，可以找到一种平均最短编码长度-霍夫曼编码。可将构造平均最短编码转化为，构造平均查找长度最小的编码树（构造更有效的搜索树）

二、哈夫曼树

哈夫曼树的定义

带权路径长度就是所有叶子节点的编码长度乘以权重的和。希望权重越高的叶子节点，编码长度越小。

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

哈夫曼树的构造

初始全是只有一个节点的树构成的森林（优先队列存放树的根节点，每次合并后将新的树插入队列）

每次把权值最小的两棵二叉树合并（自底向上）

使用最小堆，Huffman树为二叉树

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int Weight;
    HuffmanTree Left, Right;
};

/* WPL WeightPathLength Cost越小编码越有效， O(NlogN) */ 
HuffmanTree Huffman( MinHeap H )
{ 
  /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    int i; 
    HuffmanTree T;
    BuildMinHeap(H); /* 将H->Elements[]按权值调整为最小堆 */
    /* 做 H->Size - 1 次合并 */
    for (i = 1; i < H->Size; i++) 
{ 
         T = malloc( sizeof( struct TreeNode) ); /* 建立新结点 */        
         T->Left = DeleteMin(H);  /* 从最小堆中删除一个结点，作为新T的左子结点 */
         
         T->Right = DeleteMin(H);
 /* 从最小堆中删除一个结点，作为新T的右子结点 */        
         T->Weight = T->Left->Weight + T->Right->Weight; /*计算新权值*/

         Insert( H, T ); /*将新T插入最小堆*/
     }
     T = DeleteMin(H);
     
    return T;


int WPL( HuffmanTree H )
{
    return H->Weight;
}

　　文章来源地址https://www.toymoban.com/news/detail-414602.html

哈夫曼树的特点