当前位置: 首页 > 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;定…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...