【数据结构与算法】哈夫曼树与哈夫曼编码
文章目录
- 哈夫曼树(最优二叉树)
- 定义
- 举个🌰(WPL的计算)
- 哈夫曼树的构造(最优二叉树的构造)
- 举个🌰
- 哈夫曼树的性质
- 哈夫曼编码
- 定义
- 构造
哈夫曼树(最优二叉树)
在介绍哈夫曼树之前,我们需要介绍一些概念:
-
路径:路径是指从一个结点到另一个结点的之间所经过的所有结点构成的序列。
-
路径长度:路径长度是路径上所经过的边的个数
-
权:在应用树的时候,我们常常会将树的结点赋予一个表示某种意义的数值,这个值称为权。
-
结点的带权路径长度:从根结点到一个结点的路径长度 * 该结点的权值 = 该结点的带权路径长度。
-
树的带权路径长度(WPL):树中所有叶结点的带权路径长度之和称为树的带权路径长度
定义
在含有n个带权叶结点的二叉树中,其中带权路径最小的二叉树称为哈夫曼树,也称最优二叉树。
举个🌰(WPL的计算)

第一棵树的 W P L = 7 ∗ 2 + 5 ∗ 2 + 2 ∗ 2 + 4 ∗ 2 = 36 WPL=7*2+5*2+2*2+4*2=36 WPL=7∗2+5∗2+2∗2+4∗2=36
第二棵树的 W P L = 4 ∗ 2 + 7 ∗ 3 + 5 ∗ 3 + 2 ∗ 1 = 46 WPL=4*2+7*3+5*3+2*1=46 WPL=4∗2+7∗3+5∗3+2∗1=46
第三棵树的 W P L = 7 ∗ 1 + 5 ∗ 2 + 2 ∗ 3 + 4 ∗ 3 = 35 WPL=7*1+5*2+2*3+4*3=35 WPL=7∗1+5∗2+2∗3+4∗3=35
第三颗树的 WPL 恰好是所有含有n个带权叶结点的二叉树中最小的,因此第三棵树为哈夫曼树。
注意:证明一个树是否为哈夫曼树,要看的是所有含有n个带权叶结点的WPL,而不是给几个二叉树选其中WPL最小的。(当然,由于这种证明几乎不可能实现,所以要证明一棵树为哈夫曼树,我们只需要证明它的结构符合最优构造方法即可——因为哈夫曼树并不唯一,例如把一颗哈夫曼树的左右子树交换,它就构成了一棵新的哈夫曼树)。
哈夫曼树的构造(最优二叉树的构造)
给定 n n n 个权值分别为 w 1 , w 2 , . . . , w n w_1,w_2,...,w_n w1,w2,...,wn 的结点,构造最优二叉树的方法如下:
- 将这 n n n 个结点视为 n n n 棵只有一个结点的二叉树,它们构成了一个森林 F F F。
- 在森林中选择两颗根节点权值最小的二叉树 T 1 , T 2 T_1,T_2 T1,T2,新增一个结点 N N N,把 T 1 , T 2 T_1,T_2 T1,T2 的根节点作为 N N N 的左、右孩子构成一棵新的二叉树 T 3 T_3 T3, N N N的权值等于 T 1 , T 2 T_1,T_2 T1,T2的根的权值之和。
- 从 F F F 中删除 T 1 , T 2 T_1,T_2 T1,T2,把 T 3 T_3 T3加入到 F F F 中。
- 重复步骤 2 , 3 2,3 2,3,直到 F F F 中只剩下一颗树。
如果对哈夫曼树的构造方法的正确性感兴趣的同学,可以搜一搜哈夫曼树的构造方法的正确性证明。
举个🌰

把这几个叶结点按权值的从小到大排列,有:

选择权值最小的两个结点构成新的二叉树,有:

继续选择两个最小的结点,有:

继续:

这样我们就得到一颗哈夫曼树了
哈夫曼树的性质
- 初始结点最终都为叶结点,并且权值越小的结点到根节点的路径长度越大。
- 因此哈夫曼树的结点总数为 2 ∗ n − 1 2*n-1 2∗n−1,因为构造的过程中新增了n-1个结点(即新增了n-1个分支结点)。
- 哈弗曼树中不存在度为1的结点,因为每次构造都是选择两颗树作为新结点的子节点。
- 哈夫曼树的带权路径长度,等于所有分支结点的权值之和。
哈夫曼编码
在了解哈夫曼编码前,我们先了解一些相关的概念:
- 定长编码:长度固定的编码。
- 变长编码:长度不固定的编码。
- 前缀编码:没有一个编码是另一个编码的前缀,这样的编码叫做前缀编码(显然,根据定义来说,定长编码一定是前缀编码,变长编码不一定是前缀编码)。
对于前缀编码来说,我们可以用树辅助构造前缀编码。
例如:假设要为a,b,c,d四个字符设计二进制前缀编码,那么我们可以用二叉树来辅助构造。
为了使编码能够符合前缀编码的要求,显然,a、b、c、d不会出现在分支结点上。
我们设从任意结点往左边走代表0,从任意结点往右边走代表1,(即指向左子树的边代表0,指向右子树的边代表1)那么a、b、c、d的编码为从根节点到对应叶结点所经过的边代表的值的序列。
我们可以得到如下所示的二叉树:

- a的编码为:0
- b的编码为:10
- c的编码为:110
- d的编码为:111
显然,没有一个编码是另一个编码的前缀,这种编码是前缀编码。
定义
哈夫曼编码是一种变长的二进制前缀编码,它利用哈夫曼树来辅助构造编码,能够非常有效地压缩二进制数据。
构造
我们将每一个字符当做一个独立的结点,其权值等于它出现的次数(或频度),构造一棵哈夫曼树。
设从任意结点指向左子树的边代表0,指向右子树的边代表1或指向左子树的边表示1,指向右子树的边表示0。则各个结点的编码为从根节点到对应结点所经过的边代表的值的序列。
上面的例子就是一个构造哈夫曼编码的案例。
注意:相同结点构造出的哈夫曼树并不唯一,因为它并没有限制到底是左大右小还是右大左小。但相同结点构造出的不同的哈夫曼树的WPL一定是相同的。
同理,哈夫曼编码也是不唯一的。
全篇至此结束,感谢观看。
相关文章:
【数据结构与算法】哈夫曼树与哈夫曼编码
文章目录 哈夫曼树(最优二叉树)定义举个🌰(WPL的计算) 哈夫曼树的构造(最优二叉树的构造)举个🌰 哈夫曼树的性质 哈夫曼编码定义构造 哈夫曼树(最优二叉树) …...
基于多头注意力机制卷积神经网络结合双向门控单元CNN-BIGRU-Mutilhead-Attention实现柴油机故障诊断附matlab代码
在使用这些深度学习库时,你可以按照以下步骤构建CNN-BIGRU-Multihead-Attention模型: 导入所需的库和模块。例如,在使用TensorFlow时,你可以导入tensorflow库和其他需要的模块。 定义输入层。根据你的数据,定义适当的…...
k8s redis 单节点部署
k8s redis 单节点部署kubectl 执行脚本 kubectl --kubeconfig ~/.kube-rz-real/config apply -f redis-leader.yaml -n rz-dt vi redis-leader.yamlapiVersion: apps/v1 kind: Deployment metadata:name: redis-leader-deploylabels:app: redisrole: leadertier: backend sp…...
科普童话投稿
《科普童话》杂志是由国家新闻出版总署批准、黑龙江省教育厅主管、黑龙江省语言文字报刊社主办的正规期刊。《科普童话》以培养科学素养与创新探索精神为办刊宗旨,以科学与艺术统一为编辑方针,以科学教育、教育科学作为自己的出发点,致力于对…...
【Ardiuno】使用ESP32单片机创建web服务通过网页控制小灯开关的实验(图文)
经过实验测试ESP32单片机的网络连接还是很方便的,这里小飞鱼按照程序实例的代码亲自实验一下使用Esp32生成的网页服务来实现远程无线控制小灯开关功能,这样真的是离物联网开发越来越近了,哈哈! 连接好开发板和电路,将…...
百元蓝牙耳机哪款音质最好?四款实力超群机型推荐
在蓝牙耳机市场竞争日益激烈的今天,百元级别的耳机已经具备了令人瞩目的音质表现,对于追求高性价比的消费者来说,如何在众多选项中挑选出一款音质卓越的蓝牙耳机,无疑是一项重要而又充满挑战的任务,今天我将为大家推荐…...
Linux系统之mtr命令的基本使用
Linux系统之mtr命令的基本使用 一、mtr命令介绍二、mtr命令使用帮助2.1 mtr命令的帮助信息2.2 mtr帮助信息解释 三、安装mtr工具四、mtr命令的基本使用4.1 直接使用4.2 设定ping次数4.3 禁用DNS解析4.4 显示IP地址4.5 调整间隔 五、总结 一、mtr命令介绍 mtr命令是一个网络诊断…...
实战tcpdump4.99.4交叉编译
主要是记录交叉编译的一个坑,不知道为什么网上的教程都没遇到过。 环境 libpcap 1.10.4tcpdump 4.99.4WSL 编译步骤 注意事项 注意解压的时候文件夹名需要是libpcap-1.10.4,由于我是在github直接下载zip的压缩包名是libpcap-libpcap-1.10.4.tar.gz解…...
重生奇迹MU召唤术师简介
出生地:幻术园 性 别:女 擅 长:召唤幻兽、辅助魔法&攻击魔法 转 职:召唤巫师(3转) 介 绍:从古代开始流传下来的高贵的血缘,为了种族纯正血缘的延续及特殊使用咒术的天赋&…...
神经网络模型---AlexNet
一、AlexNet 1.导入tensorflow库,这里给简称为tf库 import tensorflow as tf from tensorflow.keras import datasets, layers, modelsdatasets:是用于训练和测试机器学习模型的数据集合 layers:是构建神经网络模型的关键组成部分 models&a…...
corona渲染器与vray比哪个好?支持云渲染平台吗
在视觉渲染技术领域,V-Ray和Corona都以其卓越的性能和广泛应用赢得了高度评价。这两款渲染器各有其独特的优势,使得在它们之间做出选择并非易事。不同的应用场景和用户需求可能会让它们各自展现出不同的优势。 一、corona渲染器跟vray怎么样 在比较V-…...
每日一练:攻防世界:Ditf
这是难度1的题吗??? 拿到一个png图片,第一反应就是CRC爆破,结果还真的是高度被修改了 这里拿到一个字符串,提交flag结果发现不是,那么只可能是密钥之类的了 看看有没有压缩包,搜索…...
约瑟夫环递归算法详解与实现
一、引言 约瑟夫环问题是一个著名的理论问题,其背景是在古罗马时期,有n个犯人被围成一个圈,从第一个人开始报数,每次报到m的人将被处决,然后从下一个人开始重新报数,直到所有人都被处决。这个问题可以用递…...
互联网应用主流框架整合之构建REST风格的系统
REST(Representational State Transfer),中文译为“表述性状态转移”,是由Roy Fielding博士在他的博士论文中提出的一种软件架构风格,特别适用于网络应用的设计。REST不是一个标准,而是一种设计原则和约束集…...
vue3-自定义指令来实现input框输入限制
文章目录 前言具体实现分析主要部分详细解析导入和类型定义mounted 钩子函数unmounted 钩子函数指令注册使用 总结 前言 使用vue中的自定义指令来实现input框输入限制 其中关键代码强制触发input ,来避免,输入规则外的字符时,没触发vue的响…...
MySQL日志——redolog
redo log(重做日志) 为什么需要redo log? 在mysql提交一个事务后,这个事务所作的数据修改并不会直接保存到磁盘文件中,而是先保存在buffer pool缓冲区中,在需要读取数据时,先从缓冲区中找&…...
Python热涨落流体力学求解算法和英伟达人工智能核评估模型
🎯要点 🎯平流扩散简单离散微分算子 | 🎯相场模拟:简单旋节线分解、枝晶凝固的 | 🎯求解二维波动方程,离散化时间导数 🎯英伟达 A100 人工智能核性能评估模型 | 🎯热涨落流体动力学…...
【C语言】数组参数和指针参数详解
在写代码的时候难免要把【数组】或者【指针】传给函数,那函数的参数该如何设计呢? 1 一维数组传参 #include <stdio.h> void test(int arr[])//ok? {} void test(int arr[10])//ok? {} void test(int* arr)//ok? {} void test2(int* arr[20])…...
Tuple 元组
文章目录 一、什么是元组 ?二、元组的具体操作2.1 创建元组2.1.1 tuple() 创建元组函数和 list() 创建列表函数总结 2.2 元组的元素访问操作2.3 元组的元素计数操作2.4 zip 对象 一、什么是元组 ? 列表属于可变序列,可以任意修改列表中的元素。 元组的…...
(资料收藏)王阳明传《知行合一》共74讲,王阳明知行合一音频讲解资料
今天给大家带来的不是软件,而是一份精神食粮——《知行合一》的教程福利。这可不是一般的教程,它关乎心灵,关乎智慧,关乎我们如何在纷繁复杂的世界中找到自己的位置。 咱们得聊聊王阳明,这位明代的大儒,他…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀”
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀” 在JavaScript中,我们经常需要处理文本、数组、对象等数据类型。但当我们需要处理文件上传、图像处理、网络通信等场景时,单纯依赖字符串或数组就显得力不从心了。这时ÿ…...
初级程序员入门指南
初级程序员入门指南 在数字化浪潮中,编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言,明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 (一)编程语言抉择 编…...
Flask和Django,你怎么选?
Flask 和 Django 是 Python 两大最流行的 Web 框架,但它们的设计哲学、目标和适用场景有显著区别。以下是详细的对比: 核心区别:哲学与定位 Django: 定位: "全栈式" Web 框架。奉行"开箱即用"的理念。 哲学: "包含…...
