数据结构-哈夫曼树

一.什么是哈夫曼树

不同搜索树的效率是不一样的,根据不同的频率构造效率比较好或者最好的搜索树就是哈夫曼树

二.哈夫曼树的定义

将带权路径的长度降低最低

每个叶子节点到根节点的距离乘权值,再全都加起来就得到了WPL值

第一颗二叉树:从上到下计算 5x1+4x2+3x3+2x4+1x4=34

第二颗二叉树:从上到下计算 1x1+2x2+3x3+4x4+5x4=50

第二颗二叉树:从上到下计算 1x3+2x3+3x2+4x2+5x2=33

哈夫曼树为了构造一个树WPL最小

三.哈夫曼树的构造

构造哈夫曼树的方法从小到大排序,将最小的两个权值并在一起形成新的二叉树,这个二叉树的权值就是并在一起两个权值的和,再把这个根形成的根节点放到序列中重新按照从小到大排序,然后重复上面的操作,直到所有节点都用完

下面的列子权值  (1,2,3,4,5,6)

实现哈夫曼树的代码

把节点权值构造成最小堆,从里面找出两个最小和在一起形成一个新的节点在插入到堆中,也可以用排序的方法但不如堆的效率高.

#include<iostream>
using namespace std;
typedef struct HNode* Heap;
typedef struct TreeNode* HuffmanTree;
typedef HuffmanTree ElementType;
int A[] = { 13,1,45,7,20,4,19,13,40,33,38 };  // 预先定义好一组权值 
int A_length = 11;  // 定义其长度 
struct TreeNode
{int Weight;//权值HuffmanTree Left, Right;//左右孩子
};
struct HNode {ElementType* Data;//存储哈夫曼的数组int Size;//当前堆元素的个数int Capacity;//堆的最大容量
};
HuffmanTree CreateHuffman() {HuffmanTree Huffman = new TreeNode();Huffman->Weight = 0;Huffman->Right = Huffman->Left = NULL;return Huffman;
}
typedef Heap MinHeap;//最小堆
#define MINDATA -1000;
MinHeap CreateHeap(int MaxSize) {//创建容量为MinSize的空的最小堆MinHeap H = new HNode();H->Data = new ElementType[MaxSize + 1];H->Size = 0;H->Capacity = MaxSize;HuffmanTree man = CreateHuffman();man->Weight = MINDATA;H->Data[0] = man;return H;
}bool Insert(MinHeap H, ElementType X) {int i;i = ++H->Size;/*增加树的元素*//*根节点元素大于插入的元素根节点元素从根节点到子节点*/for (; H->Data[i / 2]->Weight > X->Weight; i /= 2)H->Data[i] = H->Data[i / 2];/*根节点下来*/H->Data[i] = X;return true;
}ElementType DeleteMin(MinHeap H) {int Parent, Child;ElementType MinHuffman, X;MinHuffman= H->Data[1];//取出根节点存放的最小值X = H->Data[H->Size--];//取出堆最后一个值并删除/*Parent*2<=H->Size判断左子树是否存在Parent*2>H->Size 表示左字数不存在*/for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {/*向下到左右树最小的地方*/Child = Parent * 2;/*Child!=H->Size判断右子树是否存在,左子树等于Size表明左子树是最后一个元素所以右子树不存在*/if ((Child != H->Size) && (H->Data[Child + 1]->Weight < H->Data[Child]->Weight))Child++;if (H->Data[Child]->Weight >= X->Weight)break;else/*左右儿子中最小的值上来*/H->Data[Parent] = H->Data[Child];}H->Data[Parent] = X;return MinHuffman;
}
void PercDown(MinHeap H, int p) {int Parent, Child;ElementType X;X = H->Data[p];//取出根节点for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {Child = Parent * 2;if ((Child != H->Size) && (H->Data[Child + 1]->Weight < H->Data[Child]->Weight))Child++;if (H->Data[Child]->Weight >= X->Weight)break;elseH->Data[Parent] = H->Data[Child];}H->Data[Parent]->Weight = X->Weight;
}
void BuildHeap(MinHeap H) {/*调整H->Data[]中的元素,使满足小堆的有序性*//*这里假设所有H->Size个元素已经存在H->Data[]中*//*从最后一个节点的父节点开始,到根节点1*/int i;for (i = H->Size / 2; i > 0; i--)PercDown(H, i);
}
void BuildMinHeap(MinHeap H) {HuffmanTree Huff;for (int i = 0; i < A_length; i++) {Huff = CreateHuffman();Huff->Weight = A[i];H->Data[++H->Size] = Huff;}BuildHeap(H);
}
//遍历 
void PreOrderTraversal(HuffmanTree Huff) {if (Huff) {cout << Huff->Weight << " ";PreOrderTraversal(Huff->Left);PreOrderTraversal(Huff->Right);}
}
HuffmanTree Huffman(MinHeap H) {HuffmanTree T;BuildMinHeap(H);int times = H->Size;for (int i = 1; i < times; i++) {T = new TreeNode();T->Left = DeleteMin(H);T->Right = DeleteMin(H);T->Weight = T->Right->Weight + T->Left->Weight;Insert(H, T);}T = DeleteMin(H);return T;
}
int main()
{MinHeap H;HuffmanTree Huff;H = CreateHeap(1000);Huff = Huffman(H);PreOrderTraversal(Huff);return 0;}

四.哈夫曼树的特点

1.特点没有度唯1的节点因为每个节点都是两个权值合并在一起形成的

五.哈夫曼编码

当所有的节点都在叶节点就不可能出现一个字符编码是另一个字符的前缀,当你编码节点出现在另外一个编码节点当中的时候在树的非叶节点上的时候会场出现前缀

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/472903.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

go环境搭建

华子目录 下载vscode安装vscodego编译器下载go编译器安装配置go环境变量vscode安装go插件测试 下载vscode 官方&#xff1a;https://code.visualstudio.com/Download 安装vscode vscod安装成功 go编译器下载 官方&#xff1a;https://golang.google.cn/ 点击下载 go编译器安…

v-html 富文本中图片使用element-ui image-viewer组件实现预览,并且阻止滚动条

效果 导入组件 import ElImageViewer from "element-ui/packages/image/src/image-viewer"; components:{ ElImageViewer },模板使用组件 <el-image-viewerv-if"isShowPics":on-close"closeViewer":url-list"srcList"/>定义两…

【nginx】client timed out和send_timeout的大小设置

websocket连接会断开&#xff0c;抓包检查后发现是中间的代理服务器nginx断开的&#xff0c;同时将后端和浏览器都断开了。将nginx日志调到debug级别后&#xff0c;有下面的断开信息。 [info] 125923#125923: *34 client timed out (110: Connection timed out) while proxyin…

C++初阶——日期类的实现

目录 1、Date.h 2、注意 3、Date.cpp 实现 4、test.cpp 测试用例 日期类的实现是为了巩固C初阶——类和对象(上)(中)的知识点 1、Date.h #pragma once #include <iostream> using namespace std; #include <assert.h>class Date {// 友元函数&#xff0c;C初…

rust高级特征

文章目录 不安全的rust解引用裸指针裸指针与引用和智能指针的区别裸指针使用解引用运算符 *&#xff0c;这需要一个 unsafe 块调用不安全函数或方法在不安全的代码之上构建一个安全的抽象层 使用 extern 函数调用外部代码rust调用C语言函数rust接口被C语言程序调用 访问或修改可…

【Linux系统编程】第四十六弹---线程同步与生产消费模型深度解析

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、Linux线程同步 1.1、同步概念与竞态条件 1.2、条件变量 1.2.1、认识条件变量接口 1.2.2、举例子认识条件变量 1.2.3、…

工作时发现自己手写SQL能力很低,特此再来学习一遍SQL

SQL语法 ①常用的数据库本身的操作 # 显示数据库列表 show databases;# 使用某个数据库 use twbpm_dev;# 创建一个数据库 create database db_test;# 删除一个数据库 drop database if exists db_test;# 显示数据库中所有的表 show tables;# 查看MySQL的版本 select version();…

华为Ensp模拟器配置RIP路由协议

目录 RIP路由详解&#xff1a;另一种视角解读 1. RIP简介&#xff1a;轻松理解基础概念 2. RIP的核心机制&#xff1a;距离向量的魅力 3. RIP的实用与局限 RIP配置实验 实验图 ​编辑 PC的ip配置 RIP配置步骤 测试 结语&#xff1a;RIP的今天与明天 RIP路由详解&…

控制器ThinkPHP6

五、控制器中对数组值的返回 在做接口服务时&#xff0c;很多时候回使用数组作为返回值&#xff0c;那么数组如何返回成 json呢&#xff1f; 在 tp6 中返回json 很简单&#xff0c;直接使用 json 进行返回即可&#xff0c;例如&#xff1a; public function index(){$resarra…

SAFETY LAYERS IN ALIGNED LARGE LANGUAGEMODELS: THE KEY TO LLM SECURITY

目录 概要 背景 大语言模型对齐 对齐大语言模型中的过度拒绝 微调攻击 研究设置 问题定义 对齐的大语言模型 大语言模型的提示模板 安全层的存在和定位 安全层的存在性 1.从余弦相似度说明 2.从向量之间角度差异说明 3.与预训练LLM对比说明 安全层的定位 1.推理…

营销手段的变革:开源 AI 智能名片与 S2B2C 商城小程序在新趋势下的机遇与挑战

摘要&#xff1a;本文探讨了在当今营销环境变化下&#xff0c;企业必须改变传统营销手段的必要性。分析了大环境造就的主流趋势对企业的要求&#xff0c;以及传统营销方式如邮件直投的局限性。着重阐述了移动营销的重要性&#xff0c;并进一步研究开源 AI 智能名片和 S2B2C 商城…

【SpringBoot】公共字段自动填充

问题引入 JavaEE开发的时候&#xff0c;新增字段&#xff0c;修改字段大都会涉及到创建时间(createTime)&#xff0c;更改时间(updateTime)&#xff0c;创建人(craeteUser)&#xff0c;更改人(updateUser)&#xff0c;如果每次都要自己去setter()&#xff0c;会比较麻烦&#…

网络安全练习之 ctfshow_web

文章目录 VIP题目限免&#xff08;即&#xff1a;信息泄露题&#xff09;源码泄露前台JS绕过协议头信息泄露robots后台泄露phps源码泄露源码压缩包泄露版本控制泄露源码(git)版本控制泄露源码2(svn)vim临时文件泄露cookie泄露域名txt记录泄露敏感信息公布内部技术文档泄露编辑器…

Git_2024/11/16

文章目录 前言Git是什么核心概念工作流程常见术语解读Git的优势 Git与SVN对比SVNGit总结 Git配置流程及指令环境配置获取Git仓库本地初始化远程克隆 工作目录、暂存区、版本库文件的两种状态本地仓库操作远程仓库操作Git分支Git标签IntelliJ IDEA使用Git回滚代码 GitHub配置流程…

游戏引擎学习第八天

视频参考: https://www.bilibili.com/video/BV1ouUPYAErK/ 理解下面的代码 关于虚函数 代码分解 结构体 foo 的定义&#xff1a; struct foo {int32 X;int64 Y;virtual void Bar(int c); };foo 结构体有两个成员变量&#xff1a;X&#xff08;int32 类型&#xff09;和 Y&…

蓝桥杯-洛谷刷题-day3(C++)

目录 1.忽略回车的字符串输入 i.getline() ii.逐个字符的识别再输入 2.获取绝对值abs() 3.做题时的误区 4.多个变量的某一个到达判断条件 i.max() 5.[NOIP2016 提高组] 玩具谜题 i.代码 6.逻辑上的圆圈 i.有限个数n的数组 7.数组的定义 i.动态数组 1.忽略回车的字符串输…

不用来回切换,一个界面管理多个微信

你是不是也有多个微信号需要管理&#xff1f; 是不是也觉得频繁切换账号很麻烦&#xff1f; 是不是也想提升多账号管理的效率&#xff1f; 在工作中&#xff0c;好的辅助工具&#xff0c;能让我们的效率加倍增长&#xff01; 今天&#xff0c; 就给大家分享一个多微管理工具…

Word_小问题解决_1

1.第二页是空白的&#xff0c;但是删不掉 将鼠标弄到第二页最开始的地方打开段落设置行距为固定值0.7磅 2.表格中有文字进入了表格中怎么办 打开段落&#xff0c;将缩进改为0即可

LLM - 计算 多模态大语言模型 的参数量(Qwen2-VL、Llama-3.1) 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/143749468 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 影响 (…

GEE下载ERA5-Land气象数据(1950-至今,降水、温度)

GEE下载ERA5-Land气象数据&#xff08;1950-至今&#xff0c;降水、温度&#xff09; ERA5-Land是一个高分辨率的陆地再分析数据集,相比ERA5数据集具有更高的空间分辨率。它是通过重新运行ECMWF ERA5气候再分析系统的陆地分量生成的。 空间分辨率特点&#xff1a; 网格间距…