【数据结构】- 详解哈夫曼树（用 C 语言实现哈夫曼树的构造和哈夫曼编码）

目录

一、哈夫曼树的基本概念

二、哈夫曼树的构造算法

2.1 - 哈夫曼树的构造过程

2.2 - 哈夫曼树的存储表示

2.3 - 算法实现

三、哈夫曼编码

3.1 - 哈夫曼编码的主要思想

3.2 - 哈夫曼编码的性质

3.3 - 算法实现

 

一、哈夫曼树的基本概念

哈夫曼树的定义，涉及路径、路径长度、权等概念，下面先给出这些概念的定义，然后再介绍哈夫曼树。

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

  2. 路径长度：路径上的分支数目称作路径长度。

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

  4. 权：赋予某个实体的一个量，对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权和边权具体代表什么意义，由具体情况决定。如果在一棵树中的结点上带有权值，则对应就有带权树等概念。

  5. 结点的带权路径长度：从树根到该结点的路径长度与该结点上权值的乘积。

  6. 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作 。

在含有 n 个叶子结点的二叉树中，每个叶子结点的权值为 ，则其中 WPL 最小的二叉树称作最优二叉树或哈夫曼（Huffman）树。

例如，下图所示的 3 棵二叉树中，都含有 4 个叶子结点 a、b、c、d，分别带权 7、5、2、4。

其中 (c) 树的带权路径长度最小，可以验证，它恰为哈夫曼树。

哈夫曼树中具有不同权值的叶子结点的分布有什么特点呢？从上面的例子中，可以直观地发现，在哈夫曼树中，权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称哈夫曼算法。

二、哈夫曼树的构造算法

2.1 - 哈夫曼树的构造过程

  1. 根据给定的 n 个权值 ，构造 n 棵只有根结点的二叉树，这 n 棵二叉树构成一个森林 F（Forest）。

  2. 在森林 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

  3. 在森林 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。

  4. 重复 2 和 3，直到 F 中只含一棵树为止，这棵树便是哈夫曼树。

在构造哈夫曼树时，首先选择权值小的结点，这样保证权值大的结点离根结点较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。

例如，下图所示为上图 (c) 所示的哈夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。

注意：哈夫曼树并不唯一，但 WPL 必然相同且最优。

2.2 - 哈夫曼树的存储表示

typedef struct HTNode
{
    int weight;  // 结点的权值
    int parent;  // 结点的双亲的下标
    int left;  // 结点的左孩子的下标
    int right;  // 结点的右孩子的下标
}HTNode;
​
typedef struct HTree
{
    HTNode* data;
    int size;
}HTree;

哈夫曼树中的各结点存储在 data 指向的一个大小为 2n - 1 的动态分配的数组中。

解释 1：n 个叶子结点进行 n - 1 次合并，生成 n - 1 个度为 2 的新结点，所以总结点数 N 为 2n - 1。

解释 2：因为哈夫曼树中没有度为 1 的结点，所以一棵有 n 个叶子结点的哈夫曼树总共有 2n - 1 结点，即 N = N0 + N1 + N2 = 2N0 - 1 = 2n - 1。

将叶子结点集中存储在 data[0] ~ data[n - 1] 中，将非叶子结点存储在 data[n] ~ data[2n - 2] 中。

2.3 - 算法实现

构造哈夫曼树算法的实现可以分为两大部分：

  1. 初始化：首先动态申请 2n - 1 个单元，然后循环 2n - 1 次，将所有单元中结点的双亲、左孩子、右孩子的下标都初始化为 -1，如果是前 n 个单元，还要初始化这 n 个单元中叶子结点的权值。

  2. 创建树：循环 n - 1 次，通过 n - 1 次的选择、删除与合并来创建哈夫曼树。

HuffmanTree.c：

#include "HuffmanTree.h"
#include <stdlib.h>
​
// 在 HT->data[0] ~ HT->data[end] 中选择两个双亲的下标为 -1 且权值最小的结点，
// 并通过输出型参数 pMinIndex1 和 pMinIndex2 返回它们在 HT->data 中的下标
void Select(HTree* HT, int end, int* pMinIndex1, int* pMinIndex2)
{
    int min1 = INT_MAX;
    for (int i = 0; i <= end; ++i)
    {
        if (HT->data[i].parent == -1 && HT->data[i].weight < min1)
        {
            min1 = HT->data[i].weight;
            *pMinIndex1 = i;
        }
    }
    int min2 = INT_MAX;
    for (int i = 0; i <= end; ++i)
    {
        if (i != *pMinIndex1 && 
            HT->data[i].parent == -1 && HT->data[i].weight < min2)
        {
            min2 = HT->data[i].weight;
            *pMinIndex2 = i;
        }
    }
}
​
HTree* CreateHuffmanTree(int* weight, int n)
{
    // 初始化
    HTree* HT = (HTree*)malloc(sizeof(HTree));
    HT->data = (HTNode*)malloc(sizeof(HTNode) * (2 * n - 1));
    HT->size = 2 * n - 1;
    for (int i = 0; i < 2 * n - 1; ++i)
    {
        if (i < n)
            HT->data[i].weight = weight[i];
​
        HT->data[i].parent = -1;
        HT->data[i].left = -1;
        HT->data[i].right = -1;
    }
    // 创建树
    for (int i = n; i < 2 * n - 1; ++i)
    {
        int minIndex1, minIndex2;
        // 选择
        Select(HT, i - 1, &minIndex1, &minIndex2); 
        // 删除
        HT->data[minIndex1].parent = i;
        HT->data[minIndex2].parent = i;
        // 合并
        HT->data[i].left = minIndex1;
        HT->data[i].right = minIndex2;
        HT->data[i].weight = HT->data[minIndex1].weight + HT->data[minIndex2].weight;
    }
    return HT;
}

Test.c：

#include "HuffmanTree.h"  // 包含了哈夫曼树的存储表示以及函数声明
#include <stdio.h>
#include <stdlib.h>
​
void PreOrder(HTree* HT, int rootIndex)
{
    if (rootIndex == -1)
        return;
​
    printf("%d ", HT->data[rootIndex].weight);
    PreOrder(HT, HT->data[rootIndex].left);
    PreOrder(HT, HT->data[rootIndex].right);
}
​
void DestroyHuffmanTree(HTree* HT)
{
    free(HT->data);
    HT->data = NULL;
    HT->size = 0;
}
​
int main()
{
    int weight[8] = { 5, 29, 7, 8, 14, 23, 3, 11 };
    HTree* HT = CreateHuffmanTree(weight, 8);
    PreOrder(HT, HT->size - 1);
    // 100 42 19 8 3 5 11 23 58 29 29 14 15 7 8
    printf("\n");
    DestroyHuffmanTree(HT);
    return 0;
}

 

三、哈夫曼编码

3.1 - 哈夫曼编码的主要思想

在数据通信、数据压缩问题中，需要将数据文件转换成二进制字符 0、1 组成的二进制串，称之为编码。

假设待压缩的数据为 "abcdabcdaaaaabbbdd"，数据包含 18 个字符，其中只有 a(7 个)、b(5 个)、c(2 个)、d(4 个) 四种字符，如果采用等长编码，每个字符编码取两位即可，编码总长度为 36 位。下表所示为一种等长编码方案。

字符编码
a00
b01
c10
d11

但这并非最优的编码方案，因为每个字符出现的频率不同，如果在编码时考虑字符出现的频率，使频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不等长编码，则会获得更好的空间效率，这也是文件压缩技术的核心思想。下表所示为一种不等长编码方案，采用这种编码方案，编码总长度为 35 位。

字符编码
a0
b10
c110
d111

但是对于不等长编码，如果设计得不合理，便会给解码带来困难。例如，对于下表所示的另一种不等长编码方案。

字符编码
a0
b01
c010
d111

采用该编码方案后，上述数据编码后为 "00101111100101111100000010101111111"。但是这样的编码数据无法翻译，例如，传过去的字符串中前 4 个字符的子串 "0010" 就可有不同的译法，或是 "aba"，或是 "ac"。因此，若要设计长度不等的编码，必须满足一个条件：任何一个字符的编码都不是另一个字符的编码的前缀（最左子串）。

那么如何设计有效的用于数据压缩的二进制编码呢？我们可以利用哈夫曼树来设计。第二个表格所示的编码是以字符 a、b、c、d 在数据串 "abcdabcdaaaaabbbdd" 中出现的次数 7、5、2、4 为权值，构造下图所示的哈夫曼树，约定左分支标记为 0，右分支标记为 1，则根结点到每个叶子结点路径上的 0、1 序列即为相应字符的编码。

a、b、c、d 的哈夫曼编码分别为 0、10、110 和 111。

3.2 - 哈夫曼编码的性质

  1. 性质一：哈夫曼编码是前缀编码。

    前缀编码：如果在一个编码方案中，任一个编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。

    证明：哈夫曼编码是从根结点到叶子结点路径上的编码序列，由树的特点可知，若路径 A 是另一条路径 B 的左部分，则 B 经过了 A，则 A 的终点一定不是叶子结点。而哈夫曼编码对应路径的终点一定为叶子结点，因此，任一哈夫曼编码都不会与任意其他哈夫曼编码的前缀部分完全重叠，因此哈夫曼编码是前缀编码。

  2. 性质二：哈夫曼编码是最优前缀编码。

    对于包含 n 个字符的数据文件，分别以它们出现次数为权值构造哈夫曼树，则利用该树对应的哈夫曼编码对文件进行编码，能使文件压缩后对应的二进制文件的长度最短。、

    证明：由哈夫曼树的构造算法可知，出现次数较多的字符对应的编码较短，这便直观地说明了该定理是成立的。

3.3 - 算法实现

在构造哈夫曼树之后，求哈夫曼编码的主要思想是：依次以叶子结点出发，向上回溯至根结点位置。回溯时走左分支则生成代码 0，走右分支则生成代码 1。

由于每个哈夫曼编码是变长编码，因此使用一个字符指针数组来存放每个字符编码串的首地址。

#include "HuffmanTree.h"
#include <stdlib.h>
#include <string.h>

char** CreateHuffmanCode(HTree* HT)
{
	int n = (HT->size + 1) / 2;
	char** HC = (char**)malloc(sizeof(char*) * n);
	char* tmp = (char*)malloc(sizeof(char) * n);  // 字符编码的长度一定小于 n
	tmp[n - 1] = '\0';
	// 逐个求 n 个字符的哈夫曼编码
	for (int i = 0; i < n; ++i)
	{
		int pos = n - 2;
		int cur = i;
		int parent = HT->data[i].parent;
		while (parent != -1)
		{
			if (HT->data[parent].left == cur)
				tmp[pos--] = '0';
			else
				tmp[pos--] = '1';
			// 向上回溯
			cur = parent;
			parent = HT->data[parent].parent;
		}
		HC[i] = (char*)malloc(sizeof(char) * (n - 1 - pos));
		strcpy(HC[i], &tmp[pos + 1]);
	}
	free(tmp);
	tmp = NULL;
	return HC;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/224906.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

c语言五子棋

c语言五子棋

下面是一个简单的C语言五子棋实现示例&#xff1a; #include <stdio.h>#include <stdlib.h>#define BOARD_SIZE 15char board[BOARD_SIZE][BOARD_SIZE];void init_board() { int i, j; for (i 0; i < BOARD_SIZE; i) { for (j 0; j < BOARD_…
阅读更多...
“2024京津冀人工智能大会”推动京津冀人工智能产业快速发展

“2024京津冀人工智能大会”推动京津冀人工智能产业快速发展

作为全球科技创新的前沿阵地&#xff0c;北京的人工智能产业近年来得到了迅速发展。在京津冀地区&#xff0c;人工智能产业已经成为了一个热点领域&#xff0c;产业规模和创新能力在全国居于领先地位。在这个背景下&#xff0c;2024北京国际人工智能展览会&#xff08;简称:世亚…
阅读更多...
Sql Server 2017主从配置之：AlwaysOn高可用

Sql Server 2017主从配置之：AlwaysOn高可用

AlwaysOn高可用功能&#xff0c;真正实现了数据库的灾备切换、高可用。 AlwaysOn通过Windows Server故障转移群集&#xff0c;部署高可用数据库组。 在故障转移群集基础上完成部署读写分离&#xff0c;只读负载平衡最多3个写入节点实现故障转移最多3个数据实时同步节点 环境…
阅读更多...
MySQL 8创建数据库、数据表、插入数据并且查询数据

MySQL 8创建数据库、数据表、插入数据并且查询数据

我使用的数据库是MySQL 8。 创建数据库 create database Bookbought; -- 创建数据库Bookbought use Bookbought; -- 使用数据库Bookbought创建数据表 创建用户表bookuser。 create table ## 往allbook里边插入数据(id INT PRIMARY KEY AUTO_INCREMENT, -- id 为 主键userna…
阅读更多...
什么是https加密协议，相比http的好处在哪？

什么是https加密协议，相比http的好处在哪？

先了解什么是http HTTP&#xff08;Hypertext Transfer Protocol&#xff09;是一种用于在计算机网络上传输超文本的应用层协议。它是一种无状态的、无连接的协议&#xff0c;通常用于在Web浏览器和服务器之间传输HTML页面、图片、音频、视频以及其他数据资源。 以下是HTTP的…
阅读更多...
圆通单号查询，圆通速递物流查询，对需要的单号进行颜色标记

圆通单号查询，圆通速递物流查询，对需要的单号进行颜色标记

批量查询圆通速递单号的物流信息&#xff0c;并对需要的单号进行颜色标记。 所需工具&#xff1a; 一个【快递批量查询高手】软件 圆通速递单号若干 操作步骤&#xff1a; 步骤1&#xff1a;运行【快递批量查询高手】软件&#xff0c;第一次使用的伙伴记得先注册&#xff0c…
阅读更多...
249：vue+openlayers 经纬度坐标转化为地址信息，点击后在弹窗显示

249：vue+openlayers 经纬度坐标转化为地址信息，点击后在弹窗显示

第249个 点击查看专栏目录 本示例是演示如何在vue+openlayers项目中点击某点，转化经纬度坐标为地址信息，弹窗显示。 通过点击地图，获取到经纬度坐标，然后通过调取mapbox的地址转换API，将经纬度坐标转化为地址信息，通过overlay的方式，在弹窗中展示出来。 直接复制下面的…
阅读更多...
API接口使用方法（封装好的电商平台）

API接口使用方法（封装好的电商平台）

为了进行此平台API的调用&#xff0c;首先我们需要做下面几件事情。 1、 获取一个KEY。 点击获取 2、 参考API文档里的接入方式和示例。 3、查看测试工具是否有需要的接口&#xff0c;响应实例的返回字段是否符合参数要求。 4、利用平台的文档中心和API测试工具&#xff0c…
阅读更多...
可视化监控云平台/智能监控平台EasyCVR国标设备开启音频没有声音是什么原因？

可视化监控云平台/智能监控平台EasyCVR国标设备开启音频没有声音是什么原因？

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。GB28181视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云存…
阅读更多...
从零开始的c语言日记day40——字符函数和字符串函数——内存函数

从零开始的c语言日记day40——字符函数和字符串函数——内存函数

常用函数介绍 求字符串长度 strlen 长度不受限制的字符串函数 Strcpy Strcat strcmp 长度受限制的字符串函数介绍 strncpy strncat strncmp 字符串查找 Strstro strtok 错误信息报告 strerror 字符操作 内存操作函数 memcpy memmove memset Memcmp 使用Asser…
阅读更多...
Vue学习计划-Vue2--VueCLi（一）准备工作，安装node、vuecli

Vue学习计划-Vue2--VueCLi（一）准备工作，安装node、vuecli

1. 安装node 网址&#xff1a;https://nodejs.org/en下载LTS版本表示长期支持版本说明&#xff1a; node是一个基于Chrome V8引擎的javascript运行环境,让JavaScript 运行在服务端的开发平台vuecli创建的项目必须运行在node环境中&#xff0c;npm为node自带包管理工具&#xf…
阅读更多...
100G光模块的选购技巧——帮助您节省数据中心成本

100G光模块的选购技巧——帮助您节省数据中心成本

数据中心在确保信息的即时可用性和访问性方面扮演着至关重要的角色。随着数据呈指数级增长&#xff0c;数据中心运营商一直在积极寻求优化其基础设施和降低成本的有效途径。在数据中心这个复杂生态系统中&#xff0c;100G光模块是一个不可或缺的部分&#xff0c;它对于实现高速…
阅读更多...
C#如何使用SqlSugar操作MySQL/SQL Server数据库

C#如何使用SqlSugar操作MySQL/SQL Server数据库

一. SqlSugar 连接MySQL数据库 public class MySqlCNHelper : Singleton<MySqlCNHelper>{public static SqlSugarClient CnDB;public void InitDB() {//--------------------MySQL--------------------CnDB new SqlSugarClient(new ConnectionConfig(){ConnectionString…
阅读更多...
【C++11(二)】lambda表达式以及function包装器

【C++11(二)】lambda表达式以及function包装器

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; C11 1. 前言2. lambda表达式的提出3. lambda表达…
阅读更多...
STM32F1定时器TIM

STM32F1定时器TIM

目录 1. TIM&#xff08;Timer&#xff09;定时器 2. 定时器类型 2.1 基本定时器框图 2.2 通用定时器框图 2.3 高级定时器框图 3. 定时器代码 3.1 恢复缺省配置 3.2 时基单元初始化 3.3 结构体变量附一个默认值 3.4 使能计数器 3.5 使能中断输出信号 3.…
阅读更多...
Office Tool Plus 使用教程 让个人也能轻松使用上免费的Office

Office Tool Plus 使用教程 让个人也能轻松使用上免费的Office

&#x1f680; 个人主页 极客小俊 ✍&#x1f3fb; 作者简介&#xff1a;web开发者、设计师、技术分享博主 &#x1f40b; 希望大家多多支持一下, 我们一起学习和进步&#xff01;&#x1f604; &#x1f3c5; 如果文章对你有帮助的话&#xff0c;欢迎评论 &#x1f4ac;点赞&a…
阅读更多...
网络安全（四）--Linux 主机防火墙

网络安全（四）--Linux 主机防火墙

7.1. 介绍 防火墙&#xff08;Firewall&#xff09;&#xff0c;也称防护墙&#xff0c;是由Check Point创立者Gil Shwed于1993年发明并引入国际互联网&#xff08;US5606668&#xff08;A&#xff09;1993-12-15&#xff09;。 它是一种位于内部网络与外部网络之间的网络安全…
阅读更多...
Unity中Batching优化的动态合批

Unity中Batching优化的动态合批

文章目录 前言一、动态合批的规则1、材质相同是合批的前提&#xff0c;但是如果是材质实例的话&#xff0c;则一样无法合批。2、支持不同网格的合批3、动态合批需要网格支持的顶点条件二、我们导入一个模型并且制作一个Shader&#xff0c;来测试动态合批1、我们选择模型的 Mesh…
阅读更多...
第十一节HarmonyOS 常用容器组件2-List和Grid

第十一节HarmonyOS 常用容器组件2-List和Grid

一、List列表组件的使用 1、简介 List是很常见的滚动类容器组件&#xff0c;一般和子组件ListItem一起使用&#xff0c;List列表中每一个列表项对应一个ListItem组件。 2、List组件使用ForEeach渲染列表 一个列表往往由多个相似的Item项组成&#xff0c;所以一个List组件中包含…
阅读更多...
​Python Flask库：web开发神器

​Python Flask库：web开发神器

概要&#xff1a; Python是一种广泛应用的编程语言&#xff0c;它在Web开发领域中有着丰富的库和框架。其中&#xff0c;Flask是一款轻量级的Web应用框架&#xff0c;它简单而灵活&#xff0c;适用于从简单的静态网页到复杂的Web应用的开发。本文将详细介绍使用Python Flask库…
阅读更多...
最新文章

Copyright @ 2022~2023