【数据结构】二叉树-堆（上）
一、树的概念及结构
在我们学习二叉树之前，我们先要了解一下树的概念，二叉树就是一种树
1、概念
树是一种非线性的数据结构，它是由n个有限节点组成一个具有层次关系的集合，因为根据它所画出的抽象图看起来像一棵倒挂着的树，它的根朝上，树叶朝下
一棵树最顶上的节点叫做根节点，一棵树有且只有一个根节点，根节点没有前驱节点也就是说根节点上面就没有节点了
除了根节点以外，其余节点被分成N个互不相交的集合，我们形象的来说，就是一棵树的叶子和树枝是多对一的概念，也就是说一个树枝可以有多个叶子或者没有叶子，但是一个叶子只能长在一个树枝上，一条小树枝只能长在一条大树枝上，所以树是递归定义的
2、相关概念
节点的度：一个节点含有子树的个数（A的度是3，C的度是0）
叶节点（终端节点）：度为0的节点称为叶节点（GHIJKL）
分支节点（非终端节点）：度不为0的节点（ABDF）
子节点：一个节点含有的子树的根结点（B是A的子节点）
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点（A是B的父节点）
兄弟节点：这里的兄弟指的是亲兄弟，也就是具有相同父节点的节点（BCD是兄弟节点）
树的度：整棵树的度是这棵树中的节点的度中最大的那个度（这棵树最大是3）
节点的层次：根为第一层，根的子节点为第二层，子节点的子节点为第 三层，以此类推（第一层：A；第二层：BCD；第三层：FGHI；第四层：JKL）
树的高度（深度）：树中节点的最大层次（四层）
堂兄弟节点：父亲为同一层的节点（HI）
节点的祖先：从根到该节点所经分支上的所有节点（J节点的祖先是ABF）
子孙：以某节点为根的子树中任意节点都称为该节点的子孙（B-L都是A的子孙）
森林：由N棵（N>0）互不相交的树组成的集合称为森林
树的概念都是由人类的亲缘关系决定的，我们在记忆的时候可以结合我们人类的亲缘关系来记忆
3、树的表示
树的表示方法有很多种，如果我们再像以前一样定义一个结构体，其中存放指针和数据，那样就不行了，因为我们不知道一个节点有多少子树，这样就没办法定义树的节点的结构体，这里，我们有一个最好的办法就是左孩子右兄弟法
左孩子右兄弟法：
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点，也就是最左边的孩子
struct Node* _pNextBrother;
// 指向其下一个兄弟结点，就是右边第一个兄弟
DataType _data; // 结点中的数据域
};左孩子右兄弟法就是一个指针指向左边第一个孩子，右指针指向右边第一个兄弟
图画的不太好看，将就一下 红色的线是左孩子 蓝色的线是右兄弟 这样我们可以简洁并且快速地找到这棵树所有的分支
4、树的实际应用
文件系统的目录就是树的应用
E盘：
这里就是树的应用，文件系统的目录是用树的结构实现的
二、二叉树的概念和结构
1、概念
二叉树就是在树的基础上加上特殊 二叉树是由一个根节点加上一个左子树和一个右子树组成的 二叉树不存在度大于2的节点 二叉树是有序树，因为它的子树有左右之分，次序不能颠倒
2、特殊二叉树
（1）满二叉树 一个二叉树，如果每一个层的节点数都达到最大值，那么这个二叉树就是满二叉树
（2）完全二叉树 完全二叉树是效率很高的二叉树，它的最后一层可以不满，最后一层之前的层都是满的，然后最后一层的节点是需要按序排列的，满二叉树是一种特殊的完全二叉树
3、二叉树的性质
若规定根节点的层数为1，具有n个节点的满二叉树的深度h=log₂（n+1）
对于具有n个节点的完全二叉树，如果按照从上到下，从左到右的数组顺序对所有节点从0开始编号则对于序号为i的节点有如下几个性质： ①若i>0，i位置节点的父亲序号：（i-1）/2；i=0，i为根节点编号，无父亲节点 ②若2i+1<n，左孩子序号为2i+1并且2i+1≥n，否则无左孩子 ③若2i+2<n，右孩子序号为2i+2并且2i+2≥n，否则无右孩子
4、二叉树的存储结构
二叉树有两种存储结构，一种是顺序存储，另一种是链式存储
（1）顺序存储
顺序存储就是使用数组来存储，一般只适合表示完全二叉树，因为不是完全二叉树会有空间上的浪费，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树
（2）链式存储
链式存储就是使用链表来存储，通常的方法是链表节点由三个域组成，分别是数据域以及左右指针域，左右指针存储左右孩子的地址
链式结构又分为二叉链和三叉链，这里使用的是二叉链
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* Left; // 指向左孩子
struct BinTreeNode* Right; // 指向右孩子
BTDataType data; // 值域
};
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* Parent; // 指向父节点
struct BinTreeNode* Left; // 指向左孩子
struct BinTreeNode* Right; // 指向右孩子
BTDataType data; // 值域
};三、二叉树的顺序结构以及实现
1、二叉树的顺序结构
现实中我们经常把堆（一种二叉树）使用顺序结构的数组来存储，这里的堆与malloc位置的堆的概念是不同的，malloc位置的堆是操作系统中的内存管理，这里的堆是我们人为实现的一种数据结构
2、堆的概念及结构
把一堆数据按照完全二叉树的顺序存储方式存储在一个一维数组中，并且满足第i项 ≤ 第2i+2项，i为自然数，则称为堆，根节点最大的堆叫大堆（大根堆），根节点最小的堆叫小堆（小根堆）
性质： ①堆总是一颗完全二叉树 ②堆中某个节点的值总是不大于或不小于其父节点的值
（1）小根堆
逻辑结构：
物理结构（存储结构）：
（2）大根堆
逻辑结构：
物理结构（存储结构）：
这里的存储结构中的数据不一定是有序的，也可以不是升序或者降序，但是大堆的父节点一定比子节点大，小堆的父节点一定比子节点小
3、堆的实现
（1）堆的向上调整算法–堆的创建
①一般方法
我们在使用堆的向下调整算法之前要保证左右子树都要是堆，那么在使用之前我们先要创建堆
我们创建一个数组，在逻辑上可以看做一颗完全二叉树，然后我们通过算法把它构建成为一个堆，从倒数第一个叶子节点开始调整一直到根节点，就可以调整成堆
int arr[] = {1,4,7,2,5,9};
最后的9与它的父节点7交换：
1<9再交换
然后再检查最后一个叶子节点，重复上面的步骤，虽然这样最终可以建立一个堆，但这样效率特别低，所以我们有了向上调整算法来建堆
②向上调整建堆
现在我们有一个数组，在逻辑上看成一棵完全二叉树，我们要创建一个堆，可以用向上调整算法
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;//因为除法向下取整，所以右孩子也能
//因为是一颗完全二叉树，所以父节点总是可以通过子节点减1除以二找到
//while (parent >= 0)
while (child > 0)//这里用子节点作为循环条件，因为child可能调整到根节点上
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}//大于就交换，把此时的父节点变成子节点，父节点的父节点变成父节点，比较上一层的关系
else
{
break;
}
}
}从二叉树的根节点的左孩子开始调整，按照下标依次调整，最终会建成一个堆 图演示：
下标1向上调整：
下标2向上调整：
下标3调整两次：（第二次小于7，不调）
下标4调整两次：（第二次小于7，不调）
下标5调整两次： 第一次：
第二次：
这样就建成一个堆了
（2）向上调整算法的时间复杂度
设树的高度为h 第1层：2^0个节点，需要向上移动0层 第2层：2^1个节点，需要向上移动1层 第3层：2^2个节点，需要向上移动2层 …… 第h-1层：2^(h-2)个节点，需要向上移动h-2层 第h层：2^(h-1)个节点，需要向上移动h-1层 将它们相加
解得原式=2+2^h*(h-2)
遍历一遍为N = 2^h
去掉不重要的项，得时间复杂度O(N*log₂N)
（3）向下调整算法维护堆
当我们需要将堆顶的数据删除掉，那么这个堆就没有了根，如果再重新进行建堆会浪费很多的时间，这里有一种方法的时间复杂度小于重新建堆，这种算法就是向下调整算法
void AdjustDown(int* a, int n, int parent)//n是数组a的数据个数
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
// 选出左右孩子中大的那个
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}//谁大谁是爹
else
{
break;
}
}
}（4）向下调整算法的时间复杂度
设树的高度为h 第1层：2^0个节点，需要向下移动h-1层 第2层：2^1个节点，需要向下移动h-2层 第3层：2^2个节点，需要向下移动h-3层 …… 第h-1层：2^(h-2)个节点，需要向下移动1层 第h层：2^(h-1)个节点，需要向下移动0层 将它们相加之后由错位相减法得 2^h-1-h 因为N = 2^h，所以原式=N-1-log₂N
因为当h趋于无穷大时，N远大于log₂N，所以时间复杂度O(N)
今日分享就到这~
腾讯云开发者
