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

【数据结构】哈夫曼树

哈夫曼树

路径长度:从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径,路径上的分支数目称为路径长度

树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记为WPL= ∑ k = 1 n w k l k \sum^{n}_{k=1}w_kl_k k=1nwklk

带权路径长度最小的二叉树称为最优二叉树哈夫曼树

注意

哈夫曼树不一定是完全二叉树

书中一定没有度为1的结点

树中权值最小的两个结点一定是兄弟

包含n个叶子节点的哈夫曼树共有2n-1个结点

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树,共形成n-1个新结点,且度为2

树中任意非叶子节点的权值一定不小于下一层任意结点的权值

哈夫曼树的构造

哈夫曼算法:

  1. 根据给定的权值构成n棵二叉树的森林,每棵树只有一个带权为wi的根节点
  2. 在森林中选取两棵根节点权值最小的树作为左右子树,构造一棵新的二叉树,且设置新的二叉树的根节点的权值为其左右子树的权值和
  3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中
  4. 重复(2)(3),直到森林中只有一棵树为止,这棵树即为哈夫曼树(重复第二步时不一定选用新树)

哈夫曼树的实现

采用顺序存储结构

typedef struct{int weight;int parent,lch,rch;
}HTNode,*HTree;
void CreateHuffmanTree(HuffmanTree HT,int n){if(n<=1)return;m=2*n-1;//数组共2n-1个元素HT=new HTNode[m+1];//0号单元未用,HT[m]表示根节点for(i=1;i<=m;i++){	//将2n-1个元素的lch、rch、parent置为0HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;//输入前n个元素的weight值//初始化结束,下面开始建立哈夫曼树for(i=n+1;i<=m;i++){	//合并产生n-1个结点——构造Huffman树Select(HT,i-1,s1,s2);//在HT[k]中选择两个双亲域为0,且权值最小的结点,并返回它们在HT中的序号s1和s2HT[s1].parent=i;HT[s2].parent=i;	//表示从F中删除s1、s2HT[i].lch=s1;	HT[i].rch=s2;	//s1,s2分别作为i的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子权值之和}
}

哈夫曼编码

将编码设计为不等长的二进制编码,让代传字符中出现次数较多的字符采用较短的编码

前缀编码:任一个字符的编码都不是另一个字符的字符的编码的前缀

构造哈夫曼编码:

  1. 将字符出现的频率作为权值,构建哈夫曼树
  2. 从根节点出发,左分支标记0,右分支标记1
  3. 从根节点出发,到叶子节点,路过的所有分支的编码组合起来,就是哈夫曼编码

相关文章:

【数据结构】哈夫曼树

哈夫曼树 路径长度&#xff1a;从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径&#xff0c;路径上的分支数目称为路径长度 树的带权路径长度&#xff1a;树中所有叶子结点的带权路径长度之和&#xff0c;通常记为WPL ∑ k 1 n w k l k \sum^{n}_{k1}w_kl_k …...

springboot422甘肃旅游服务平台代码-(论文+源码)_kaic

摘 要 使用旧方法对甘肃旅游服务平台的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在甘肃旅游服务平台的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次开发的…...

docker中安装minio

1.首先需要搜索可用镜像&#xff0c;当然也可以不用 docker search minio/minio 2.拉取镜像 docker pull minio/minio 3.在本地新建两个文件夹路径 mkdir -p /opt/minio/datamkdir -p /opt/minio/config解释一下&#xff0c;data是文件存储的首路径。config是配置路径&…...

golang实现简单的reids服务2

golang实现redis兼容的redis服务实现redis兼容的redis服务思路 golang实现redis兼容的redis服务 之前做的redis服务是通过tcp封装的自定义协议 原版项目地址:https://github.com/dengjiayue/my-redis.git 那么能不能实现一个redis兼容的redis服务,这样一般的redis包也可以调…...

跟李笑来学美式俚语(Most Common American Idioms): Part 67

Most Common American Idioms: Part 67 前言 本文是学习李笑来的Most Common American Idioms这本书的学习笔记&#xff0c;自用。 Github仓库链接&#xff1a;https://github.com/xiaolai/most-common-american-idioms 使用方法: 直接下载下来&#xff08;或者clone到本地…...

QT 中 QDateTime::currentDateTime() 输出格式备查

基础 QDateTime::currentDateTime() //当前的日期和时间。 QDateTime::toString() //以特定的格式输出时间&#xff0c;格式 yyyy: 年份&#xff08;4位数&#xff09; MM: 月份&#xff08;两位数&#xff0c;07表示七月&#xff09; dd: 日期&#xff08;两位数&#xff0c…...

安卓手机怎么轻松转换更新ip网络地址

随着移动互联网的快速发展&#xff0c;IP地址作为网络身份标识的重要性日益凸显。对于安卓手机用户来说&#xff0c;但有时候我们希望能够轻松转更换ip地址&#xff0c;以提高网络安全性或访问特定内容的需要。那么&#xff0c;安卓手机如何更换IP地址呢&#xff1f;本文将为您…...

spring项目添加本地依赖,报java程序包不存在

删除引入程序中的iml文件 重新在当前项目目录下构建项目...

嵌入式硬件-- 元器件焊接

1.锡膏的使用 锡膏要保存在冰箱里。 焊接排线端子&#xff1b;138度的低温锡&#xff08;锡膏&#xff09;&#xff0c; 第一次使用&#xff0c;直接拿东西挑一点涂在引脚上&#xff0c;不知道多少合适&#xff0c;加热台加热到260左右&#xff0c;放在上面观察锡融化&#…...

物联网入门-Arduino的下载与配置教程(以ESP32为例)-2024

教程介绍 本次教程主要讲述如何下载与配置Arduino&#xff0c;以及开发版对应驱动的下载安装 原文链接&#xff1a;物联网入门-Arduino的下载与配置教程(以ESP32为例)-2024 步骤概述 1&#xff1a;下载Arduino 2&#xff1a;安装Arduino 3&#xff1a;下载安装驱动 4&am…...

防火墙旁挂部署+故障切换

一、实验环境 华为ENSP 二、拓扑 三、目的 1、内网PC1访问Server 2、防火墙旁挂部署&#xff0c;对流量进行过滤&#xff0c;防火墙挂掉之后&#xff0c;内网PC1能继续访问到Server 3、防火墙恢复正常后&#xff0c;流量能回切至防火墙转发 四、思路&#xff1a; 1、AR1…...

PyTorch基本使用-张量的基本运算及函数计算

文章目录 1. 张量数值计算1. 1 张量基本运算1.2 点乘运算1.3 矩阵运算 2. 张量运算函数 1. 张量数值计算 1. 1 张量基本运算 加减乘除取负号&#xff1a; add、sub、mul、div、neg add_ 、sub_、 mul_ 、div_、 neg_ (其中带下划线的版本会修改原数据) data torch.randin…...

C#--方法

C#的代码包装 三种实现途径&#xff1a;方法、类和名字空间。 • 方法是包含一系列语句的代码块。 • 类用于组合类&#xff0c;方法&#xff0c;属性。 • 将多个相关类组合成名字空间。 静态方法和静态变量 • 静态成员 在类中&#xff0c;使用static修饰符声明的成员称为静态…...

前端权限控制

前端权限控制 一、路由权限&#xff08;控制页面访问&#xff09; vue // router.js const routes [{path: /dashboard,name: Dashboard,component: () > import(/views/Dashboard.vue),meta: { requiresAuth: true, roles: [admin, manager] }},{path: /user,name: Use…...

mac下载安装jdk

背景 长时间不折腾mac全部忘记 特此记录 安装 1.下载jdk 根据需要下载对应的jdk 我直接 下载到/Applicatiions目录 https://www.oracle.com/java/technologies/downloads/#java8-mac 2.解压 cd /Applicatiions tar -zxvf jdk-8u431-macosx-x64.tar.gz 3.配置环境 …...

在线PS工具:UI设计的创新选择

对于刚踏入UI设计领域的新手来说&#xff0c;选择合适的在线Photoshop替代工具是至关重要的。市场上存在众多的在线设计工具&#xff0c;让人难以抉择。以下是10个值得尝试的在线PS工具&#xff0c;希望能帮助你找到最适合你的那一款。 Adobe Photoshop Photoshop是设计师们长…...

生成式AI概览与详解

1. 生成式AI概览&#xff1a;什么是大模型&#xff0c;大模型应用场景&#xff08;文生文&#xff0c;多模态&#xff09; 生成式AI&#xff08;Generative AI&#xff09;是指通过机器学习模型生成新的数据或内容的人工智能技术。生成式AI可以生成文本、图像、音频、视频等多种…...

数据结构与算法学习笔记----树与图的深度优先遍历

数据结构与算法学习笔记----树与图的深度优先遍历 author: 明月清了个风 first publish time: 2024.12.9 pa⭐️这里只有一道题哈哈。 Acwing 846.树的重心 给定一棵树&#xff0c;树中包含 n n n个节点&#xff08;编号 1 ∼ n 1 \sim n 1∼n&#xff09;和 n − 1 n - 1 n…...

IEEE T-RO 软体机器人手指状态估计实现两栖触觉传感

摘要&#xff1a;南方科技大学戴建生院士、林间院士、万芳老师、宋超阳老师团队近期在IEEE T-RO上发表了关于软体机器人手指在两栖环境中本体感知方法的论文。 近日&#xff0c;南方科技大学戴建生院士、林间院士、万芳老师、宋超阳老师团队在机器人顶刊IEEE T-RO上以《Propri…...

【NLP 14、激活函数 ② tanh激活函数】

学会钝感力&#xff0c;走向美好的方向 —— 24.12.11 一、tanh激活函数 1. tanh函数的定义 tanh是双曲正切函数&#xff08;Hyperbolic Tangent&#xff09;&#xff0c;数学表达式为 其函数图像是一个S型曲线&#xff0c;以原点 (0&#xff0c;0) 为中心对称&#xff0c;定…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...