数据结构-哈夫曼树

一.什么是哈夫曼树

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

二.哈夫曼树的定义

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

每个叶子节点到根节点的距离乘权值,再全都加起来就得到了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.xdnf.cn/news/10653.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

双11精选网络安全书单:打造数字世界的钢铁长城!

&#x1f91f; 基于入门网络安全/黑客打造的&#xff1a;&#x1f449;黑客&网络安全入门&进阶学习资源包 &#x1f31f;双11火热来袭&#xff0c;网络安全书单推荐&#x1f680; 随着数字化浪潮的汹涌澎湃&#xff0c;网络安全已经成为了每个从业者不可回避的重要议…

WebGUI之Gradio:Gradio 5的简介、安装和使用方法、案例应用之详细攻略

WebGUI之Gradio&#xff1a;Gradio 5的简介、安装和使用方法、案例应用之详细攻略 目录 Gradio 5的简介 1、Gradio的适用场景 2、Gradio 5 的主要改进包括&#xff1a; Gradio 5的安装和使用方法 1、安装和使用方法 2、使用方法 2.1、文本内容 (1)、简单的输入/输出组件…

初始Python篇(5)—— 集合

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; Python 目录 集合 相关概念 集合的创建与删除 集合的操作符 集合的相关操作方法 集合的遍历 集合生成式 列表、元组、字典、集合的…

探索Python的Shell力量:Plumbum库揭秘

文章目录 探索Python的Shell力量&#xff1a;Plumbum库揭秘第一部分&#xff1a;背景介绍第二部分&#xff1a;Plumbum是什么&#xff1f;第三部分&#xff1a;如何安装Plumbum&#xff1f;2. 创建管道3. 重定向4. 工作目录操作5. 前台和后台执行 第五部分&#xff1a;场景应用…

大模型时代,算法岗到底哪个最有前景?什么样的算法工程师更吃香?

毫无疑问&#xff0c;全栈型的算法工程师将更为抢手&#xff0c;如果你精通大模型从训练到应用的整个流程&#xff0c;你走到哪里都不怕。 但往往人的精力有限&#xff0c;如果从数据、预训练、微调、对齐、推理、应用几个方面来看的话&#xff0c;个人觉得 “预训练>数据&…

Linux系统之sleep命令的基本使用

Linux系统之sleep命令的基本使用 一、sleep命令介绍二、sleep的使用帮助2.1 查看帮助信息2.2 基本语法 三、sleep命令的基本使用3.1 指定暂停时间长度3.2 结合多个时间单位 四、在脚本中应用五、注意事项 一、sleep命令介绍 sleep命令是一个在Unix和类Unix操作系统中常见的命令…

《Java核心技术 卷I》Swing处理2D图形

处理2D图形 Java1.0开始&#xff0c;Graphics类就包含绘制直线、矩形和椭圆等方法&#xff0c;但是绘制图形的操作能力有限&#xff0c;我们将使用Java2D的图形库。想绘制需要获得Graphics2D类的一个对象&#xff0c;是Graphics的子类。paintCompoent方法接收一个2D类对象&…

MySQL:客户端工具创建数据库

MySQL 是一个开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;用于存储、管理和检索数据。MySQL是基于SQL语言的&#xff0c;它具有高效、可靠、易用的特点。 客户端工具 这个mysqld.exe就在计算机安装的数据可服务&#xff0c;启动之后&#xff0c;mys…

【Python】计算机视觉应用:OpenCV库图像处理入门

计算机视觉应用&#xff1a;OpenCV库图像处理入门 在当今的数字化时代&#xff0c;计算机视觉&#xff08;Computer Vision&#xff09;已经渗透到各行各业&#xff0c;比如自动驾驶、智能监控、医疗影像分析等。而 Python 的 OpenCV 库&#xff08;Open Source Computer Visi…

万字长文详解JavaScript基础语法--前端--前端样式--JavaWeb

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 今天毛毛张带来的前端教程的第三期&#xff1a;JavaScript 文章目录 4.JavaScript4.1 JS简介4.1.1 JS起源4.1.2 JS 组成部分4.1.3 JS的引入方式 4.2 JS的数据类型和运…

医学图像算法之基于Unet的视网膜血管分割

第一步&#xff1a;准备数据 视网膜血管分割数据比较少&#xff0c;但效果好&#xff0c;总共40张 第二步&#xff1a;搭建模型 UNet主要贡献是在U型结构上&#xff0c;该结构可以使它使用更少的训练图片的同时&#xff0c;且分割的准确度也不会差&#xff0c;UNet的网络结构…

深度剖析JUC中LongAdder类源码

文章目录 1.诞生背景2.LongAdder核心思想3.底层实现&#xff1a;4.额外补充 1.诞生背景 LongAdder是JDK8新增的一个原子操作类&#xff0c;和AtomicLong扮演者同样的角色&#xff0c;由于采用AtomicLong 保证多线程数据同步&#xff0c;高并发场景下会导致大量线程同时竞争更新…

Python(PySimpleGUI 库)

PySimpleGUI 是一个用于简化 GUI 编程的 Python 包&#xff0c;它封装了多种底层 GUI 框架&#xff08;如 tkinter、Qt、WxPython 等&#xff09;&#xff0c;提供了简单易用的 API。PySimpleGUI 包含了大量的控件&#xff08;也称为小部件或组件&#xff09;&#xff0c;这些控…

LangChain学习心得总结

大模型开发遇到的问题及langchain框架学习 背景&#xff1a; 1、微场景间跳转问题&#xff0c;无法实现微场景随意穿插 2、大模型幻读&#xff08;推荐不存在的产品、自己发挥&#xff09; 3、知识库检索&#xff0c;语义匹配效果较差&#xff0c;匹配出的结果和客户表述的…

Linux基础(十二)——文件与文件系统的压缩、打包和备份

文件与文件系统的压缩、打包和备份 1.压缩1.1 压缩方法及其后缀1.2 gzip1.3 bzip21.4 xz 2.打包3.XFS文件系统备份与还原4.镜像文件创建&#xff08;mkisofs&#xff09; 1.压缩 1.1 压缩方法及其后缀 我们知道在 Linux 下面的扩展名是没有什么很特殊的意义的&#xff0c; 不…

简简单单的UDP

前言 上一篇了解了TCP的三次握手过程&#xff0c;目的、以及如何保证可靠性、序列号与ACK的作用&#xff0c;最后离开的时候四次挥手的内容&#xff0c;这还只是TCP内容中的冰山一角&#xff0c;是不是觉得TCP这个协议非常复杂&#xff0c;这一篇我们来了解下传输层另外一个协…

MLMs之OmniGen:OmniGen(统一图像生成模型)的简介、安装和使用方法、案例应用之详细攻略

MLMs之OmniGen&#xff1a;OmniGen(统一图像生成模型)的简介、安装和使用方法、案例应用之详细攻略 导读&#xff1a;这篇论文介绍了OmniGen&#xff0c;一个用于统一图像生成的扩散模型。论文的核心要点可以总结如下&#xff1a; >> 背景痛点&#xff1a; ● 图像生成领…

LeetCode 143.重排链表

题目&#xff1a; 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为&#xff1a; L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值&#xff0c;而是需要实际…

Linux进程信号(信号的产生)

目录 什么是信号&#xff1f; 信号的产生 信号产生方式1&#xff1a;键盘 前台进程 后台进程 查看信号 signal系统调用 案例 理解进程记录信号 软件层面 硬件层面 信号产生方式2:指令 信号产生方式3:系统调用 kill系统调用 案例 其他产生信号的函数调用 1.rais…

【C++】STL— stack的常见用法和模拟实现

目录 1、stack的介绍 2、stack的使用 构造一个空栈 stack的简单接口应用 3、stack的模拟实现 4、栈的相关题目 4.1 最小栈 4.1.2思路 4.1.3 实现代码 4.2 栈的压入、弹出序列 4.2.2 思路 4.2.3程序实现 1、stack的介绍 在C中&#xff0c;stack是一种标准模板库&am…