408数据结构-哈夫曼树 自学知识点整理

2024-05-13 18:44

本文主要是介绍408数据结构-哈夫曼树 自学知识点整理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前置知识:二叉树的概念、性质与存储结构


哈夫曼树

哈夫曼树的定义

首先需要明确几个概念。
路径:从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度:路径上的分支数目称为路径长度
(值):树中结点被赋予的表现或具有某种现实含义的值,这个值称为该结点的。(就是一般存放在 T − > d a t a T->data T>data里的那玩意)
结点的带权路径长度:从树的根到一个结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度
例如,对下图中的树,结点 I I I的带权路径长度为 3 × 3 = 9 3×3=9 3×3=9
在这里插入图片描述
树的带权路径长度:树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为
W P L = ∑ i = 1 ∞ w i l i WPL=\sum\limits_{i=1}^{\infty }{{{w}_{i}}{{l}_{i}}} WPL=i=1wili
式中, w i w_i wi是第 i i i个叶结点所带的权值, l i l_i li是该叶结点到根结点的路径长度。对上图中的树,其带权路径长度为 3 × ( 5 + 1 + 10 + 3 ) = 57 3×(5+1+10+3)=57 3×(5+1+10+3)=57

哈夫曼树:在含有 n n n个带权叶结点的二叉树中,其中带权路径长度( W P L WPL WPL)最小的二叉树称为哈夫曼树,也称最优二叉树

哈夫曼树的构造

给定 n n n个权值分别为 w 1 , w 2 , ⋯ , w n {{w}_{1}},{{w}_{2}},\cdots ,{{w}_{n}} w1,w2,,wn的结点,构造哈夫曼树的算法描述如下:

  1. 将这 n n n个结点分别作为 n n n棵仅含一个结点的二叉树,构成森林 F F F
  2. 构造一个新结点,从 F F F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左右子树上根结点的权值之和。
  3. F F F中删除刚才选出的两棵树,同时将新得到的树加入 F F F中。
  4. 重复步骤 2 2 2和步骤 3 3 3,直至 F F F中只剩下一棵树为止。

简而言之,就是把所有结点看成只有根节点的二叉树,然后每次从这一坨二叉树里选两个根结点权值最小的作为兄弟结点(无顺序),构成一棵新的二叉树,新二叉树的根结点权值为这两个结点权值的和。一直重复下去直到只剩最后一棵树,就是哈夫曼树,且不唯一。

哈夫曼树的性质

从构造过程中,可以看出哈夫曼树具有如下特点:

  1. 每个初始结点最终都将成为叶结点,且权值越小的结点到根结点的路径长度越大。
  2. 构造过程中共新建了 n − 1 n-1 n1个新结点(且均为双分支结点),因此哈夫曼树的结点总数为 2 n − 1 2n-1 2n1
  3. 每次构造都选择 2 2 2棵树作为新结点的孩子,因此哈夫曼树必是二叉树,且其中不存在度为 1 1 1的结点。

(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025

哈夫曼编码

在数据通信中,若对每个字符用相等长度的二进制位表示,则称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示,则称这种编码方式为可变长度编码。可变长度编码要比固定长度编码好得多,其特点是对频率高的字符赋以短编码,而对频率较低的字符则赋以较长一些的编码,从而可以使字符的平均编码长度减短,起到压缩数据的效果。

若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码
由哈夫曼树得到哈夫曼编码,只需将字符中的每个字符作为一个结点,各个字符出现的频度(或次数)作为结点的权值,构造出对应的哈夫曼树。然后,从根到叶结点的路径上分支标记的字符串作为该字符的编码,这样就得到了哈夫曼编码。因为哈夫曼树是不唯一的,所以哈夫曼编码同样也不唯一。
哈夫曼编码常应用在数据压缩中。


在408考研初试中,常考对于一个给定的字符集,如何设计一个哈夫曼编码,其实就是构造一棵哈夫曼树。这一块知识对编写代码不作要求,只需掌握手推即可。
以上。

这篇关于408数据结构-哈夫曼树 自学知识点整理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/986522

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Mysql中深分页的五种常用方法整理

《Mysql中深分页的五种常用方法整理》在数据量非常大的情况下,深分页查询则变得很常见,这篇文章为大家整理了5个常用的方法,文中的示例代码讲解详细,大家可以根据自己的需求进行选择... 目录方案一:延迟关联 (Deferred Join)方案二:有序唯一键分页 (Cursor-based Paginatio

Mysql中InnoDB与MyISAM索引差异详解(最新整理)

《Mysql中InnoDB与MyISAM索引差异详解(最新整理)》InnoDB和MyISAM在索引实现和特性上有差异,包括聚集索引、非聚集索引、事务支持、并发控制、覆盖索引、主键约束、外键支持和物理存... 目录1. 索引类型与数据存储方式InnoDBMyISAM2. 事务与并发控制InnoDBMyISAM

StarRocks索引详解(最新整理)

《StarRocks索引详解(最新整理)》StarRocks支持多种索引类型,包括主键索引、前缀索引、Bitmap索引和Bloomfilter索引,这些索引类型适用于不同场景,如唯一性约束、减少索引空... 目录1. 主键索引(Primary Key Index)2. 前缀索引(Prefix Index /

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)