【c数据结构】二叉树深层解析 (模拟实现+OJ题目）

前言

一、树

1.树的概念与结构

2.树的专业用语

1.根节点

2.边

3.父节点/双亲节点

4.子节点/孩子节点

5.节点的度

6.树的度

7.叶子节点/终端节点

8.分支节点/非终端节点

9.兄弟节点

10.节点的层次

11.树的高度/深度

12.节点的祖先

13.子孙

14.路径

15.森林

3. 树型结构的实际应用场景

二、二叉树

1. 满二叉树

概念：

性质：

4. 完全二叉树

5. 二叉树的存储形式

5.1 顺序存储结构

5.2 链式存储结构

三. 二叉树的顺序结构——堆

1. 堆的结构

2. 堆的性质

3. 堆的逻辑推理公式

4. 堆的模拟实现

4.1 定义堆的结构

4.2 方法的声明

4.3 方法的实现

4.3.1 初始化

4.3.2 销毁

4.3.3 判空

4.3.4 辅助函数交换两数据

4.3.5 插入

4.3.6 删除

4.3.7 取堆顶数据

前言

在编程的世界里，堆无疑是一个不可忽视的存在。在深入了解堆之前，让我们先回溯到其根源——树，这个在计算机科学中同样占据核心地位的数据结构。

声明一下！！紫色的字是作者本人的个人粗暴理解

一、树

1.树的概念与结构

与线性表不同，树是一种非线性的数据结构，它是由n（n>=0）个节点所构成的有层次关系的数据结构。它的层次关系看起来就像是一棵倒挂的树：

其实咱可以把下面看成一个家族族谱，上面的结点生了一堆孩子，从祖先开始，代代传承

注意：树形结构当中，子树之间不能有相交的情况，否则就不是树。

如图，以下结构都不是树型结构：

毕竟，家族里可不能乱伦~

2.树的专业用语

以下图示例

1.根节点

就像树根一样，树中所有节点都是从一个节点A发出的，这样的A节点叫做根节点。

（一棵树只有一个根节点）

2.边

连接两个节点的线叫做树的边

（一棵有N个节点的树具有N-1条边）

3.父节点/双亲节点

可以理解为一个结点连接的上面的节点(简单点说，就是爸爸)。

如图所示，B,C,D,E的父节点都是A。

（除根节点之外，所有节点有且仅有一个父节点）

4.子节点/孩子节点

与父节点相反，你是我的父节点（你是我爸），那么我就是你的子节点（我是你儿~）。

对于节点A，则B,C,D,E都是它的子节点。

5.节点的度

一个节点有多少个子节点，那么它的度就是多少（你生了几个孩子）。

例如：节点A的度为4（A这家伙nb生了4个儿，养殖场猪都没你能生），节点B的度为3，节点C的度为0。

6.树的度

所有节点的度的最大值叫做树的度（就是生孩子最多那位就是家族的生产队代表）。

如图，这颗树的度就是4。

7.叶子节点/终端节点

度为0的节点称之为叶子节点/终端节点（就是丁克）。

如图，这颗树中的叶子节点为：F,G,H,C,L,M,J,K。

8.分支节点/非终端节点

度不为0的节点称之为分支节点/非终端节点（非丁克~）。

除了叶子节点外，其他节点都是分支节点。

9.兄弟节点

具有相同父节点的节点互称为兄弟节点（都是同一个爸爸生的）。

例如，B,C,D,E是兄弟节点，F,G,H是兄弟节点。

10.节点的层次

由根节点开始，根节点为第一层；

它的所有子节点为第二层；

子节点的子节点为第三层；

以此类推。（家里的第几代）

11.树的高度/深度

节点的最大层次（就是家族传了几代人了）。

如图，这颗树的高度为4。

12.节点的祖先

一个节点，从根节点开始到该节点所经的所有节点（除该节点本身）（就是你的所有长辈）。

例如：A,B是G的祖先，A,D,I是L的祖先。

13.子孙

与祖先相反，你是我的祖先，我就是你的子孙。

例如，F,G,H是B的子孙；所有除A外的节点都是A的子孙。

14.路径

从任意节点开始，沿着边到达任意其他节点所经过的节点构成的序列。（你是咋被生下来的）

例如：A到L的路径为：A-D-I-L。

15.森林

由m（m>0）棵互不相交的树（不同树之间没有相交节点）所构成的集合（不同的家族就是不同的森林）。

如图，如果将根节点A删除，剩下的子树组成的部分就是森林。

3. 树型结构的实际应用场景

树型结构在计算机中是被广泛使用的。例如：操作系统中文件根目录与子目录之间的关系、数据库的索引、编译器中的语法树、网络路由协议的构成等。在这些实例中，树形结构对文件的访问、程序的运行效率有很大的帮助。

二、二叉树

在树形结构当中，最常用的一种数据结构就是二叉树。

所谓二叉树，指的是每一个节点的度不超过2的树（即二胎政策的家族）。

一棵二叉树可以分为根节点、左子树、右子树，对于每一棵子树，也可以这样细分，直到其子树不存在为止。

这里要注意：左右子树的次序不能颠倒。

1. 满二叉树

满二叉树是一种特殊的二叉树。

概念：

一个二叉树每一层的节点数都达到最大值（ $2^{i-1}$ ）（即每代都是二胎）

如图所示，这是一棵高度为3的满二叉树：

性质：

（如下前提是根结点层数为1，且非空）

第 $i$ 层最多有 $2^{i-1}$ 个节点。（求每层结点个数）
高度为 $h$ ，最大节点总个数n是 $2^{h}-1$ 。（求树的所有结点的总个数）
反过来，有 $n$ 个节点，高度 $h=log_{2}(n+1)$ 。（求树的总层数）
对于任何一颗非空二叉树，设其度为2的节点个数为 $a$ ，度为1的节点个数为 $b$ ，叶子节点个数为 $c$ ，边数为 $m$ ，则有 $2a+b=m$ 、 $a+b+c-1=m$ 、 $a=c-1$ 。

4. 完全二叉树

完全二叉树也是一种特殊的二叉树。通俗的讲，一个完全二叉树需要满足两个条件：

对于一棵高度为N的二叉树，第1层到第N-1层的节点数均达到最大值。（到最后一层的上一层都必须是满二叉树的状态）
最后一层的节点必须是从左到右连续排列的状态。（二胎→左子树→右子树→无后代子树）

如图，就是一个完全二叉树

由于 **满二叉树** **满足完全二叉树的条件，所以它是一种特殊的完全二叉树**。

5. 二叉树的存储形式

一般来讲，二叉树的存储形式有两种：顺序存储结构和链式存储结构。

5.1 顺序存储结构

顾名思义，用数组来存储二叉树的数据。

对比两图可以看出，非完全二叉树的顺序存储会 **浪费一定的空间**，所以 **完全二叉树更适合顺序存储**。

通常情况下，我们将采用顺序存储结构存储的完全二叉树叫做堆。

5.2 链式存储结构

与链表相同，链式存储结构是指用节点和指针来表示数据元素之间的逻辑关系。

通常情况下，二叉树的链式存储结构分为二叉链和三叉链。

二叉链的指针域：指向左右子结点的指针（指向孩子）
三叉链的指针域：指向左右子结点的指针＋指向父节点的指针。（双向指针，指向孩子和爸爸)

//二叉链
struct BTreeNode
{
	int data;
	struct BTreeNode* leftchild;//指向左子结点的指针
	struct BTreeNode* rightchild;//指向右子结点的指针
};

//三叉链
struct BTreeNode
{
	int data;
	struct BTreeNode* leftchild;//指向左子结点的指针
	struct BTreeNode* rightchild;//指向右子结点的指针
	struct BTreeNode* parent;//指向父结点的指针
};

三. 二叉树的顺序结构——堆

之前提到，采用顺序存储结构存储的完全二叉树叫做堆。

1. 堆的结构

堆的逻辑结构：完全二叉树
堆的物理结构：顺序存储

2. 堆的性质

堆的分类可分为小根堆和大根堆

（把每个结点存储的数据看成每个家庭成员的存款）

小根堆：根结点数值最小，且每个子结点的数值 >= 其父节点（祖先存款最少，每个儿子的存款都>= 爸爸的存款，典型长江后浪推前浪~）
大根堆：根结点数值最大，且每个子结点的数值 <= 其父节点（祖先存款最多，每个儿子的存款都<= 爸爸的存款，典型一代不如一代~）

综上所述，堆具有以下性质：

1.堆总是一棵完全二叉树。

2.堆中的任意节点（非叶子节点）的值总是小于等于/大于等于其子节点的值。

（要么一代更比一代强，要么一代不如一代）

3. 堆的逻辑推理公式

设堆中总共有n个节点，按照数组下标 $0\sim n-1$ 对应每一个节点

假设一个下标为 $i$ 的结点，怎么通过公式推理得到他的子结点或者父结点呢？

Ⅰ 子结点→父结点： $(i-1)\div 2$

Ⅱ 父结点→子结点：

①推出左孩子 $2i+1$ （防止越界，前提条件：，否则无左孩子）

②推出右孩子 $2i+2$ （防止越界，前提条件：，否则无右孩子）

4. 堆的模拟实现

4.1 定义堆的结构

堆的底层是数组，它的结构定义与顺序表差不多

typedef int HPDataType;
 
//定义堆的结构
typedef struct Heap
{
	HPDataType* arr;//数组起始指针
	int capacity;//堆的空间大小
	int size;//堆中有效数据个数
}HP;

4.2 方法的声明

创建新的头文件 Heap.h 放如下代码

//初始化
void HPInit(HP* php);
 
//销毁
void HPDestroy(HP* php);
 
//判空
bool HPEmpty(HP* php);
 
//辅助函数交换两数据
void Swap(HPDataType* x, HPDataType* y);
 
//堆的向上调整
void AdjustUp(HPDataType* arr, int child);
 
//堆的向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
 
//插入
void HPPush(HP* php, HPDataType n);
 
//删除
void HPPop(HP* php);
 
//取堆顶数据
HPDataType HPTop(HP* php);

4.3 方法的实现

创建 源文件 Heap.c 实现如下代码

4.3.1 初始化

//初始化
void HPInit(HP* php)
{
	assert(php);//防止传空指针
	php->arr = NULL;
	php->capacity = php->size = 0;
}

4.3.2 销毁

//销毁
void HPDestroy(HP* php)
{
	assert(php);//防止传空指针
	if (php->arr)//防止多次释放空间
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->capacity = php->size = 0;
}

4.3.3 判空

当堆中有效数据为0时，堆即为空。

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.3.4 辅助函数交换两数据

这是一个辅助函数，用于之后插入和删除时交换堆中的数据元素。

//辅助函数交换两数据
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y; 
	*y = tmp;
}

4.3.5 插入

一般来说，堆的插入是从数组末尾插入
由于我们是小根堆，父亲存款必须小于儿子，而我们插入的可能是小数据的（新的元素可能会小于其父节点的值，就不满足堆的条件）
此时我们就需要向上调整堆的数据，具体如图

思路：

新插入的数据与它的父结点开始比较，然后child = parent ,parent = parent的parent ，不断向上调整

//插入
void HPPush(HP* php, HPDataType n)
{
	assert(php);
	//要判断空间是否满了
	//满了你插个锤子
	if (php->capacity == php->size)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail！");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = n;
	//此时的size没有自增，表示新元素的下标

	AdjustUp(php->arr, php->size);//向上调整
	++php->size;//调整之后，元素个数+1

}


//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;//先找到父节点的下标
	while (parent > 0)//一直比较到parent没有父亲了（也就是到堆顶祖先了）
	{
		if (arr[child] < arr[parent])//若孩子节点的值小于父节点的值，就需要调整
		{
			Swap(&arr[child], &arr[parent]);
			child = parent; //新的孩子节点跑到了原来父节点的位置
			parent = (child - 1) / 2;//确定新的父节点
		}
		else//不需要调整，退出循环
		{
			break;
		}
	}
}

4.3.6 删除

堆是从堆顶开始删除

但是跟数组不同，第一个元素删除后面顺次往前进一位的话，岂不是有兄弟竟是我爸爸的错位
大咩大咩，所以删除完我们要向下调整

思路：

堆顶和最后一个元素交换数据，然后删最后一个数组下标（此时其数据是原堆顶数据）；

然后新堆顶向下慢慢调整

//删除
void HPPop(HP* php)
{
	//注意断言不能是空数组，空的你删个啥玩意
	assert(php && php->size);

	//交换堆顶和末尾元素
	Swap(&php->arr[php->size - 1], &php->arr[0]);
	php->size--;

	AdjustDown(php->arr, 0, php->size);
}

//堆的向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
	//已知Parent，通过2i + 1或者2i + 2找到parent的左右孩子结点
	int child = parent * 2 + 1;


	while (child < n)//不能让child因为++操作导致越界
	{
		//两个左右孩子中存款少的那个和parent交换，因为爸爸得存款最少嘛
	//所以我们要比较两个孩子哪个存款少
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			//child+1<n是为了防止出现child++越界的情况
			// 你想 这个爸爸只有左孩子，没右孩子你++不就+出数组越界了
			child++;
		}

		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else//无需调整，直接跳出
		{
			break;
		}
	}
}

4.3.7 取堆顶数据

由于堆存放在数组当中，堆顶数据即是数组的首元素，直接返回即可。

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	//注意断言不能是空数组，空的你取个啥玩意
	assert(!HPEmpty(php));
	return php->arr[0];
}

希望对你有帮助