【数据结构与算法】哈夫曼树,哈夫曼编码 详解

2024-06-22 14:20

本文主要是介绍【数据结构与算法】哈夫曼树,哈夫曼编码 详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

哈夫曼树的数据结构。

struct TreeNode {ElemType data;TreeNode *left, *right;
};
using HuffmanTree = TreeNode *;

结构体包含三个成员:

  • data 是一个 ElemType 类型的变量,用于存储哈夫曼树节点的数据。
  • left 是一个指向 TreeNode 类型的指针,用于指向哈夫曼树节点的左子节点。
  • right 是一个指向 TreeNode 类型的指针,用于指向哈夫曼树节点的右子节点。

Huffman树能够解决的问题是什么?

Huffman树,也称为Huffman编码树,主要用于数据压缩和编码。它可以解决如何以最短的方式来表示一组数据的问题,使得整体数据的存储或传输更加高效。

如何构造Huffman树?

  1. 根据给定的n个权值{w1,w2,……wn},构造n 棵二叉树的集合F={T1,T2,……,Tn},其中每棵二叉树Ti 中只有一个带权为wi 的根结点,其左右子树均为空。
  2. 在森林F中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。
  3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中。
  4. 重复上述2和3两步直到只含一棵树为止,这棵树即哈夫曼树。
TreeNode *createTreeNode(ElemType e, TreeNode *l, TreeNode *r) {TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));if (!t) {return NULL;}t->data = e;t->left = l;t->right = r;return t;
}HuffmanTree createHuffmanTree(int n, ElemType *a, int *f) {priority_queue<Node> hmin;for (int i = 0; i < n; i++) {TreeNode *t = createTreeNode(a[i], nullptr, nullptr);hmin.push({f[i], t});}while (hmin.size() > 1) {Node a = hmin.top();hmin.pop();Node b = hmin.top();hmin.pop();if (a.f > b.f) {swap(a, b);}TreeNode *t = createTreeNode(' ', a.node, b.node);// cout << a.f << " " << b.f << endl;hmin.push({a.f + b.f, t});}return hmin.top().node;
}

这篇关于【数据结构与算法】哈夫曼树,哈夫曼编码 详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1084537

相关文章

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J