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

前言

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

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

一、树

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];
}

希望对你有帮助