【数据结构】哈夫曼树和哈夫曼编码
一、哈夫曼树
1.1 哈夫曼树的概念
给定一个序列,将序列中的所有元素作为叶子节点构建一棵二叉树,并使这棵树的带权路径长度最小,那么我们就得到了一棵哈夫曼树(又称最优二叉树)
接下来是名词解释:
- 权:节点的数值
- 路径长度:两节点间路径的边数
- 带权路径长度:节点的权值乘以该节点到根节点的路径长度即为该节点的带权路径长度。哈夫曼树的带权路径长度是树中所有叶子节点的带权路径长度之和。
例如下面这棵哈夫曼树:

通过观察我们可以发现,所有父节点的权值都是自身的两个子节点的权值之和。而为了要使树的带权路径长度最小,我们要尽可能的让权值小的节点离根节点远,让权值大的节点离根节点近。
因此,我们引出哈夫曼树的构造算法。
1.2 哈夫曼树的构造算法
要将一个序列构造成一棵哈夫曼树,我们首先需要对其进行升序排序

将排序好后的序列中的每个值看作一棵只有一个节点的树,从中选出根节点权值最小的两棵树作为新树的左右子树,并将这两棵树从序列中删除,而新树的根节点的权值是这两棵树根节点的权值之和
哈夫曼树没有规定左右子树的顺序,因此下面的例子中将10和18的位置对调也是正确的

将新树的根节点的权值放入序列中并重新进行升序排序,重复上述步骤




至此,就构建了一棵哈夫曼树
因为哈夫曼树没有规定左右子树的顺序,因此一个序列可以构建出不同的哈夫曼树
二、哈夫曼编码
2.1 等长编码
假设我们要对一个字符串ABAACDC进行二进制编码
我们可以按顺序给每个字符设置一个编码,A为0,B为1,C为10,D为11
那么就可以将上面的字符串转化为0100101110
但是在解码的时候我们会发现,这一串二进制序列可以解码为ACACDBA、ACABABDA等字符串,出现了歧义。
这是因为我们在对字符进行编码的时候,出现了一个字符是另一个字符的前缀的情况,例如D可以用两个B来表示。
为了避免歧义,我们可以采用等长编码的方案,就是每个字符的编码都一样长,例如A为00,B为01,C为10,D为11,这样就不会产生歧义了。
但是这种方案并不是一个最短的方案。
2.2 哈夫曼编码
统计字符出现的次数,把字符定义成一个节点,节点的权值就是它出现的次数。
例如上面A出现了3次,B出现了1次,C出现了2次,D出现了1次
哈夫曼编码的核心思想就是让出现次数越多的字符编出来的码越短,我们将全部节点构建成一棵哈夫曼树,出现次数越少的字符对应的节点就越靠近树的底层,编码也就越长,出现次数越多的字符编码就越短。
对二叉树的边标号,向左的边标为0,向右的边标为1,至此所有字符的编码就是从根节点到该字符节点路径上经过的标号,例如A为1,B为010,C为00,D为011,这种编码方案就叫做哈夫曼编码。

构建哈夫曼树的时候,所有的字符节点都是叶子节点,不会出现一个字符出现在另一个字符的路径上,也就不会出现一个字符是另一个字符的前缀这种造成歧义的情况
哈夫曼树的编码不是唯一的,节点放置的左右也会造成字符编码的不同,但是生成的编码长度一定都是一样的。
完.
相关文章:
【数据结构】哈夫曼树和哈夫曼编码
一、哈夫曼树 1.1 哈夫曼树的概念 给定一个序列,将序列中的所有元素作为叶子节点构建一棵二叉树,并使这棵树的带权路径长度最小,那么我们就得到了一棵哈夫曼树(又称最优二叉树) 接下来是名词解释: 权&a…...
深入探索微软Edge:领略新一代浏览器的无限可能
深入探索微软Edge:领略新一代浏览器的无限可能 在当今数字化时代,网络浏览器已经成为我们日常生活中不可或缺的一部分。而随着技术的不断进步,浏览器的功能和性能也在不断提升。微软Edge作为微软推出的全新一代浏览器,引领着浏览…...
JavaScript表达式和运算符
表达式 表达式一般由常量、变量、运算符、子表达式构成。最简单的表达式可以是一个简单的值。常量或变量。例:var a10 运算符 运算符一般用符号来表示,也有些使用关键字表示。运算符由3中类型 1.一元运算符:一个运算符能够结合一个操作数&…...
爬虫实训案例:中国大学排名
近一个月左右的时间学习爬虫,在用所积累的知识爬取了《中国大学排名》这个网站,爬取的内容虽然只是可见的文本,但对于初学者来说是一个很好的练习。在爬取的过程中,通过请求数据、解析内容、提取文本、存储数据等几个重要的内容入…...
C++ IO流
C标准IO流 使用cout进行标准输出,即数据从内存流向控制台(显示器)使用cin进行标准输入,即数据通过键盘输入到程序中使用cerr进行标准错误的输出使用clog进行日志的输出 C文件IO流 文件流对象 ofstream:只写 ofstream 是 C 中用于输出文件…...
debian nginx upsync consul 实现动态负载
1. consul 安装 wget -O- https://apt.releases.hashicorp.com/gpg | sudo gpg --dearmor -o /usr/share/keyrings/hashicorp-archive-keyring.gpg echo "deb [signed-by/usr/share/keyrings/hashicorp-archive-keyring.gpg] https://apt.releases.hashicorp.com $(lsb_r…...
前端基础入门三大核心之HTML篇 —— 同源策略的深度解析与安全实践
前端基础入门三大核心之HTML篇 —— 同源策略的深度解析与安全实践 一、同源策略:定义与起源1.1 定义浅析1.2 何为“源”?1.3 起源与意义 二、同源策略的运作机制2.1 限制范围2.2 安全边界 三、跨越同源的挑战与对策3.1 JSONP3.2 CORS3.3 postMessage 四…...
go 微服务框架 kratos 日志库使用方法及原理探究
一、Kratos 日志设计理念 kratos 日志库相关的官方文档:日志 | Kratos Kratos的日志库主要有如下特性: Logger用于对接各种日志库或日志平台,可以用现成的或者自己实现Helper是在您的项目代码中实际需要调用的,用于在业务代码里…...
VC++位移操作>>和<<以及逻辑驱动器插拔产生的掩码dbv.dbcv_unitmask进行分析的相关代码
VC位移操作>>和<<以及逻辑驱动器插拔产生的掩码dbv.dbcv_unitmask进行分析的相关代码 一、VC位移操作符<<和>>1、右位移操作符 >>:2、左位移操作符 <<: 二、逻辑驱动器插拔产生的掩码 dbv.dbcv_unitmask 进行分析的…...
查看gpu
## 查看gpu信息 if_cuda torch.cuda.is_available() print("if_cuda",if_cuda)gpu_count torch.cuda.device_count() print("gpu_count",gpu_count)...
CSS与表格设计
在网页设计中,表格是一种不可或缺的元素,用于展示和组织数据。虽然HTML提供了基本的表格结构,但通过CSS(层叠样式表)的应用,我们可以极大地提升表格的外观和用户体验。本文将探讨如何利用CSS来设计既美观又…...
阴影映射(线段树)
实时阴影是电子游戏中最为重要的画面效果之一。在计算机图形学中,通常使用阴影映射方法来实现实时阴影。 游戏开发部正在开发一款 2D 游戏,同时希望能够在 2D 游戏中模仿 3D 游戏的光影效果,请帮帮游戏开发部! 给定 x-y 平面上的…...
Docker 容器间通讯
1、虚拟ip/访问 同一网络 安装docker时,docker会默认创建一个内部的桥接网络docker0,每创建一个容器分配一个虚拟网卡,容器之间(包括宿主机)可以根据分配的ip互相访问(ps:其他主机(包括其他主机的容器)无法ping通docker容器ip无法访问&#…...
C语言章节学习归纳--数据类型、运算符与表达式
3.1 C语言的数据类型(理解) 首先,对变量的定义可以包括三个方面: 数据类型 存储类型 作用域 所谓数据类型是按被定义变量的性质,表示形式,占据存储空间的多少,构造特点来划分的。在C语言中&…...
Centos 7.9 使用 iso 搭建本地 YUM 源
Centos 7.9 使用 iso 搭建本地 YUM 源 1 建立挂载点 [rootlocalhost ~]# mkdir -p /media/cdrom/ 2 创建光盘存储路径 [rootlocalhost ~]# mkdir -p /mnt/cdrom/ 3 上传 CentOS-7-x86_64-Everything-2207-02.iso 到 光盘存储路径 [rootlocalhost ~]# ls /mnt/cdrom/ CentOS-…...
NFT Insider #131:Mocaverse NFT市值破3.5万ETH,The Sandbox 参加NFCsummit
引言:NFT Insider由NFT收藏组织WHALE Members(https://twitter.com/WHALEMembers)、BeepCrypto (https://twitter.com/beep_crypto)联合出品,浓缩每周NFT新闻,为大家带来关于NFT最全面、最新鲜、…...
BatBot智慧能源管理平台,更加有效地管理能源
随着能源消耗的不断增加,能源管理已成为全球面临的重要问题。BatBot智慧能源管理作为一种的能源管理技术,促进企业在用能效率及管理有着巨大的提升。 BatBot智慧能源管理是一种基于人工智能技术的能源管理系统,通过智能分析和优化能源使用&…...
医院预约挂号系统微信小程序APP
医院预约挂号小程序,前端后台(后台 java spring boot mysql) 医院预约挂号系统具体功能介绍:展示医院信息、可以注册和登录, 预约挂号(包含各个科室的预约,可以预约每个各个医生)&…...
【代码随想录 二叉树】二叉树前序、中序、后序遍历的迭代遍历
文章目录 1. 二叉树前序遍历(迭代法)2. 二叉树后序遍历(迭代法)3. 二叉树中序遍历(迭代法) 1. 二叉树前序遍历(迭代法) 题目连接 🍎因为处理顺序和访问顺序是一致的。所…...
Error:(6, 43) java: 程序包org.springframework.data.redis.core不存在
目录 一、在做SpringBoot整合Redis的项目时,报错: 二、尝试 三、解决办法 一、在做SpringBoot整合Redis的项目时,报错: 二、尝试 给依赖加版本号,并且把版本换了个遍,也不行,也去update过ma…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
