了解赫夫曼树一文就够了-白红宇的个人博客

了解赫夫曼树一文就够了

发布日期：2021-06-29 14:17:49 浏览次数：3 分类：技术文章

本文共 4543 字，大约阅读时间需要 15 分钟。

前言

这是我听老师讲课做的笔记。
作者：RodmaChen
关注我的csdn博客，更多数据结构与算法知识还在更新

赫夫曼树及其应用（必考）

一. 定义

路径：从树中一个结点到另一个结点之间的分支构成两个结点之间
的路径。

路径长度：路径的上分支的数目。就是从一个结点到另一个结点有多少个路径

结点的路径长度：从根到该结点的路径长度。

树的路径长度：从树根到每一个结点的路径长度之和。

结点的权：在一些应用中，赋予树中结点的一个有某种意义实数

结点的带权路径长度：从根结点到各个叶结点的路径长度与相应结点权值的乘积。

树的带权路径长度：所有叶结点的带权路径长度之和，记作：
$\sum_{k=1}^n W_kl_k} （其中，n：叶结点数目；W_k：叶结点 k的权值；l_k根到k之间的路径长度）$

最优二叉树/ 赫夫曼树：假设有n个权值(w1,w2…wn)，试
构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi ，
则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫
夫曼树。

二. 赫夫曼算法

1.基本思想

给定n个权值，先找出两个最小的权值wi,wj,求wi+wj=wk,把wk与其它权值继续重复此动作，直至所有的wi都成为叶子结点。

如下图所示：给定7,5,3,1。选取根结点的权值最小（1）和次小（3）的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和（4）。最后7，5,3,1变成叶子结点。这样一颗树就是赫夫曼树。

在这里插入图片描述

2.算法的实现

（1）赫夫曼树的存储结构：

赫夫曼树是一种二叉树，由于赫夫曼树中没有度为 1 的结点，因此一棵有 n 个叶子的赫夫曼树共有 2n-1 个结点，可以用一个大小为 2n-1 的一维数组存放赫夫曼树的各个结点。

为什么是2n-1： [根据二叉树的性质三](file:///D:/课本笔记/我的笔记/计算机数据结构与算法笔记/第六章：树和二叉树的性质和定义.html)由于没有度为1的结点，所以度为2的结点N=n-1，总结点等于2n-1

由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成

一个静态三叉链表。

权值双亲左孩子右孩子

（2）赫夫曼树的类型定义：

用静态三叉链表实现的哈夫曼树类型定义如下：

#define N 20 /* 叶子结点的个数。*/#define M 2*N-1 /* 所有结点的个数。*/typedef struct{
   	int weight ; /* 结点的权值*/	int parent ; /* 双亲的下标*/	int LChild ; /* 左孩子结点的下标*/	int RChild ; /* 右孩子结点的下标*/} HTNode, HuffmanTree[M+1];/* HuffmanTree 是一个结构数组类型，0 号单元不用。 */void CrtHuffmanTree(HuffmanTree ht, int w[ ], int n){
       /*构造哈夫曼树 ht[M+1]， w[ ]存放 n 个权值。*/      /* 1 ~ n 号单元存放叶子结点，初始化*/     for(i=1;i<=n;i++) ht[i] ={
    w[i],0,0,0};     m=2*n-1;     for(i=n+1;i<=m;i++) ht[i] ={
   0,0,0,0};    /* n+1 ~ m 号单元存放非叶结点，初始化 */   ——————————初始化完毕！对应算法步骤 1，下面左边的表——————    for(i=n+1; i<=m; i++) /*创建非叶结点，建哈夫曼树*/   {
           select(ht, i-1, s1, s2);       /* 在 ht[1] ~ ht[i-1] 的范围内选择两       个 parent 为 0 且 weight 最小的结点，其序号分别赋值给 s1、s2 返回 */       ht [i].weight= ht [s1].weight+ ht [s2].weight;       ht [s1].parent=i; ht [s2].parent=i;       ht [i].LChild=s1; ht [i].RChild=s2;    } /*哈夫曼树建立完毕*/}

（3）代码事列：

数据传送中的二进制编码。要传送数据 state, seat,act, tea, cat, set, a,eat，如何使传送的长度最短？为了保证长度最短，先计算各个字符出现次数，将出现次数当作权值，如下表所示。

按照创建哈夫曼树算法，该例建立哈夫曼树的结果如下表所示：

三.赫夫曼编码

1.编码和解码（考例题）

（1）数据压缩过程称为编码。即将文件中的每个字符均转

换为一个惟一的二进制位串。

（2）数据解压过程称为解码。即将二进制位串转换为对应

的字符。

等长编码：每个字符的码长一样。

变长编码：频度高的（出现多的）字符编码短，反之则长。

举例：假设需传送的电文为’ABACCDA'，分别按定长和不定长编码，如

下表所示

如上表所示：A、B、C、D的定长编码分别为00、01、10和11，则上

述7个字符的电文便为’00010010101100’ ，总长14位，对方接收时，可

按二位一分进行译码。

如果设计A、B、C、D的编码分别为0、00、1和01，则上述7个字符的

电文可转换成总长为9的字符串’000011010'。但是，这样的电文无法翻

译，例如传送过去的字符串中前4个字符的子串’0000’就可有多种译法，

或是’AAAA'，或是’ABA’，也可以是’BB’等。

前面两种编码一个太长，一个容易出错

前缀编码：若要设计长短不等的编码，则必须是任一个字符的编码
都不是另一个字符的编码的前缀

举例：可以利用二叉树来设计二进制的前缀编码。左走0右走1

二进制前缀编码便称为赫夫曼编码。

2.编码实现

由于赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫夫曼树
共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需知孩子结点的信息。

由此，设定下述存储结构:

//一一一一赫夫曼树和赫夫曼编码的存储表示----------typedef struct{
   unsigned int weight;unsigned int parent, lchild, rchild;}EINode, * HuffmanTree: //动态分配数组存储赫夫曼树typedef char * *HuffmanCode; //动态分配数组存储赫夫曼编码表void HaffmanCoding(HuffmanTree &HT, HuffmanCode &HC，int *w，int n) {
   //  w存放n个字符的权值(均>0)，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC /---构造赫夫曼树HT---   if (n<= 1) return;//如果只有一个结点，就没必要构造了m = 2 * n - 1; //结点总数HT = (HuffmanTree)malloc((m+ 1) * sizeof(HTNode)); //0号单元未用for (p=HT, i=1; i<=n; ++i, ++p, ++w) *p = {
   *w,0, 0,0 );for(; i≤=m; ++i，++p) *p ={
   0,0,0.0};for (i=n+ 1; i<=m; ++i) {
    //建赫夫曼树//在HT[1..i-1]选择parent 为0且weight 最小的两个结点,其序号分别为s1s2.Select(HT, i- 1, sl, s2);HT[sl]. parent = i; HT[s2]. parent = i;HT[i]. Ichild = s1; HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}/---从叶子到根逆向求每个字符的赫夫曼编码---HC= (HuffmanCode)malloc ((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量cd = (char * )malloc(n* sizeof(char)); //分配求编码的工作空间cd[n-1] = "\0"; //编码结束符。for(i=1; i<=n; ++i) {
    //逐个字符求赫夫曼编码start = n-1; //编码结束符位置for (c=i, f= HT[i]. parent; f!=0; :c= f, f=HT[f].parent) //从叶子到根逆向求编码if (HT[f].lchild==c) cd[--start] = "0”;else cd[--start] ="1";HC[i] = (char *)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间strcpy(HC[i], &cd[start]); //从cd复制编码(串)到HC}free(ed); //释放工作空间}//HuffanCoding