数据结构——二叉树+堆-EW帮帮网

1.树

1.1树的概念与结构

树是一种非线性的数据结构，它是由 n (n>=0) 个有限节点组成一个具有层次关系的集合。把它叫为树的是因为他看起来像一颗倒挂的树。

有一个特殊的结点，称为根结点，根结点没有前驱结点。
除根结点以外，其余结点被分成 M (M>0) 个互不相交的集合 T1、T2、T3、……、Tn，其中每一个集合 Ti (1 <= i <= n) 又是一颗结构与树类似的子树。每颗子树的根结点有且只有一个前驱，可以有 0个或多个后继。因此，树是递归定义的。

树形结构中，子树之间是不能有交集的，否则就不是树形结构

子树是不相交的
除了根结点外，每个结点有且仅有一个父结点
一颗N个结点的树有N-1条边

1.2 树相关术语

父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
结点的度：一个结点有几个孩子，他的度就是多少；比如A的度为2，E的度为0
树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为2
叶子结点/终端结点：度为0的结点称为叶结点；如上图：E、F都是叶结点
分支结点/非终端结点：度不为0的结点；如上图：A、B、C、D、G都是分支结点
兄弟结点：具有相同父结点的结点胡成为兄弟结点；如上图：B、C是兄弟结点
结点的层次：从根开始定义，跟为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中结点的最大层次；如上图：树的高度为4
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
路径：一条从树中任意结点出发，沿父结点到子结点连接，达到任意节点的序列；比如A到K的路径：A-C-G-K；H到F的路径：H-D-B-A-C-F
子孙：以某节点为根的子树中任一结点都成为该结点的子孙。如上图：所有的结点都是A的子孙
森林：有 m (m>0) 棵互不相交的树的集合成为森林

1.3树的表示

孩子兄弟表示法：

树结构相对线性表就比较复杂，存储起来就比较麻烦，既要保存值域，也要保存节点和节点之间的关系，实际中树有很多表示方式如：双亲表示法，孩子表示法，孩子双亲表示法等。最常用的是孩子兄弟表示法。

struct TreeNode
{
    struct TreeNode* child;   //左边开始的第一个孩子
    struct TreeNode* brother; //指向右边的下一个兄弟的结点
    int data;                 //结点中的数据域
    
};

1.4 树形结构实际运用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

2.二叉树

2.1 概念与结构

在树形结构中，我们最常用的就是二叉树，一棵二叉树是结点的一个有限集合，该集合有一个根节点加上两棵别成为左子树和右子树的二叉树组成或者为空。

从上图可以看出二叉树具备以下的特点：

二叉树不存在度大于2的结点（二叉树的度有可能是 0、1、2）

二叉树的姿势有所有之分，次序不能颠倒，因此二叉树是有序树

注意：以下是符合二叉树的情况

2.2 特殊的二叉树

2.2.1 满二叉树

一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 n ，且节点个数是，则它就是满二叉树。推导公式如下：

2.2.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。特点：除了最后一层节点的个数不一定达到最大，其余的层对应的节点个数都是达到最大，并且最后一层的结点必须从左往右依次排列，否则，便不是完全二叉树。

所以完全二叉树和满二叉树的关系是：完全二叉树不一定是满二叉树，但是满二叉树一定是完全二叉树

二叉树的性质：

若规定根结点的层数为1，则一颗非空二叉树的第 i 层上最多有 $2^{i-1}$ 个结点

若规定根结点的层数为1，则深度为 h 的二叉树的最大节点数是 $2^h-1$

若规定根结点的层数为1，具有 n 个节点的满二叉树的深度 $h=\log_{2}(n+1)$

第3点的二叉树性质的推导：

2.3 二叉树存储结构

二叉树一般可以使用的两种存储结构，一种是顺序结构，一种是链式结构

2.3.1 顺序结构

顺序结构就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。

现实中，我们通常把堆（一种二叉树）使用顺序结构的数组来存储，特别要注意的是这里的堆和操作系统的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.3.2 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，用链表来指示元素的逻辑关系。通常的方法是链表中的每个节点有三个域组成，数据域和指针域，左右指针分别用来给该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，一般都是二叉链。在红黑树会使用到三叉链。

3.实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

3.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 否则无右孩子

上述性质的推导：

3.2 堆的实现

堆的底层结构是数组，因此定义堆的结构为：

堆的实现代码

3.2.1 向上调整算法

堆的插入

将要插入的数据插入数组的尾上，再依次进行比较，利用向上调整算法，直到实现堆。

向上调整算法：

先将元素插入到堆的尾部，最后一个孩子之后

插入之后依次与其双亲结点进行比较，调整到合适的位置

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整算法
void Adjustup(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;
	
	while (child > 0)
	{
		// < : 小堆
		// > : 大堆
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child],&arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}

}

//插入数据
void HeapPush(Heap* php, HPDataType x) {
	assert(php);
		//增容
		if (php->size == php->capacity)
		{
			int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
			HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
			if (tmp == NULL)
			{
				perror("realloc fail!!!\n");
				exit(1);
			}
			php->arr = tmp;
			php->capacity = newCapacity;
		}
	//空间足够，插入数据
	php->arr[php->size] = x;
	//这里不能进行size++，因为下面向上调整算法中的第二个参数穿的是孩子节点的
	//下标，必须是要有效的，如果在这里进行了size++，那么后面的size就不是有效
	//的了
	
	//向上调整算法
	Adjustup(php->arr, php->size);
	php->size++;
}

堆的向上调整算法的时间复杂度

因为堆是完全二叉树，而满二叉树是特殊的完全二叉树，为了简便，使用满二叉树来推导向上调整算法的时间复杂度

分析：

第1层： $2^{0}$ 个结点，需要向上移动0层

第2层： $2^{1}$ 个结点，需要向上移动1层

第3层： $2^{2}$ 个结点，需要向上移动2层

第4层： $2^{3}$ 个结点，需要向上移动3层

第h层： $2^{h-1}$ 个结点，需要向上移动h-1层

需要移动的结点总的移动步数为：每层结点个数*向上调整的次数（第一层调整次数为0）

$T (h) = 2^{1}*1+2^{2}*2+2^{3}*3+2^{4}*4+...+2^{h-2}*(h-2)+2^{h-1}*(h-1)$
$2T (h) = 2^{2}*1+2^{3}*2+2^{4}*3+2^{5}*4+...+2^{h-1}*(h-2)+2^{h}*(h-1)$

2式-1式错位相减：

$T (h) =-2^{1}*1-(2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1})+2^{h}*(h-1)$

$T (h) =-2^{0}-2^{1}*1-(2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1})+2^{h}*(h-1)+2^{0}$

$T (h) =-(2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1})+2^{h}*(h-1)+2^{0}$

$T (h) =-(2^{h}-1)+2^{h}*(h-1)+2^{0}$

根据二叉树性质： $n=2^h-1$ 和 $h=\log_{2}(n+1)$

$T(n)=-n+2^h*(h-1)+2^0$

$T(h)=-2^{h}+1+2^h*(h-1)+2^0$

将 $2^h$ 提出来：

$T(h)=2^h*(h-2)+2$

将 $h=\log_{2}(n+1)$ 带入上面的是式子中：

$T(n)=(n+1)(\log_{2}(n+1)-2)+2$

所以向上调整算法的时间复杂度为： $O(n\log_{2}n)$

3.2.2 向下调整算法

堆的删除

删除堆就是删除堆顶元素，并不是将堆顶元素直接删除并将后续的元素整体往前挪动就行，这是错误的；而是将堆顶与最后一个数据进行交换，然后删除数组的最后一个元素，在进行向下调整算法。

向下调整算法的前提：左右子树必须是一个堆才可以调整。

向下调整算法：

将堆顶元素与堆中最后一个元素进行交换

删除堆中的最后一个元素

将堆顶元素进行向下调整道满足堆的特性为止

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	//小堆
	int child = 2 * parent + 1;
	while (child < n )
	{
		//先比较child和child++，谁小，比较谁
		//找最小的孩子
		if (child++<n && arr[child] > arr[child++])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			//进行交换
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}


	}
}

//删除元素 ---- 对于堆来说，删除的就是堆顶元素
void HeapPop(Heap* php) 
{
	assert(!HeapEmpty(php));
	//堆尾元素与堆顶元素进行交换
	Swap(&php->arr[0], &php->arr[php->size-1]);
	php->size--;
	//向下调整
	AdjustDown(php->arr, 0, php->size);

}

堆的向下调整算法的时间复杂度

和向上调整算法的时间复杂度的思路是相似的，有一点点不同

分析：

第1层： $2^{0}$ 个结点，需要向下移动h-1层

第2层： $2^{1}$ 个结点，需要向下移动h-2层

第3层： $2^{2}$ 个结点，需要向下移动h-3层

第4层： $2^{3}$ 个结点，需要向下移动h-4层

第h-1层： $2^{h-2}$ 个结点，需要向上下移动1层

需要移动的结点总的移动步数为：每层结点个数*向上调整的次数（第一层调整次数为0）

$T (h) = 2^{0}*(h-1)+2^{1}*(h-2)+2^{2}*(h-3)+2^{3}*(h-4)+...+2^{h-2}*1$
$2T (h) =2^{1}*(h-1)+2^{2}*(h-2)+2^{3}*(h-3)+2^{4}*(h-4)+...+2^{h-1}*1$

2式-1式错位相减：

$T (h) =1-h-(2^{1}+2^{2}+2^{3}+2^{4}...+2^{h-2}+2^{h-1})$

$T (h) =2^{0}+2^{1}+2^{2}+2^{3}+2^{4}...+2^{h-2}+2^{h-1}-h$

$T (h) =2^{h}-1-h$

根据二叉树性质： $n=2^h-1$ 和 $h=\log_{2}(n+1)$

$T(n)=n-\log_{2}(n+1)\approx n$

所以向下调整算法的时间复杂度为：O(n)

3.3 堆的应用

3.3.1 堆排序

1.建堆过程

数组为：int arr[] = { 12,19,23,17,20,14 };
先让上面的数组成为一个有效的堆（要么是大堆要么是小堆）

先从右子树开始，也就是最后一个结点的父结点开始进行向下调整算法（从上图中的23开始）

调试的过程：

上述仅仅是将堆变为有效的堆并没有排好序，应该怎样排序呢？？？？

2.排序过程

将根结点与最后一个结点进行交换，end--（int end=n-1，下标位置）
将根结点进行向下调整算法，调整到合适的位置
循环前两步操作，循环条件：while(end>0)

调试结果：

//堆排序
void HeapSort(HPDataType* arr,int n)
{
	//方一：
	// 
	//int child = n - 1;
	//int parent = (child - 1) / 2;
	//while (parent >= 0)
	//{
	//	AdjustDown(arr, parent, n);
	//	parent--;
	//}

	//方二：
	
	//根据给定的数组来进行建堆
	//child：n-1  parent：(child-1)/2 = (n-1-1)/2

	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//向下调整算法建堆,先从最后一个结点的父结点开始
		AdjustDown(arr, i, n);
	}

	//开始堆排序——借助堆的思想而不是借助数据结构——堆来实现堆排序
	
	//排升序 ----- 建大堆
	//排降序 ----- 建小堆 (最小的数据放在数组最后的位置上，次小的放在n-2的位置上，那么最大的放在下标为0的位置上，所以排的是降序)
	int end = n - 1;
	while (end> 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);  //向下调整算法的时间复杂度为：O(N)
		end--;
	}



}

堆排序中将小堆根结点与最后一个结点进行交换，最小的值在数组下标为end=n-1的位置，end--

对新的根结点进行向下调整放在合适的位置，继续对根结点同样的操作，次小的值放在end的位置

所以：

排降序 -------- 建小堆

排升序 -------- 建大堆

记忆方法：

建小堆将最小的放在末尾，自然排的就是降序，反之建大堆排的就是升序

3.3.2 TOP-K问题

思路：

找最大的前k个数据，建小堆，遍历剩余的N-k个数据，与堆顶（最小的）进行比较

比堆顶大的数据入堆，因为找的是大的数据，比堆顶小的不入堆

找最小的前k个数据相反，建大堆

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void TopK()
{
	int k = 0;
	printf("请输入k的大小：");
	scanf("%d",&k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen feil!\n");
		exit(1);
	}

	//前k个数据进行建堆,找最大的数据建小堆
	int* minHeap = (int*)malloc(sizeof(int)*k);
	if (minHeap == NULL)
	{
		perror("malloc feil!\n");
		exit(2);
	}

	//读取文件中前k个数据建堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历N-K个数据，与堆顶比较，谁大谁入堆,
	//调整堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}

//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);

	minHeap = NULL;
	free(minHeap);

}

运行结果1：

运行结果2：

完全二叉树由数组实现，非完全二叉树由链式结构来实现

4. 实现链式结构二叉树

链式结构二叉树：用链表来表示一棵二叉树，即用链来只是元素的逻辑关系。结构如下：

typedef char BTDataType;

//二叉树结点结构的定义

typedef struct BinaryTreeNode {
	BTDataType data;   //当前结点的值域
	struct BinaryTreeNode* left;   //指向当前结点的左孩子
	struct BinaryTreeNode* right;  //指向当前结点的右孩子
}BTNode;

手动实现一颗链式二叉树的代码如下：

BTNode* buyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

//手动实现一棵二叉树
BTNode* CreateTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');
	BTNode* nodeG = buyNode('G');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	nodeE->left = nodeG;

	return nodeA;

}

4.1 二叉树的前中后序遍历

4.1.1 遍历规则

按照规则，二叉树的遍历有：前序、中序、后序的递归结构遍历：

前序遍历（先序遍历）：访问根结点的操作发生在遍历其左右子树之前

访问顺序为：根 -> 左 -> 右

中序遍历：访问根结点的操作发生在遍历其左右子树之间

访问顺序为：左 -> 根 -> 右

后序遍历：访问根结点的操作发生在遍历其左右子树之后

访问顺序为：左 -> 右 -> 根

4.1.2 先序遍历代码实现：

//前序遍历(先序遍历) ---- 根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

代码分析：

同样的思路，中序代码的实现：

//中序遍历  ------  左根右
void InOrder(BTNode* root) {
	if (root == NULL)
	{
		printf("NULL ");
		return;

	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

依次类推，后序代码的实现：

//后序遍历  ----- 左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);

}

4.2 结点个数以及高度

//二叉树结点个数
int BinaryTreeSize(BTNode* root){
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);

}

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//二叉树第k层结点个数
int BinaryTreeKSize(BTNode* root,int k) {
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeKSize(root->left,k-1) + BinaryTreeKSize(root->right,k-1);
}

//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root) 
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

//二叉树查找值为x的结点
BTNode* BinaryTreeNodeFind(BTNode* root,int x) 
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind=BinaryTreeNodeFind(root->left,x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeNodeFind(root->right,x);
	if (rightFind)
	{
		return rightFind;
	}
	//左右子树都没找到值为x的结点，返回NULL
	return NULL;
}

4.3 层序遍历

二叉树除了上述的先、中、后序遍历外，还有层序遍历。设二叉树的根结点所在层数为1，二叉树的层序遍历就是从二叉树的根结点出发，首先访问第一层的根结点，其次访问的就是从左到右的结点，以此类推，访问第三层的结点，第n层的结点。

二叉树的层序遍历需要借助数据结构：队列

//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return; //空树情况
	}
	//借助数据结构——队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", top->data);
		//将队头的左右孩子入队列
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDestroy(&q);
}

4.4 判断此二叉树是否为完全二叉树

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root) 
{
	//借助数据结构——队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		//将不为空的队头结点的左右孩子入队列
		QueuePush(&q,top->left);
		QueuePush(&q, top->right);
		
	}
	//队列不一定为空，继续取队头出队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
		QueueDestroy(&q);
		return true;
	}
}

5. 二叉树选择题

二叉树性质：

1）对任何一棵二叉树，如果度为 0 其叶结点个数为 $n_{0}$ ,度为 2 的分支结点个数为 $n_{2}$ ，则有 $n_{0} = n_{2} + 1$

数据结构——二叉树+堆

1.树