【数据结构】二叉树-堆（上）

个人主页~

---

一、树的概念及结构

在我们学习二叉树之前，我们先要了解一下树的概念，二叉树就是一种树

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; // 结点中的数据域
};
1
2
3
4
5
6
7
8

左孩子右兄弟法就是一个指针指向左边第一个孩子，右指针指向右边第一个兄弟

图画的不太好看，将就一下
红色的线是左孩子
蓝色的线是右兄弟
这样我们可以简洁并且快速地找到这棵树所有的分支

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、二叉树的顺序结构以及实现

1、二叉树的顺序结构

现实中我们经常把堆（一种二叉树）使用顺序结构的数组来存储，这里的堆与malloc位置的堆的概念是不同的，malloc位置的堆是操作系统中的内存管理，这里的堆是我们人为实现的一种数据结构

2、堆的概念及结构

把一堆数据按照完全二叉树的顺序存储方式存储在一个一维数组中，并且满足第i项 ≤ 第2i+2项，i为自然数，则称为堆，根节点最大的堆叫大堆（大根堆），根节点最小的堆叫小堆（小根堆）

性质：
①堆总是一颗完全二叉树
②堆中某个节点的值总是不大于或不小于其父节点的值

（1）小根堆

逻辑结构：

物理结构（存储结构）：

（2）大根堆

逻辑结构：

物理结构（存储结构）：

这里的存储结构中的数据不一定是有序的，也可以不是升序或者降序，但是大堆的父节点一定比子节点大，小堆的父节点一定比子节点小

3、堆的实现

（1）堆的向上调整算法–堆的创建

①一般方法

我们在使用堆的向下调整算法之前要保证左右子树都要是堆，那么在使用之前我们先要创建堆

我们创建一个数组，在逻辑上可以看做一颗完全二叉树，然后我们通过算法把它构建成为一个堆，从倒数第一个叶子节点开始调整一直到根节点，就可以调整成堆

int arr[] = {1,4,7,2,5,9};
1

最后的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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

从二叉树的根节点的左孩子开始调整，按照下标依次调整，最终会建成一个堆
图演示：

下标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;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（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)

---

今日分享就到这~