当前位置： 首页 > news >正文

数据结构----哈夫曼树

news 2026/3/28 4:56:22

这里写目录标题

  • 基本概念
    • 引子
    • 基本概念
      • 各种路径长度
      • 各种带权路径长度
        • 结点的带权路径长度
        • 树的带权路径长度
        • 哈夫曼树
    • 哈夫曼树的构造
      • 理论基础
      • 构造思想
      • 总结
    • 哈夫曼树的实现
    • 哈夫曼编码
      • 前缀编码
      • 哈夫曼编码的思想
      • 案例
      • 代码实现
    • 编码与解码

基本概念

引子

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
哈夫曼树就是寻找构造最优二叉树，用于提高效率

基本概念

各种路径长度

在这里插入图片描述
在这里插入图片描述

各种带权路径长度

结点的带权路径长度

在这里插入图片描述
在这里插入图片描述

树的带权路径长度

在这里插入图片描述

在这里插入图片描述

哈夫曼树

在这里插入图片描述
带权路径长度最短的树或者二叉树

也就是树的叶子结点带权路径长度之和 ：也就是叶子结点的结点路径长度（根结点到叶子结点的路径数） *权重 再求和
在这里插入图片描述
在这里插入图片描述
总结：位高权重
并且哈夫曼树不唯一

哈夫曼树的构造

理论基础

在这里插入图片描述
在这里插入图片描述

构造思想

在这里插入图片描述
可以看到 先将所有结点看成根结点构造出森林 并将权重赋值给结点
之后 选择两个小权重的结点 二者构造出新树 如上图 新树根结点权重为子树结点权重之和
这时要先将森林中的两个树删除 之后 将两个树构造成的新树加入森林（为了进行下一次权重的比较 从而下一步构造的顺利进行）
重复23步 直到剩单根

在这里插入图片描述
在这里插入图片描述
度 是指结点有的子树个数

哈夫曼树结点的度只能是0或者2
n个叶子结点的哈夫曼树 一共有2n-1个结点 分析如上橙色框

总结

在这里插入图片描述

哈夫曼树的实现

在这里插入图片描述
首先是已知叶子结点的个数以及权重

依次放入结构数组的前面 数组一共长度是2n 因为结点一共有2n-1 所以构造2n的数组 不用0下标

进行第二步 合并的时候 将新合并出来的结点往后依次放入 所以根结点是数组中的最后一个位置

新节点合成的时候 要修改新节点数组中的孩子结点下标 两个孩子要修改数组中双亲的下标

之后重复查找最小的权重的两个结点 前提是parent值是空 这是判断的关键 一旦parent值不为空的时候 就相当于退出了比较

在这里插入图片描述
在这里插入图片描述
初始化

在这里插入图片描述
上图中select方法 功能是在HT[K]中选择两个双亲域为0并且权重最小的结点 并返回s1 s2 用于后续操作

方法参数中i-1 是新合成结点的下标 ，在选最小的两个结点时 要从新节点前面选 这里对应理论分析中“第三步的a步骤”
i会逐渐递增

哈夫曼编码

前缀编码

在这里插入图片描述
图中为非前缀编码 所以要设计任意一个字符的编码都不是另一个字符编码的前缀
但是可以前缀一样 后面不一样

哈夫曼编码的思想

在这里插入图片描述
要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点
在这里插入图片描述
所以在路径上标注0 或者 1
看从根结点到某一个叶子结点经过的路径 那些路径得出来的编码就是字符对应的二进制编码

因为叶子结点不会出现一个字符的路径完全包含另一个字符的路径 所以也就是前缀编码
并且要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点 所以哈夫曼编码效率更高
在这里插入图片描述
因为叶子结点不会出现一个字符的路径完全包含另一个字符的路径 所以也就是前缀编码
并且要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点 所以哈夫曼编码效率更高

案例

在这里插入图片描述
先根据哈夫曼树的设计思想 画出来哈夫曼树 在路径上标注0 1
在这里插入图片描述

代码实现

在这里插入图片描述
在这里插入图片描述
其中HC数组是指针数组 每个指针指向对应的字符串 也就是字符串的头指针

编码与解码

在这里插入图片描述
进行哈夫曼编码时 构造指针数组
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
先根据哈夫曼树的构造思想+字符频度表 构造出哈夫曼树 标上各个叶子结点代表的字符 之后开始解码 0就向左走 1就向右走 直到走到叶子结点 记录一个字符 重复此操作即可

相关文章：

数据结构----哈夫曼树

这里写目录标题 基本概念引子基本概念各种路径长度各种带权路径长度结点的带权路径长度树的带权路径长度哈夫曼树 哈夫曼树的构造理论基础构造思想总结 哈夫曼树的实现哈夫曼编码前缀编码哈夫曼编码的思想案例代码实现 编码与解码 基本概念 引子 哈夫曼树就是寻找构造最优二叉…...

编程日记 2023/8/18 2:31:26

Spring之Aop切面---日志收集（环绕处理、前置处理方式）--使用/教程/实例

Spring之Aop切面---日志收集（环绕处理、前置处理方式）--使用/教程/实例 简介系统登录日志类LoginLogEntity .java 一、环绕处理方式1、自定义注解类LoginLogAop.class2、切面处理类LogoutLogAspect.java 二、前置处理方式：1、自定义注解类Log…...

编程日记 2023/8/18 2:30:25

UE4/UE5 照明构建失败 “Lightmass crashed”解决“数组索引越界”

在构建全局光照时,经常会出现“Lightmass crashed”的错误,导致光照构建失败。本文将分析这一问题的原因,并给出解决建议。 UE4 版本4.26 报错如下&#xff1a; <None> Lightmass crashed: Assertion failed: (Index > 0) & (Index < ArrayNum) [File:d:\bu…...

编程日记 2023/8/18 2:29:21

并发编程系列-Semaphore

Semaphore&#xff0c;如今通常被翻译为"信号量"&#xff0c;过去也曾被翻译为"信号灯"&#xff0c;因为类似于现实生活中的红绿灯&#xff0c;车辆是否能通行取决于是否是绿灯。同样&#xff0c;在编程世界中&#xff0c;线程是否能执行取决于信号量是否允…...

编程日记 2023/8/18 2:28:20

3年 Android 开发的面试心经（后悔当初没有拿 N+1）

作者&#xff1a;勇闯天涯 当某人顺利通过大厂面试时&#xff0c;总会有人认为这是运气比较好罢了&#xff0c;但他们不曾得知对方之前受过多少苦和委屈&#xff0c;又付出了多少努力一步步去突破这些困境。正是因为他们的努力付出&#xff0c;在合适的时间与地点&#xff0c;用…...

编程日记 2023/8/18 2:27:18

【c语言】 -- 指针进阶

&#x1f4d5;博主介绍&#xff1a;目前大一正在学习c语言&#xff0c;数据结构&#xff0c;计算机网络。 c语言学习&#xff0c;是为了更好的学习其他的编程语言&#xff0c;C语言是母体语言&#xff0c;是人机交互接近底层的桥梁。 本章来学习指针进阶。 让我们开启c语言学习…...

编程日记 2023/8/18 2:26:17

软件压力测试对软件产品起到什么作用?

一、软件压力测试是什么? 软件压力测试是一种通过模拟正常使用环境中可能出现的大量用户和大数据量的情况&#xff0c;来评估软件系统在压力下的稳定性和性能表现的测试方法。在软件开发过程中&#xff0c;经常会遇到一些性能瓶颈和稳定性问题&#xff0c;而软件压力测试的作…...

编程日记 2023/8/18 2:25:16

Stephen Wolfram：那么…ChatGPT 在做什么，为什么它有效呢？

So … What Is ChatGPT Doing, and Why Does It Work? 那么…ChatGPT在做什么&#xff0c;为什么它有效呢&#xff1f; The basic concept of ChatGPT is at some level rather simple. Start from a huge sample of human-created text from the web, books, etc. Then train…...

编程日记 2023/8/18 2:24:14

机器学习基础（五）

决策树 决策树是一种预测模型，它代表着对象属属性与对象值之间的一种映射关系。树中的每个节点代表一个对象，分叉路径（或者叫树枝）则代表一个属性值。 决策树常用方法： 分类树分析，是一种监督学习，用于预计结果可能为离散类型。 回归树分析，用于预计结果为实数。 CART，…...

编程日记 2023/8/18 2:23:13

阿里云服务器安装WordPress网站教程基于CentOS系统

阿里云百科分享使用阿里云服务器安装WordPress博客网站教程&#xff0c;WordPress是使用PHP语言开发的博客平台&#xff0c;在支持PHP和MySQL数据库的服务器上&#xff0c;您可以用WordPress架设自己的网站&#xff0c;也可以用作内容管理系统&#xff08;CMS&#xff09;。本教…...

编程日记 2023/8/18 2:22:12

【100天精通python】Day37：GUI界面编程_PyQT从入门到实战（上）

目录 专栏导读 1 PyQt6 简介&#xff1a; 1.1 安装 PyQt6 和相关工具&#xff1a; 1.2 PyQt6 基础知识&#xff1a; 1.2.1 Qt 的基本概念和组件&#xff1a; 1.2.2 创建和使用 Qt 窗口、标签、按钮等基本组件 1.2.3 布局管理器&#xff1a;垂直布局、水平布局、网格布局…...

编程日记 2023/8/18 2:21:11

数据结构—散列表的查找

7.4散列表的查找 7.4.1散列表的基本概念 基本思想&#xff1a;记录的存储位置域关键字之间存在对应关系 ​ 对应关系——hash函数 ​ Loc&#xff08;i&#xff09; H&#xff08;keyi&#xff09; 如何查找&#xff1a; 根据散列函数 H(key) k 查找key9&#xff0c;则访…...

编程日记 2023/8/18 2:20:09

Expo项目 使用Native base UI库

装包&#xff1a; yarn add native-base expo install react-native-svg12.1.1 Index.js: import React from react import { View, Text } from react-native import useList from ./useList import { NativeBaseProvider, Button, Box } from native-base import styles f…...

编程日记 2023/8/18 2:19:08

74、75、76——tomcat项目实战

tomcat项目实战 tomcat 依赖 java运行环境，必须要有jre ， 选择 jdk1.8 JvmPertest 千万不能用 kyj易捷支付 项目机器 选择 一台机器 ，安装jdk1.8的机器下载tomcat的包 上传到机器，解压tomcattomcat文件 bin文件夹： 启动文件 堆栈配置文件 catalina.sh JAVA_OPTS="-Xm…...

编程日记 2023/8/18 2:18:06

jmeter errstr :“unsupported field type for multipart.FileHeader“

在使用jmeter测试接口的时候&#xff0c;提示errstr :"unsupported field type for multipart.FileHeader"如图所示 这是因为我们 在HTTP信息头管理加content-type参数有问题 直接在HTTP请求中&#xff0c;勾选&#xff1a; use multipart/form-data for POST【中文…...

编程日记 2023/8/18 2:17:05

C#调用C++ DLL传参byte[]数组字节值大于127时会变为0x3f的问题解决

最近做了一个网络编程的DLL给C#调用&#xff0c;DLL中封装了一个TCP Client的函数接口&#xff0c;如下所示 //C TCP报文发送接口 int TcpClient_send(unsigned char* buffSend, unsigned int nLen) {unsigned char buff[1024];int len StringToHex(buffSend, buff);int nRet…...

编程日记 2023/8/18 2:16:03

【vue3+xlxs+xlsx-style-vite】vue3项目中使用xlsx插件实现Excel表格的导出和解析，已实现

在vue3项目中使用xlsx插件实现Excel表格的导出和解析 1、xlsx插件包官方 xlsx插件包官方 2、FileReader官方文档&#xff1a;FileReader官方文档 安装xlsx和xlsx-style-vite、file-saver npm install xlsx npm install xlsx-style-vite npm install file-saverpackage.json中查…...

编程日记 2023/8/18 2:15:02

Doris2.0时代的一些机遇和挑战！

300万字&#xff01;全网最全大数据学习面试社区等你来&#xff01; 上个周五的时候&#xff0c;Doris官宣了2.0版本&#xff0c;除了在性能上的大幅提升&#xff0c;还有一些特性需要大家特别关注。 根据官网的描述&#xff0c;Doris在下面领域都有了长足进步&#xff1a; 日志…...

编程日记 2023/8/18 2:14:00

Leetcode-每日一题【剑指 Offer 32 - I. 从上到下打印二叉树】

题目 从上到下打印出二叉树的每个节点&#xff0c;同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回&#xff1a; [3,9,20,15,7] 提示&#xff1a; 节点总数 < 1000 解题思路 1.题目要求我们从…...

编程日记 2023/8/18 2:12:59

网神 SecGate 3600 防火墙任意文件上传漏洞复现

0x01 产品简介 网神SecGate3600下一代极速防火墙&#xff08;NSG系列&#xff09;是基于完全自主研发、经受市场检验的成熟稳定网神第三代SecOS操作系统 并且在专业防火墙、VPN、IPS的多年产品经验积累基础上精心研发的高性能下一代防火墙 专门为运营商、政府、军队、教育、大型…...

编程日记 2023/8/18 2:11:57

2026-03-27：替换至多一个元素后最长非递减子数组。用go语言，给定一个整数数组 nums。 你最多只能选择其中一个位置的元素，把它改成任意整数（也可以选择不改）。 在允许这种“最多一次改动”的

2026-03-27&#xff1a;替换至多一个元素后最长非递减子数组。用go语言&#xff0c;给定一个整数数组 nums。 你最多只能选择其中一个位置的元素&#xff0c;把它改成任意整数&#xff08;也可以选择不改&#xff09;。 在允许这种“最多一次改动”的情况下&#xff0c;求能得到…...

编程新知 2026/3/28 4:44:03

UniHacker：跨平台支持的开源工具快速部署方案

UniHacker&#xff1a;跨平台支持的开源工具快速部署方案 【免费下载链接】UniHacker 为Windows、MacOS、Linux和Docker修补所有版本的Unity3D和UnityHub 项目地址: https://gitcode.com/GitHub_Trending/un/UniHacker UniHacker作为一款专业的开源工具&#xff0c;凭借…...

编程新知 2026/3/28 4:17:55

AI编程实战：如何用Cursor和Coze在1小时内完成文生图小程序开发

AI编程实战&#xff1a;如何用Cursor和Coze在1小时内完成文生图小程序开发 当产品灵感突然闪现&#xff0c;如何在最短时间内将它变成可交互的原型&#xff1f;传统开发流程中&#xff0c;从UI设计到API对接至少需要数天时间。而现在&#xff0c;借助AI编程工具链&#xff0c;我…...

编程新知 2026/3/28 3:33:29

云上实战说 | TapNow x Google Cloud 带您体验从灵感到资产的秒级转化

以下文章来源于谷歌云服务&#xff0c;作者 Google Cloud基于 Google Cloud Veo 和 Nano Banana 的前沿能力&#xff0c;TapNow (万物形象所) 邀您体验生成式 AI 如何重塑品牌与自我表达。现场实时生成风格化写真、宠物贴纸及周边&#xff0c;直观感受从灵感到资产的极速转化&a…...

编程新知 2026/3/28 3:19:20

ai结对编程实践：如何利用kimi在快马平台智能辅助完成用户认证系统开发

AI结对编程实践&#xff1a;如何利用Kimi在快马平台智能辅助完成用户认证系统开发 最近在开发一个需要用户认证功能的项目&#xff0c;后端用Node.js Express&#xff0c;前端用Vue。作为一个独立开发者&#xff0c;面对这种前后端都要兼顾的情况&#xff0c;我决定尝试用Kimi…...

编程新知 2026/3/28 2:18:51

H3六边形层次化地理空间索引：重新定义空间数据处理的颠覆式突破

H3六边形层次化地理空间索引&#xff1a;重新定义空间数据处理的颠覆式突破 【免费下载链接】h3 Hexagonal hierarchical geospatial indexing system 项目地址: https://gitcode.com/gh_mirrors/h3/h3 地理空间数据处理长期面临着精度与效率难以兼顾的困境。传统网格系…...

编程新知 2026/3/28 2:18:50

如何选择可靠的第三方软件测试机构，构建全生命周期的软件安全防线

在数字化转型的浪潮中&#xff0c;软件已成为企业运营的核心。然而&#xff0c;伴随其重要性一同增长的&#xff0c;是日益严峻的安全威胁。传统软件开发流程中&#xff0c;安全测试往往被置于交付前的独立环节&#xff0c;这种“事后补丁”的模式导致安全漏洞发现晚、修复成本…...

编程新知 2026/3/28 1:33:46

轻量级AI写作工坊：OpenClaw+nanobot内容创作流

轻量级AI写作工坊&#xff1a;OpenClawnanobot内容创作流 1. 为什么需要自动化写作助手 作为一名技术博主兼自媒体运营者&#xff0c;我每天都要面对内容创作的"三重压力"&#xff1a;选题焦虑、写作耗时、发布繁琐。最痛苦的是&#xff0c;当我花两小时写完一篇技…...

编程新知 2026/3/28 0:31:28

Play Integrity Fix：高效解决Android设备认证问题的实战指南

Play Integrity Fix&#xff1a;高效解决Android设备认证问题的实战指南 【免费下载链接】PlayIntegrityFix Fix Play Integrity (and SafetyNet) verdicts. 项目地址: https://gitcode.com/GitHub_Trending/pl/PlayIntegrityFix 问题引入&#xff1a;Android设备认证的…...

编程新知 2026/3/28 0:21:23

PCB布局设计规范与最佳实践指南

PCB布局设计的最佳实践指南1. 布局设计基础原则1.1 结构约束优先处理在PCB布局初期&#xff0c;必须优先考虑机械结构约束条件&#xff1a;根据导入的结构文件定位所有有特殊位置要求的器件连接器1脚位置必须与结构设计完全匹配严格遵守产品设计中规定的元件限高要求1.2 美观与…...

编程新知 2026/3/28 0:15:21