Note3---初阶二叉树～～

之前，我们学习了栈和队列的基础知识，有需要的小伙伴可以看小江的上一片篇博客哦～

Note2---栈和队列～～-CSDN博客文章浏览阅读323次，点赞6次，收藏7次。之前，我们学习了顺序表和链表的相关知识，也完成了相应的练习，接下来我们要学习的是栈和队列！本篇将会比较详细的进行讲解栈和队列的相关知识点及如何实现，以及一些）OJ题https://blog.csdn.net/2301_79184587/article/details/134438809这篇博客，我们一起来了解并学习数据结构中的初阶的二叉树，共同为C++打下牢固的基础！！！

二叉树的知识点和内容比较多，友友们一定要有耐心看完（跳到自己需要的部分也是OK的），下面我们开始今天的学习！！！

1.树概念及结构☎️

1.1 树的概念🎄

树是一种非线性（线性：一字排开）的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点

除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

因此，树是递归定义的。

这里我们先引入树的概念，可能会有一些看不懂的，但是没关系，第一部分看懂就行

1.2 树的相关概念🦜

注意⚠️

不是所有的概念都是重要的，我会把重要的概念标记出来，其余的我们做个了解就好

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

思考一下，为什么根定义成1，而不是0？

树的高度或深度：树中节点的最大层次；如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

1.2.1 部分概念的加深理解🐾

1. 子节点and父节点
有的节点可能是子节点，也可能同时是父节点---相对性

例如：D是A的子节点，D同时又是H的父节点

2. 节点的层次
说从根开始定义，那是从0还是1？

例如：数组我们从0开始定义下标---数组名是首元素地址（a[i]等价于*(a+i)）
但是，我们这里却大多从1开始定义

树会有这2种特殊的情况，如果我们从0开始定义：

只有根节点：0

空树：0？or -1？

怎么和只有根节点的情况区分？空树要定义成-1？

是对，定义成-1；注意这样的定义方法也是可以的，但是比较麻烦（后序实现二叉树时，每当需要高度的时候，可能还要思考一下）

如果我们从1开始定义：

只有根节点：1

空树：0

现在就很好区分了

1.2.2 树与非树🪴

树--->递归--->每次都根+子树---子树（不相交）=0的时候递归结束（即只有叶节点，没有子树了）

---铺垫后面的实现二叉树

1.3 树的表示🎋

要求：保存值域，也要保存结点和结点之间的关系

实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法

树的表示复杂在于定义多少个孩子

左孩子右兄弟的思路：

左边第一个为孩子，右边其余的为孩子的兄弟

孩子太多，管不过来--->生老大，让老大管老二，老二管老三......

typedef int DataType;
struct TreeNode
{
	DataType val;
	struct TreeNode* leftChild;
	struct TreeNode* rightBrother;
};

1.4 树在实际中的运用（表示文件系统的目录树结构）🥑

这里的实际运用主要是Linux中的树状目录结构（之后的博客，小江也会带大家学习Linux的基本知识和怎么写代码的）

指令：cd user（进入user路径下）

遍历当前目录的下一层树，遍历找到user，然后进入user---指令的本质是程序

2.二叉树概念及结构🧲

2.1概念🫒

一棵二叉树是结点的一个有限集合，该集合:

1. 一个节点只有2个孩子或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

可以理解为二叉树实行计划生育
可以生1个or不生（0个）or2个（最多2个）

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树的左右之分很重要

注意：对于任意的二叉树都是由以下几种情况复合而成的：（之后二叉树的实现会考虑到只有左/右子树，只有根节点，空树的情况）

注意⚠️
二叉树不等价于度为2的树
例如：二叉树也可能为空or只有根节点
二者是必要不充分的关系

2.2 特殊的二叉树🫑

满二叉树：每一层都是满的（每个节点都有2个孩子）

完全二叉树：前（n-1）层都是满的（每个节点都有2个孩子），最后一层不一定是满的，但是从左到右必须是连续的（是否连续的话就要看左子树和右子树了）

满二叉树是特殊的完全二叉树

如图：这就不是连续的了

2.2.1 如何求h是多少？h层（高度为h）节点数合计多少？🥝

2.3 二叉树的存储结构🪀

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

1. 顺序存储---完全二叉树/满二叉树

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储（关于堆我们后面会讲解）。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2. 链式存储---普通二叉树

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

这里说一下子节点和父节点之间的规律：

3.二叉树顺序结构及实现💊

3.1 二叉树的顺序结构🧃

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构🚛

堆---数据结构（堆总是一棵完全二叉树。）

所有元素按完全二叉树的顺序存储方式存储在一个一维数组中

堆分为：大堆和小堆

大堆：任意一个父亲（data）>=孩子（data）--->根节点是max

小堆：任意一个父亲（data）<=孩子（data）--->根节点是min

3.2.1 堆的意义🛶

1.堆排序

2.解决top k问题

1.堆排序：

大堆不一定有序，但是根是最大的--->调堆（选出max之后取出，找次大的，最多循环h次）

小堆也是同样的道理

时间复杂度：O(N*logN)

上面我们算出了完全二叉树N个节点的高度（h）范围，我们粗略估算大概有logN层，共N个节点，建堆的需要的时间复杂度：N、最多排序h次，故时间复杂度：O(N*logN)

我们大概粗略估算一下：h=logN

N=100万 h=20

最多20次就可以将100万个数据排完了

空间复杂度：O(1)

只要开辟空间给数组存储就行了

2.解决top k问题

例如我们要在100万个数据里面排出前10个最大的数据，利用堆排序的话，不需要排序100万次，只需要循环10次找出前10个最大的

3.3 堆的实现📟

在开始之前，我们先思考一下：之前说堆由顺序结构的数组来存储，那么堆的底层逻辑是顺序表嘛？

并不是，因为堆还要区分大小堆，而顺序表没有大小要求直接插入就行

3.3.1 小堆---向下调整💚

我们先以实现小堆为例，讲解一下向下调整的算法：

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

3.3.2 大堆---向上调整♻️

我们再以实现大堆为例，讲解一下向上调整的算法：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

具体的步骤和实现小堆一样，只不过遍历结束的条件是遍历到根节点，还需要递归实现

3.3.3 建堆时间复杂度🟢

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

向下调整建堆：

因此：向下调整建堆的时间复杂度为O(N)。

向上调整建堆：

由于证明思路和向下调整差不多，这里我们就不再证明了，而是简单的提一下：

我们向上调整，最后几层的节点个数在整个堆中（看作满二叉树）占比较大，往上移，移动次数又多，时间复杂度肯定高于向下调整

向下调整建堆的时间复杂度大概为O(N*logN）

3.3.4 堆的插入🟩

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

3.3.5 堆的删除🤢

删除堆是删除堆顶的数据

思路：将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

3.4 小堆代码实现📗

由于大堆和小堆只是调整到时候判断大小的符号不同，我们这里就演示小堆的实现，大堆大家可以自行实现

3.4.1 Heap.h🔋

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//数组存放
	int _size;//有效存储个数
	int _capacity;//空间
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

3.4.2 Heap.c🔫

#include"Heap.h"
// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
//交换
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)//到根节点结束
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);//交换位置
			child = parent;//继续遍历
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断空间是否足够
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (a == NULL)
		{
			perror("realloc error!\n");
			return;
		}
		hp->_a = a;
		hp->_capacity = newcapacity;
	}
	//插入数据
	hp->_a[hp->_size] = x;
	hp->_size++;
	//向上调整
	AdjustUp(hp->_a, hp->_size-1);//之前size++了
}
//向下调整
void AdjustDown(HPDataType* a, int  size, int parent)
{
	//假设法：假设最小的是左孩子，不对的话再修改
	int child = 2 * parent + 1;
	while (child<size)//child(左孩子)要在数组范围内
	{
		if (a[child + 1] < a[child] && child + 1 < size)//保证右孩子也在范围内
		{
			child++;//右孩子小--->和parent交换
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	//首尾交换
	Swap(&hp->_a[hp->_size - 1], &hp->_a[0]);
	hp->_size--;
	//向下调整
	AdjustDown(hp->_a, hp->_size, 0);//之前size--过了
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

4.4.2.1 向上调整的while（）结束的判断条件🧑🏻‍🎤

注意⚠️

我们是循环到根节点结束遍历

这里不能是while(parent>=0)

因为最后一次的时候：parent==0--->进入循环--->计算得出parent==0--->还要再次循环

而应该是while(child>0)

因为最后一次的时候：child>0--->进入循环--->计算得出child==0--->结束循环

3.4.3 test.c🧼

#include"Heap.h"
int main()
{
	int a[] = { 4,6,2,1,5,8,4,7,3,9 };
	Heap hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	return 0;
}

建堆的效果

虽然今天的代码和方法实现排序，但其实不是真正的堆排序

因为：
1.我们是把数组插入到堆里面，相当于在堆里面开了一个数组---一定的消耗
2.时间复杂度：O（N*log N）
空间复杂度：O（N）
3.堆排序是对数组进行排序，但是我们没有

更好的方法：直接将数组变成堆--->下面的内容，这也是为什么前面传参，没有把堆的结构体传过去（为堆排序做铺垫），而是传数组

4. 堆的应用🍟

4.1 堆排序---升序🧚🏻‍♀️

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

4.1.1 建堆的实现🧤

由于升序和降序的思路和实现差不多，我们这里就演示实现升序

上面提到建堆可以选择向上调整和向下调整2种方法，我们这里优先选择向下调整，因为时间复杂度低

代码实现是基于之前的堆的实现

本质是模拟堆插入的过程建堆

4.1.2 为什么建小堆不实现升序？建大堆实现升序？👒

按理来说，不应该是小堆实现升序，大堆实现降序嘛？

我们实现升序，分别2个思路对比实现一下：

4.1.3 代码实现🐸

4.1.3.1 Heap.h🐛

//堆排序
void HeapSort(int* a, int n);

4.1.3.2 Heap.c🪖

//堆排序--升序
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a,n,i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

4.1.3.2 test.c🐢

//堆排序---升序
int main()
{
	int a[] = { 13,2,6,8,4,6,0,9,5,7,3,1 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

4.2 Top-k问题👗

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

不能是前N个元素来建堆，否则占用内存过大

N个数据插入到堆里面，pop K次

时间复杂度：N*logN+K*logN--->O(N*logN) K<<N(忽略不计)

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

时间复杂度：O（N*logK）

4.2.1 为什么找前k个最大的元素要建小堆？🩴

设想一下：

建大堆的话，当最大的数据入堆时，后面的数据就进不来了

建小堆的话，当最大的数据入堆时，沉到堆底，其他数据继续入堆

4.2.2 代码实现🦖

4.2.1 Heap.h🐊

//向下调整
void AdjustDown(HPDataType* a, int  size, int parent);

4.2.2 test.c🪲

//TOP-K问题
void PrintTopK(int* a,int n,int k)
{
	//建一个k个数据的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error!\n");
		return;
	}
	//读取前k个，建小堆
	for(int i = (k - 1 - 1) / 2; i >= 0;i--)
	{
		AdjustDown(a, k-1, i);
	}
	// 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int m = 0;
	while (m<=n)
	{
		if (a[m] > minheap[0])
		{
			minheap[0] = a[m];
			AdjustDown(minheap, k, 0);
		}
		m++;
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
}
int main()
{
	int n = 10000000;//100万
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = (rand()+i) % 10000000;
	}
	//自定义k个不在范围内的，好查看方法是否正确
	a[5] = 10000000 + 1;
	a[1231] = 10000000 + 2;
	a[531] = 10000000 + 3;
	a[5121] = 10000000 + 4;
	a[115] = 10000000 + 5;
	a[2335] = 10000000 + 6;
	a[9999] = 10000000 + 7;
	a[76] = 10000000 + 8;
	a[423] = 10000000 + 9;
	a[3144] = 10000000 + 10;
	PrintTopK(a, n, 10);
	return 0;
}