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

server/2024/11/17 20:10:03/

一、哈夫曼树的基本概念

哈夫曼(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/server/142724.html

相关文章

鸿蒙系统(HarmonyOS)与OpenHarmony

一、概述 华为推出的鸿蒙系统&#xff08;HarmonyOS&#xff09;凭借其分布式架构及多设备协同能力在业界引起了广泛关注。与此同时&#xff0c;还有一个名为OpenHarmony的开源项目&#xff0c;它在推动物联网设备之间的互联互通。尽管两者同源&#xff0c;但它们的应用场景、…

Stable Diffusion Hypernetwork Embedding

本节内容&#xff0c;给大家带来的是stable diffusion的Embedding与HyperNetwork课程。在上节课程中&#xff0c;我们已经了解了关于Lora模型和LyCORIS模型的使用。我们可以通过训练Lora模型与LyCORIS模型来对基础模型进行低资源微调&#xff0c;从而实现具有某一类特征的图像产…

什么是SSL VPN?其中的协议结构是怎样的?

定义&#xff1a;SSL VPN是以SSL协议为安全基础的VPN远程接入技术&#xff0c;移动办公人员使用SSL VPN可以安全、方便的接入企业内网&#xff0c;访问企业内网资源&#xff0c;提高工作效率。 SSL&#xff08;Security Socket Layer&#xff09;是一个安全协议&#xff0c;为…

macOS解决U盘装完系统容量变小的问题

发现原来256GB容量的U盘在mac电脑上只显示34GB&#xff0c;想起来之前用该U盘装过系统&#xff0c;最终搜到了以下解决方案&#xff0c;在此记录&#xff1a; (1) 查看盘符列表&#xff0c;找到需要格式化的U盘&#xff0c;假设为disk4 diskutil list(2) 卸载分区disk4 disk…

计算机毕业设计Hadoop+Spark高考推荐系统 高考分数线预测 知识图谱 高考数据分析可视化 高考大数据 大数据毕业设计 Hadoop 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

SQL面试题——抖音SQL面试题 最大在线用户数

最大在线用户数 下面的数据记录了一个直播平台上用户进入平台和离开平台的情况 +---+-------------------+-----+ | id| etime| type| +---+-------------------+-----+ | 1|2021-06-10 10:00:00|enter| | 1|2021-06-10 19:00:00|leave| | 2|2021-06-10 11:0…

Uniapp 引入 Android aar 包 和 Android 离线打包

需求&#xff1a; 原生安卓 apk 要求嵌入到 uniapp 中&#xff0c;并通过 uniapp 前端调起 app 的相关组件。 下面手把手教你&#xff0c;从 apk 到 aar&#xff0c;以及打包冲突到如何运行&#xff0c;期间我所遇到的问题都会 一 一 进行说明&#xff0c;相关版本以我文章内为…

Ubuntu24.04配置安装可视化terminal终端

Ubuntu24.04配置安装可视化terminal终端 最开始我是想搞一下微服务&#xff0c;三台Eureka已经搞好了&#xff0c;但是配置文件总是让人难受&#xff0c;我想搞一下可以方便修改配置文件的东东&#xff0c;于是就想装一下Apollo&#xff0c;安装了一个本地Mysql版本的Apollo看…