【数据结构】11.哈夫曼树哈夫曼编码

news/2024/11/18 2:08:48/

一、哈夫曼树的基本概念

哈夫曼(Huffman)树又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。

  • 路径: 从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径。
  • 路径长度: 路径上的分支数目称作路径长度。
  • 树的路径长度: 从树根到每一叶子节点的路径长度之和。
  • 权: 赋予某个实体的一个量,是对实体的某个或某些属性的数值化描述。在数据结构中,实体有节点(元素)和边(关系)两大类,所以对应有节点权和边权。节点权或边权具体代表什么意义,由具体情况决定。如果在一棵树中的节点上带有权值,则对应的就有带权树等概念。
  • 节点的带权路径长度: 从该节点到树根之间的路径长度与节点上权值的乘积。
  • 树的带权路径长度: 树中所有叶子节点的带权路径长度之和。
  • 哈夫曼树: 假设有m个权值{w1, w2,…, wm},可以构造一棵含n个叶子节点的二叉树,每个叶子节点的权值为wi,则其中带权路径长度最小的二叉树称作最优二叉树或哈夫曼树

在这里插入图片描述

二、哈夫曼树的构造

2.1 哈夫曼树的构造过程

  1. 根据给定的n个权值{w1, w2,…, wn},构造n棵只有根节点的二叉树,这n棵二叉树构成森林F。
  2. 在森林F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。
  3. 在森林F中删除这两棵树,同时将新得到的二叉树加入F中。
  4. 重复 2 和 3 ,直到F只含一棵树为止。这棵树便是哈夫曼树。

哈夫曼树的构造就是典型的贪心算法,每次都选择权值小的使得权值大的离根节点更近。这样计算得到的带权路径长度时自然而然的就会得到最小带权路径长度。

2.2 构造哈夫曼树的算法实现

哈夫曼树是一种二叉树,由于哈夫曼树中没有度为1的节点,则一棵有n个叶子节点的哈夫曼树共有2n−1个节点,可以存储在一个大小为2n−1的一维数组中。树中每个节点还要包含其双亲信息和孩子节点的信息,由此,每个节点的存储结构设计如下:

typedef int DataType; //结点权值的数据类型typedef struct HTNode //单个结点的信息
{DataType weight; //权值int parent; //父节点int lc, rc; //左右孩子
}*HuffmanTree;

哈夫曼树的各节点存储在由HuffmanTree定义的动态分配的数组中,为了实现方便,数组的0号单元不使用,从1号单元开始使用,所以数组的大小为2n。将叶子节点集中存储在前面部分的n个位置,而后面的n−1个位置存储其余非叶子节点。

接下来我们就要对HuffmanTree进行初始化并创建:

//在下标为1到i-1的范围找到权值最小的两个值的下标,其中s1的权值小于s2的权值
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{int min;//找第一个最小值for (int i = 1; i <= n; i++){if (HT[i].parent == 0){//先确定一个默认值min = i;break;}}for (int i = min + 1; i <= n; i++){if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)min = i;}//第一个最小值给s1s1 = min; //找第二个最小值for (int i = 1; i <= n; i++){if (HT[i].parent == 0 && i != s1){min = i;break;}}for (int i = min + 1; i <= n; i++){if (HT[i].parent == 0 && HT[i].weight < HT[min].weight && i != s1)min = i;}//第二个最小值给s2s2 = min; 
}//构建哈夫曼树
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{int m = 2 * n - 1; //哈夫曼树总结点数HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode,因为下标为0的HTNode不存储数据for (int i = 1; i <= n; i++)HT[i].weight = w[i - 1]; //赋权值给n个叶子结点for (int i = n + 1; i <= m; i++) //构建哈夫曼树{//选择权值最小的s1和s2,生成它们的父结点int s1, s2;Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标,其中s1的权值小于s2的权值HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和HT[s1].parent = i; //s1的父亲是iHT[s2].parent = i; //s2的父亲是iHT[i].lc = s1; //左孩子是s1HT[i].rc = s2; //右孩子是s2}
}

三、哈夫曼树编码

3.1哈夫曼树编码的认识

对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,对每个右分支赋予1,则从根到每个叶子的路径上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。

哈夫曼编码具有这样的性质:

  1. 哈夫曼编码是前缀编码
  2. 哈夫曼编码是最优前缀编码

3.2 哈夫曼树编码的实现

在构造哈夫曼树之后,求哈夫曼编码的主要思想是:依次以叶子为出发点,向上回溯至根节点为止。回溯时走左分支则生成代码0,走右分支则生成代码1。
由于每个哈夫曼编码是变长编码,因此使用一个指针数组来存放每个字符编码串的首地址。

//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1)); //开n+1个空间,因为下标为0的空间不用char* code = (char*)malloc(sizeof(char) * n); //辅助空间,编码最长为n(最长时,前n-1个用于存储数据,最后1个用于存放'\0')code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'for (int i = 1; i <= n; i++){int start = n - 1; //每次生成数据的哈夫曼编码之前,先将start指针指向'\0'int c = i; //正在进行的第i个数据的编码int p = HT[c].parent; //找到该数据的父结点while (p) //直到父结点为0,即父结点为根结点时,停止{if (HT[p].lc == c) //如果该结点是其父结点的左孩子,则编码为0,否则为1code[--start] = '0';elsecode[--start] = '1';c = p; //继续往上进行编码p = HT[c].parent; //c的父结点}HC[i] = (char*)malloc(sizeof(char) * (n - start)); //开辟用于存储编码的内存空间strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置}free(code); //释放辅助空间
}

http://www.ppmy.cn/news/1547862.html

相关文章

【泛型 Plus】Kotlin 的加强版类型推断:@BuilderInference

视频先行 下面是视频内容的脚本文案原稿分享。 小剧场 面试官&#xff1a;「既然协程和泛型你都熟悉&#xff0c;flow() 函数是怎么实现类型推断的有了解过吗&#xff1f;」 求职者&#xff1a;「嗯……」 求职者&#xff1a;「嗯……在Kotlin协程中&#xff0c;flow 是一种构建…

ScreenAgent CogAgent 安装日志

环境&#xff1a;python3.10 、conda 4.5.11 python ./cogagent_model_worker.py --host 0.0.0.0 --port 40000 --from_pretrained "saved_models/cogagent-chat" --bf16 --max_length 2048 报错&#xff1a; [2024-11-16 18:23:52,527] [INFO] [real_accelerato…

RHCE的学习(17)

shell特性回顾 1.echo linux打印命令 参数 -n 取消输出后行末的换行符号-e 支持反斜线控制的字符转换 \n \t ! 控制字符作 用\输出\本身 !\a输出警告音\b退格键&#xff0c;也就是向左删除键\c取消输出行末的换行符。和“-n”选项一致\eEsc键向右删除键\f换页符\n换行符\r字…

聊天服务器(7)数据模块

目录 Mysql数据库代码封装头文件与源文件 Mysql数据库代码封装 业务层代码不要直接写数据库&#xff0c;因为业务层和数据层的代码逻辑也想完全区分开。万一不想存储mysql&#xff0c;想存redis的话&#xff0c;就要改动大量业务代码。解耦合就是改起来很方便。 首先需要安装m…

FPGA使用Verilog实现CAN通信

FPGA实现CAN通信&#xff08;Verilog&#xff09; 1.作者使用的方法是通过FPGA芯片&#xff08;如Xilinx公司的型号为XC7K325TFFG676-2&#xff09;控制SJA1000T芯片&#xff08;CAN控制器芯片&#xff09;实现CAN通信&#xff0c;如下图所示&#xff1a; 2.熟悉连接方式之后&…

1Panel修改PostgreSQL时区

需求 1Panel安装的PostgreSQL默认是UTC时区&#xff0c;需要将它修改为上海时间 步骤 进入PostgreSQL的安装目录 /opt/1panel/apps/postgresql/postgresql/data打开postgresql.conf文件 修改&#xff1a; log_timezone Asia/Shanghai timezone Asia/Shanghai保存后重启…

MySQL的游标和While循环的详细对比

MySQL游标和While循环的详细对比 在 MySQL 中&#xff0c;游标和 WHILE 循环是两种常用的处理结果集的机制。它们各自有不同的应用场景和特点。本文将详细对比这两种机制&#xff0c;并提供具体的示例代码和说明。 1. 游标&#xff08;Cursor&#xff09; 游标是一种数据库对…

FPGA 第8讲 简单组合逻辑--半加器

时间&#xff1a;2024.11.16 一、学习内容 1.半加器 数字电路中加法器是经常用到的一种基本器件&#xff0c;主要用于两个数或者多个数的加和&#xff0c;加法器又分为半加器&#xff08;half adder&#xff09;和全加器&#xff08;full adder&#xff09;。 半加器电路是指…