数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】

本文主要是介绍数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
哈夫曼树概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

一、相关概念

二叉树:每个节点最多有2个子树的有序树,两个子树分别称为左子树、右子树。有序的意思是:树有左右之分,不能颠倒

叶子节点:一棵树当中没有子结点的结点称为叶子结点,简称“叶子”

路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和

树的高度:树中结点的最大层次。包含n个结点的二叉树的高度至少为log2 (n+1)

二、哈夫曼树的构造算法

  1. { W 1 , W 2 , W 3 … W n } \{W_1,W_2,W_3 \dots W_n\} {W1,W2,W3Wn}看成n棵树的森林
  2. 在森林中选择两个根节点权值最小的树进行合并,作为一颗新树的左右子树,新树的根节点权值为左右子树的和
  3. 删除之前选择出的子树,把新树加入森林
  4. 重复2-3步骤,直到森林只有一棵树为止,概树就是所求的哈夫曼树

注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。

三、哈夫曼树的构造过程

  1. 8个结点的权值大小如下:
    在这里插入图片描述
  2. 从19,21,2,3,6,7,10,32中选择两个权小结点。选中2,3。同时算出这两个结点的和5。

在这里插入图片描述

  1. 从19,21,6,7,10,32,5中选出两个权小结点。选中5,6。同时计算出它们的和11。

在这里插入图片描述

  1. 从19,21,7,10,32,11中选出两个权小结点。选中7,10。同时计算出它们的和17。
    【这时选出的两个数字都不是已经构造好的二叉树里面的结点,所以要另外开一棵二叉树;或者说,如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。】
    在这里插入图片描述

  2. 从19,21,32,11,17中选出两个权小结点。选中11,17。同时计算出它们的和28。
    在这里插入图片描述

  3. 从19,21,32,28中选出两个权小结点。选中19,21。同时计算出它们的和40。另起一颗二叉树。
    在这里插入图片描述

  4. 从32,28, 40中选出两个权小结点。选中28,32。同时计算出它们的和60。

在这里插入图片描述

  1. 从 40, 60中选出两个权小结点。选中40,60。同时计算出它们的和100。 好了,此时哈夫曼树已经构建好了。
    在这里插入图片描述

可见:

  1. 权重越大,距离根节点越近
  2. 叶子的个数为n,构造哈夫曼树中新增的节点的个数为n-1

四、哈夫曼编码

在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。

例如,需传送的报文为AFTER DATA EAR ARE ART AREA,这里用到的字符集为A,E,R,T,F,D,各字母出现的次数为{8,4,5,3,1,1}。现要求为这些字母设计编码。要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101A,E,R,T,F,D进行编码发送

但是很明显,上述的编码的方式并不是最优的,即整理传送的字节数量并不是最少的。

为了提高数据传送的效率,同时为了保证【前缀编码】,可以使用哈夫曼树生成哈夫曼编码解决问题。【任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码

可用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的出现频率作为字符结点的权值赋予该结点上,显然字使用频率越小权值越小,权值越小叶子就越靠下,于是频率小编码长,频率高编码短,这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度

因此,求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的哈夫曼树的问题。

利用哈夫曼树来设计二进制的前缀编码,

  • 既满足【前缀编码】的条件
  • 又保证报文编码总长最短

下图中label1 .... label6分别表示A,E,R,T,F,D左节点用1表示,右节点用0表示

在这里插入图片描述

这篇关于数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2

如何使用Maven创建web目录结构

《如何使用Maven创建web目录结构》:本文主要介绍如何使用Maven创建web目录结构的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录创建web工程第一步第二步第三步第四步第五步第六步第七步总结创建web工程第一步js通过Maven骨架创pytho

Python循环结构全面解析

《Python循环结构全面解析》循环中的代码会执行特定的次数,或者是执行到特定条件成立时结束循环,或者是针对某一集合中的所有项目都执行一次,这篇文章给大家介绍Python循环结构解析,感兴趣的朋友跟随... 目录for-in循环while循环循环控制语句break语句continue语句else子句嵌套的循

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、