数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树

简介: 本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。

树与二叉树的应用

文章目录:

1.哈夫曼树与哈夫曼曼编码

引入1.1:在学习哈夫曼树和哈夫曼编码之前预备知识

1.1 带权路径长度

结点的权:理解为权重,重要性。
结点的带权路径长度:树根到该结点的路径长度(经过的边数✖️该结点的权值)
树的带权路径长度(WPL):树中所有叶结点的带权路径长度之和。

image.png

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

1.2 哈夫曼树

1.2.1 哈夫曼树的构造

构造步骤:
:one: 找到当前权值最小的两个结点(包括两个结点构造出的新结点)
:two: 将这两个结点通过一个构造出的父结点联系起来,父结点的权值是他俩权值之和。
:three:重复上面的步骤,直到没有结点可以添加

哈夫曼树特点:

  • 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
  • 哈夫曼树的结点总数为2n-1
  • 哈夫曼树中不存在度为1的结点
  • 哈夫曼树并不唯一,但WPL必然相同且为最优。
    image.png

引入1.3 :哈夫曼树的应用->哈夫曼编码,简单理解成,把英文字母用最少的比特表达出来。常用的字母,访问的频率高,权值就高,尽可能的放在树层次低的位置,好进行查找。而构造哈夫曼树,就是用编码的字母配上上他们的权值,构造出一个哈夫曼树,然后做分支算0,右分支算1,将字母编码,不重不漏,且最优,访问时间最快。

1.3 哈夫曼编码

固定长度编码:每个字符用相等长度的二进制位表示
可变长度编码:允许对不同字符用不等长长的二进制位表示
前缀编码:若没有
一个编码是另一个编码的前缀,则称这样的编码为前缀编码。

特点:哈夫曼树不唯一,哈夫曼编码也不唯一,但是WPL是一样的

2.并查集

2.1 并查集的三要素

2.1.1 并查集的逻辑结构

并查集划分不同的集合。
将各种元素划分为若干互不相交的子集。

让这些子集组成一颗树,指向一个子集的根结点

根据逻辑结构描述基本操作:
查:如查找两个结点,是否属于一个集合,两个结点分别查到对应集合树的根结点,并比较根结点是否相同
并:将一个子树的根结点,放到另一根子树根结点的下面,做它的孩子

2.1.2 并查集的存储结构

image.png

解释说明:

  • 存储结构是静态数组,数组下标代表元素是哪个,数组中存储的值,代表它的父结点的下标是哪个,如果是-1,代表没有父结点,即就是根结点
  • 注意,这个树的箭头,是由孩子指向双亲的

集合的两个操作:
查操作:从一个结点出发,一步一步找到根结点
并操作:将一个结点的存储值,改成合并的结点的下标。

2.2 并查集的优化

2.2.1 初步优化(并操作优化)

引入思考:

我们希望并查集的树是越宽越好,因为越深我们查找起来越慢,所以说,在并操作这个步骤,有可以改进的地方。我们应该确定两颗树,到底谁应该是谁的孩子,我们的核心目的是让更多的结点在树中的位置离根结点更近,所以,通过结点的个数确定两颗树的关系,结点少的做结点多的孩子,即小树合并到大树

存储结构的改变:

  • 根结点存储的值不再是-1,而是根据他所构成的树所有的结点数确定这个值,如他有6个结点,根结点值就是-6,这样方便两个树比较结点数。
  • 然后合并之后,把大树的值改成他俩原先的存储值之和,小树根存储值改为大树下标

    2.2.2 终极优化(查操作优化即压缩存储)

    引入思考:

    我们希望并查集的树越宽越好,我们当然可以把某一段树放到根结点下面,降低他的深度,这个操作,我们在每次查找的过程中实现,即查找某一个点的根结点,然后再他包括他经过的所有结点放到根结点下方。

  • 在这个过程中,修改途径结点的存储值,一步到位直接存储根结点的下标。

3.二叉排序树

3.1 二叉排序树的定义

二叉排序树,又称二叉查找树(BST)
一颗二叉树或者空二叉树,或者具有如下性质的二叉树:

  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一颗二叉排序树

3.2 二叉排序树的查找

从根结点出发,比根结点小走左子树,比根结点大走右子树,每次对比根结点,数值相等则查找成功,找到空子树则查找失败

3.3 二叉排序树的插入

若原二叉排序树为空,则直接插入结点,否则根据关键字先找插入位置,再进行插入操作,小的插在左边,大的插到右边

3.4 二叉排序树的构造

多次使用二叉排序树插入操作

注意:

  • 不同的关键字可能得到同款二叉排序树
  • 也可能得到不同款二叉排序树

3.5 二叉排序树的删除(重点)

二叉排序树根据删除结点的情况可分为三种情况:

先搜索找到目标结点:
:one:若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。
:two:若被删除的结点只有左子树或右子树,直接让它的那个子树代替它的位置即可
:three:被删除的结点既有左子树又有右子树

  • 从左子树找到最大的结点,代替它的位置(即左子树最右下的结点)
  • 从右子树找到最小的结点,代替它的位置(即右子树最左下的结点)

image.png

3.6 查找效率分析(ASL)

查找长度:在查找运算中,需要对比关键字的次数称为查找长度,反映了查找操作时间的复杂度。

具体实例求查找成功的平均查找长度ASL
image.png

查找成功:
(查询次数✖️同等查询次数结点数)➗结点总数
ASL=(1*1+2*2+3*4+4*1)/8=2.625

具体实例求查找失败的平均查找长度ASL
image.png

查找失败
(判断出是空子树需要的查找次数这种情况的数量)/情况数
ASL=(3\
7+4*2)/9=3.22

总结:
查找效率分析
最好情况:
n个结点的二叉树最小高度为⌊log~2~n⌋+1,平均查找长度=O(log~2~n)
最坏情况:
每个结点只有一个分支,树高h=结点n。平均查找长度O(n)

4.平衡二叉树

4.1 平衡二叉树的定义

平衡二叉树:简称AVL树,树上任一结点的左子树和右子树的高度之差不超过1

4.2 插入操作

在二叉排序树的插入操作中,不难得知,插入一个结点后,平衡二叉树可能就不平衡了,所以在每次插入完之后,我们就需要检查平衡二叉树,找出最小不平衡子树,然后调整最小不平衡子树。

4.3 插入新结点如何调整不平衡问题

根据插入位置不同,分为四种类型

  • LL(插入在左孩子的左子树)
  • RR(插入在右孩子的右子树)
  • LR(插入在左孩子的右子树)
  • RL(插入在右孩子的左子树)

    为什么假定所有子树的高度都是H

如何调整最小不平衡子树?
记法:孩子反向旋转,左旋右旋指的是往上旋转
LL:左孩子右旋成为根结点,多出来的右子树,移动到原先根结点的左子树
RR:右孩子左旋成为根结点,多出来的左子树,移动到原先根结点的右子树
LR:右子树先左旋,再右旋
RL:左子树先右旋,再左旋

4.4 查找效率分析

我们以n~h~表示深度为h的平衡树中含有的最少结点数
不难推出:
n~0~=0
n~1~=1
n~2~=2
n~3~=4
总结归纳出,n~h~=n~h-1~+n~h-2~+1
可以证明n个结点的平衡二叉树的最大深度是O(log~2~n),平衡二叉树的平均查找长度为O(log~2~n)

4.5 删除操作

:one:删除结点
若删除的结点是叶子,直接删
若删除的结点只有一个子树,用子树顶替删除位置
若删除的结点有两颗子树,用前驱(或后继结点)顶替,并转换为对前驱或后继结点的删除

:two: 一路向上找到最小不平衡子树,若无则直接结束
:three:找最小不平衡子树下,"个头"最高的儿子和孙子
:four:根据孙子的位置,调整平衡(LL/RR/LR/RL)

:five: 如果不平衡向上传导,继续:two:

image.png

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
23天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
38 1
|
28天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
13天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
62 8
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
43 4
|
17天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
46 3
|
22天前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
49 7
|
1月前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
27 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
16天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
36 0