• 【学懂数据结构】二叉树之舞之二叉树

    活动地址：CSDN21天学习挑战赛

    文章目录

    1.树概念及结构

    1.1树的概念

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

    现实世界的树：

    image-20220806091739000

    数据结构中的树：

    image-20220806091818379

    树的特征

    • 有一个特殊的结点，称为根结点，根节点没有前驱结点，每一个子树都有一个根结点。
    • 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i
      <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
    • 树是递归定义的。
    • 树形结构中，子树之间不能有交集，否则就不是树形结构 。

    image-20220806091939030

    树的相关概念

    ​ 其实就是把现实的树的概念加上人类的亲缘关系拿来形象化地命名。

    image-20220806092154657

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

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

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

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

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

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

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

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

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

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

    节点的祖先：从根到该节点所经分支上的所有节点，可以说有种一脉相承的感觉。如上图：A是所有节点的祖先；A和F是L的祖先

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

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

    树的表示

    ​ 树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

    ​ 父结点指向左边第一个子结点，子结点间的兄弟结点用指针链接起来。

    image-20220806095857866

    typedef int DataType;
struct Node
{
	struct Node* firstChild1; // (从左边算起)第一个孩子结点
	struct Node* pNextBrother; // 指向其下一个兄弟结点
	DataType data; // 结点中的数据域
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    2.二叉树概念及结构

    现实中的二叉树：

    image-20220806103427586
    还有就是舞之二叉树

    舞之二叉树

    概念

    ​ 二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

    image-20220806101145745

    由上图可以看出：

    1. 二叉树不存在度大于2的结点
    2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

    注意，对于任意的二叉树都是由以下几种情况复合而成的：

    image-20220806101916736

    特殊的二叉树

    1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
      说，如果一个二叉树的层数为K，且结点总数是2k -1 ，则它就是满二叉树。
    2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
      的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
      应时称之为完全二叉树。

    ​ 也就是说，完全二叉树，前k-1层都是满的，第k层不一定是满的，但要求从左到右是连续的，不能有空缺，结点数量范围为[2k-1 ,2k - 1]。

    image-20220807091233623

    ​ 要注意的是满二叉树是一种特殊的完全二叉树。

    二叉树的性质

    1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2i-1 个结点。
    2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2h - 1。
    3. 对任何一棵二叉树, 如果度为0的叶结点个数为n0 , 度为2的分支结点个数为n2 **,**则有n0 = n2 + 1，同时，度为1的分支节点个数为n1 ，则n1 的范围为[0, 1]。
    4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2 (n + 1)。
    5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
      1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
      2. 若2i+1，左孩子序号：2i+1；若2i+1>=n则无左孩子
      3. 若2i+2，右孩子序号：2i+2；若2i+2>=n则无右孩子

    选择题练习

    1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
    A 不存在这样的二叉树
    B 200
    C 198
    D 199

    根据题意，n2 = 199，由二叉树的性质3，n0 = n2 + 1 = 200，故选择B

    2.下列数据结构中，不适合采用顺序存储结构的是（ ）
    A 非完全二叉树
    B 堆
    C 队列
    D 栈

    A和C都不太适合采用顺序存储结构，作为单选题的话，A更不适合，因为非完全二叉树采用顺序存储结构会浪费大量空间，所以选择A。

    3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
    A n
    B n+1
    C n-1
    D n/2

    叶子结点就是度为0的结点，由二叉树的性质3，结合题意我们可以列出等式：n0 + n0 - 1 + n1 = 2n，而n1 要么是0、要么是1，假设是0，则原式为2n0 = 2n + 1，求出的n0 不为整数，而n0 只能是整数，所以n1 不为0而为1，代入就得到no = n。所以选择A。

    4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
    A 11
    B 10
    C 8
    D 12

    完全二叉树的高度范围公式为2h-1 ~ 2h - 1，而29 是512，210 - 1 是1023，531正好在这个范围内，所以这棵树的高度就为10。所以选择B。

    5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
    A 383
    B 384
    C 385
    D 386

    这道题和第三题是同一类型题，由题意得2n0 - 1 + n1 = 767，假设n1 为1，则有2n0 = 767，算出非整数，所以n1 只能是0，则有2n0 = 768，得n0 = 384。所以选择B。

    6.（不是二叉树）在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个。

    A 4
    B 5
    C 6
    D 7

    设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3.

    有n个节点的树的总边数为n-1条.

    根据度的定义,总边数与度之间的关系为：n - 1 = 0 x n0 + 1 x n1 + 2 x n2 + 3 x n3.

    联立两个方程求解,可以得到n0 = n2 + 2n3 + 1, n0=6

    所以选择C

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

    二叉树的顺序结构

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

    image-20220807122940030

    堆

    ​ 如果有一个关键码的集合K = {k0 , k1, k2, …, kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： ki<=k2i+1 且 ki<=k2i+2 (ki=>k2i+1 且 ki=>k2i+2 ) i = 0，1，2…，则称为小堆(或大堆)。

    ​ 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

    也就是说：

    • 小根堆：任何一个结点的值<=子结点的值且根节点最小。

    • 大根堆：任何一个结点的值>=子结点的值且根节点最大。

    特征：

    • 堆中某个节点的值总是不大于或不小于其父节点的值；
    • 堆总是一棵完全二叉树。

    image-20220806105902757

    堆的实现

    ​ 用动态顺序表存储和表示堆，下标的安排是从上到下、从左到右的。

    image-20220807092622051

    可以利用数组下标计算父子结点关系

    • leftChild = parent * 2 + 1
    • rightChild = parent * 2 + 2
    • parent = (child - 1) / 2（统一起来，不区分左右子节点）

    堆的结构声明

    ​ 我们使用的是动态顺序表，所以基本上就是动态顺序表的结构声明，只是取名不同。

    ​ arr是动态数组，size是现有结点总数，capacity是数组容量。

    typedef int HPDataType;
typedef struct
{
	HPDataType* arr;
	size_t size;
	int capacity;
}HP;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    初始化

    ​ 传入的结构体指针正常情况下不可能为NULL，用assert来检测异常情况。这里先不开辟动态数组，放到插入函数中实现。

    void HeapInit(HP* pH)
{
	assert(pH);

	pH->arr = NULL;
	pH->size = pH->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    堆的插入

    ​ 我们要将元素插入堆并且要保持堆的形态，也就是插完后小根堆仍是小根堆，大根堆仍是大根堆。

    ​ 这里采用向上调整算法，顾名思义，就是从下到上调整堆的结构。

    比如：先插入一个10到数组的尾上，因为这个堆是小根堆，10在下面不合适， 进行向上调整算法，10所在结点和其父结点比较，10比较小就交换，一直向上比较，直到10爬到堆顶或者比它的父结点要大为止。

    image-20220806120154917

    ​ 我们开始具体的代码实现，首先检测传入的结构体指针是否为NULL，我们要时刻记得这个堆是由动态顺序表实现的，那插入元素要先检查容量，不够的话要扩容，基本上和动态顺序表那块讲的一样。

    	//检查容量与扩容
	if (pH->size == pH->capacity)
	{
		int newCapacity = (pH->capacity == 0) ? 4 : pH->capacity * 2;

		HPDataType* tmp = (HPDataType*)realloc(pH->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		pH->arr = tmp;
		pH->capacity = newCapacity;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    ​ 然后就是将元素插入堆的尾部，再进行向上调整，这里就把向上调整算法封装成一个函数AdjustUp( )。

    //插入堆的尾
	pH->arr[pH->size] = tar;
	++pH->size;

	//向上调整算法
	AdjustUp(pH->arr, pH->size - 1);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    ​ AdjustUp函数传入的是数组和当前所在的子结点下标，再来一个父结点下标。进入循环，最坏情况是child等于0，也就是爬到了堆顶，（我们这里实现的是小根堆）其中如果child结点的值比parent结点小就向上交换，顺手封装个交换函数Swap( )，要是child结点的值更大的话，说明调整完毕，那就退出循环。

    ​ 要是向实现大根堆的话，其实很简单，其他的不用变，只需要把 if (arr[child] < arr[parent]) 改成 if (arr[child] > arr[parent]) 即可。

    void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType 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]);

		else
			break;

		child = parent;
		parent = (child - 1) / 2;
	}

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    ​ 向上调整算法时间复杂度为：O(logn)。

    ​ 总的代码实现：

    void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType 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]);

		else
			break;

		child = parent;
		parent = (child - 1) / 2;
	}

}

void HeapPush(HP* pH, HPDataType tar)
{
	assert(pH);
	//检查扩容
	if (pH->size == pH->capacity)
	{
		int newCapacity = (pH->capacity == 0) ? 4 : pH->capacity * 2;

		HPDataType* tmp = (HPDataType*)realloc(pH->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		pH->arr = tmp;
		pH->capacity = newCapacity;
	}
	//插入堆的尾
	pH->arr[pH->size] = tar;
	++pH->size;

	//向上调整算法
	AdjustUp(pH->arr, pH->size - 1);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    判断堆是否为空

    ​ 先实现判空函数是因为堆的删除和获取堆顶都要遵循一个前提——堆不为空。

    ​ 看看size是不是0，如果是的话就说明堆为空，就返回真，堆不为空就返回假。

    bool HeapEmpty(HP* pH)
{
	assert(pH);

	return pH->size == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    堆的删除

    ​ 删除堆是删除堆顶的数据并且要保持堆的形态，也就是删完后小根堆仍是小根堆，大根堆仍是大根堆。删除堆顶元素的同时保证堆的形态，这样的话原来次小或次大的元素就到了堆顶的位置了。

    ​ 将堆顶的数据和堆的最后一个数据一换，因为顺序表尾删很方便，然后删除最后一个数据，再进行向下调整算法。

    比如：删除以下堆的堆顶，由于是小根堆，只要父结点比子结点要大，就进行互换，而且是和较小的那个子结点换。

    image-20220806122236267

    image-20220807114056932

    ​ 我们来看看代码如何实现。

    ​ 首先就是检测传入指针是否为空以及堆是否为空，然后把堆顶和堆尾的元素互换一下，再向下调整，这里也把向下调整算法封装成一个函数AdjustDown( )。

    void HeapPop(HP* pH)
{
	assert(pH);
	assert(!HeapEmpty(pH));

	pH->arr[0] = pH->arr[pH->size - 1];
	--pH->size;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    ​ AdjustDown函数需要传入数组、结点总数以及堆顶下标，在比较的过程中，需要先比较出哪个子结点更小，我们这里一开始默认左结点更小int minChild = parent * 2 + 1;，而后在循环中，如果右结点存在minChild + 1 < sz，并且右结点的值比左结点的小arr[minChild + 1] < arr[minChild]，那就用右结点++minChild。

    ​ 循环的条件是minChild结点下标小于总结点数，不能越界，（小根堆）其中如果子结点更小，那就交换两结点，然后迭代继续，如果子结点更大，说明调整完毕，退出循环。

    ​ 这是针对小根堆的，如果是大根堆的话AdjustDown( )要把arr[minChild + 1] < arr[minChild]改成arr[minChild + 1] > arr[minChild]，并且要把if (arr[minChild] < arr[parent])改成if (arr[minChild] > arr[parent])。

    void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustDown(HPDataType* arr, int sz, int parent)
{
	int minChild = parent * 2 + 1;

	while (minChild < sz)
	{
		if (minChild + 1 < sz && arr[minChild + 1] < arr[minChild])
			++minChild;

		if (arr[minChild] < arr[parent])
		{
			Swap(&arr[minChild], &arr[parent]);
			parent = minChild;
			minChild = 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
    • 23
    • 24
    • 25
    • 26
    • 27

    ​ 向下调整算法时间复杂度为：O(logn)。

    获取堆顶的元素

    ​ 很简单，直接返回数组首元素即可，不过要先看看堆是不是空的，空的就无法获取了。

    HPDataType HeapTop(HP* pH)
{
	assert(pH);
	assert(!HeapEmpty(pH));

	return pH->arr[0];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    获取堆的结点数

    size_t HeapSize(HP* pH)
{
	assert(pH);
	return pH->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    堆的创建

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

    向下调整算法建堆

    ​ 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。如果是从上向下进行的话，不能保证每一个结点的左右子树都是堆，不过最下面一层不需要调整，因为它们是都是叶结点，本身就是堆，那不妨就从下向上进行调整。

    ​ 这里我们从倒数的第一个非叶结点的子树开始调整，使用向下调整算法，每次调整完后目标下标减1，然后再调整…一直循环过程到根节点的树，就可以调整成堆。

    比如下图建大根堆

    image-20220808163432524

    代码实现

    void HeapCreateDown(HPDataType* arr, size_t n)
{
    for(int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(arr, n, i);
    }  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    时间复杂度计算

    ​ 用满二叉树来看最坏情况：

    image-20220808102635321

    ​ 计算得到时间复杂度仅为：O(n)。

    ​ 层数越深，结点越多，单个结点需要调整次数越少；层数越浅，结点越少，单个结点需要调整次数越多。

    向上调整算法建堆

    ​ 从上向下进行向上调整算法，初始状态下数组第一个元素可以看成堆，根据要建成大根堆还是小根堆确定向上调整函数的比较逻辑，然后从第二个元素开始进行向上调整，接着到第三个…依次类推，每次向上调整都是一次元素插入，并且满足大根堆或小根堆的要求。

    代码实现

    void HeapCreateUp(HPDataType* arr, size_t n)
{
    for(int i = 1; i < n; i++)
    {
        AdjustUp(arr, i);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    时间复杂度计算

    ​ 用满二叉树来看最坏情况：

    image-20220808171828718

    ​ 计算得到时间复杂度为O(n*logn)。

    ​ 层数越深，结点越多，单个结点需要调整次数越多；层数越浅，结点越少，单个结点需要调整次数越少。

    堆的应用

    堆排序

    ​ 本质上是一种选择排序，依次选数，从后往前排。

    ​ 不建议新建一个堆来实现堆排序，没有必要再手搓一个堆出来，一是麻烦，二是空间复杂度会变成O(n)。

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

    1. 建堆
      升序：建大堆（建小堆依次取堆顶的话每次取堆顶后都要建堆，总时间复杂度O(n2 )）
      降序：建小堆（建大堆依次取堆顶的话每次取堆顶后都要建堆，总时间复杂度O(n2 )）

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

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

    比如：要求升序的话，每次都把堆顶元素和最后的元素互换，然后最后一个元素不看作堆里的，堆顶向下调整，选出次大的，后续依次类型处理。（要求降序的话思路类同，就是每次把最小的换到后面去顺便选出次小的）

    如图所示：

    image-20220808112340229

    代码实现

    ​ 前面写的AdjustDown( )用的是针对小根堆的逻辑，适合降序使用，如果想要升序，就在函数里把arr[minChild + 1] < arr[minChild]改成arr[minChild + 1] > arr[minChild]，并且要把if (arr[minChild] < arr[parent])改成if (arr[minChild] > arr[parent])。

    void HeapSort(int* arr, int n)
{
	//建堆
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(arr, n, i);
	}
	//排序
	for (int i = 1; i < n; ++i)
	{
		Swap(&arr[0], & arr[n - i]);
		AdjustDown(arr, n - i, 0);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    时间复杂度计算

    ​ 向下调整算法的时间复杂度为O(logn)，外面套个循环，那就是O(n*logn)。

    Top-K问题

    ​ 即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
    ​ 对于Top-K问题，能想到的最简单直接的方式就是排序，但是，如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中，而存在磁盘文件中)。

    最佳的方式就是用堆来解决，基本思路如下：

    1. 用数据集合中前K个元素来新建堆
      前k个最大的元素，则建小堆（建大堆popK次遇到大量数据就不行了，因为数据很可能不在内存而在磁盘文件中，而建堆必须要在内存中搞）
      前k个最小的元素，则建大堆（建大堆popK次遇到大量数据就不行了，因为数据很可能不在内存而在磁盘文件中，而建堆必须要在内存中搞）
    2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足条件则替换堆顶元素并调整堆。

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

    比如说我要找前K个最大元素：

    void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustDown(HPDataType* arr, int sz, int parent)
{
	int minChild = parent * 2 + 1;

	while (minChild < sz)
	{
		if (minChild + 1 < sz && arr[minChild + 1] < arr[minChild])
			++minChild;

		if (arr[minChild] < arr[parent])
		{
			Swap(&arr[minChild], &arr[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
			break;
	}

}
HPDataType* GetTopK(HPDataType* arr, int n, int k)
{
	HPDataType* heap_k = (HPDataType*)malloc(k * sizeof(HPDataType));
	if (heap_k == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	for (int j = 0; j < k; j++)
	{
		heap_k[j] = arr[j];
	}
	//建小根堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(heap_k, k, i);
	}
	//比较剩余元素和调整堆
	for (int i = 0; i < n - k; i++)
	{
		if (arr[k + i] > heap_k[0])
		{
			Swap(&heap_k[0], &arr[k+i]);
			AdjustDown(heap_k, k, 0);
		}
	}

	return heap_k;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    ​ 由K + (n-K)log2 K 推得时间复杂度：O(n)

    ​ 空间复杂度：O(K)其实就是常数级O(1)

    4.二叉树的链式结构

    概念与认知

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

    ​ 链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，以后学到高阶数据结构如红黑树等会用到三叉链。

    image-20220809094429558

    image-20220809094435123

    正确认知二叉树

    1. 空树
    2. 非空树：根节点，根节点的左子树、根节点的右子树组成的。

    image-20220809094709532

    ​ 二叉树定义是递归式的，因此后面的基本操作中基本都是按照该概念实现的 。

    简单创建二叉树

    ​ 在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在我对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，反过头再来研究二叉树真正的创建方式 。

    typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* CreateBinaryTree()
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n3->left = NULL;
	n3->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;

	return n1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    ​ 注意：上述代码并不是真正创建二叉树的方式，真正创建二叉树方式以后再重点讲解 。

    ​ 这里的代码建出来的二叉树是这样的：

    image-20220809155044612

    二叉树的遍历

    ​ 学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。 这里主要运用的是递归方法和分治思想。

    前序、中序以及后序遍历

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

    1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
    2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
    3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

    三种遍历的顺序：

    • 前序遍历：根->左子树->右子树
    • 中序遍历：左子树->根->右子树
    • 后序遍历：左子树->右子树->根

    举个例子：

    ​ 三种遍历的过程（把空树NULL也算进去）：

    image-20220809100918864

    ​ 由于被访问的结点必是某子树的根，所以N(Node**）、L(Left subtree）和R(Right subtree）又可解释为
    根、根的左子树和根的右子树**。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

    // 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    原逻辑结构图解

    image-20220809110035064

    前序遍历打印和图解分析

    ​ 这里写的是用前序遍历打印每一个结点（包括空树结点）。

    代码实现

    void PreOrderPrint(BTNode* root)
{
	if (root == NULL)
	{ 
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrderPrint(root->left);
	PreOrderPrint(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    函数调用过程图解

    image-20220809161536219

    中序遍历打印

    ​ 相比于前序遍历的代码，逻辑稍作改动即可：之前是先访问根结点，这里是先访问左子树。

    void InOrderPrint(BTNode* root)
{
	if (root == NULL)
	{ 
		printf("NULL ");
		return;
	}
    
	InOrderPrint(root->left);
	printf("%d ", root->data);	
	InOrderPrint(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    后序遍历打印

    ​ 相比于中序遍历的代码，逻辑稍作改动即可：这里是先访问左右子树再考虑根结点。

    void PostOrderPrint(BTNode* root)
{
	if (root == NULL)
	{ 
		printf("NULL ");
		return;
	}
    
	PostOrderPrint(root->left);
    PostOrderPrint(root->right);
	printf("%d ", root->data);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    遍历结果推导题

    ​ 先上三个结论：

    • 已知前序遍历结果和中序遍历结果，可以唯一确定一棵二叉树。
    • 已知中序遍历结果和后序遍历结果，可以唯一确定一棵二叉树。
    • 已知前序和后序遍历结果，不能唯一确定一棵二叉树。

    ​ 为什么第三个就不能唯一确定呢？

    ​ 举个简单的例子（这里不考虑NULL）：

    比如前序遍历结果为ABC，后序遍历结果是CBA。我们可以确定A一定是根结点，但我们无法知道，哪一个结点是左子树，哪一个结点是右子树，实际上这棵树有四种可能。

    image-20220809174223269

    ​ 从这里我们可以引申出一个结论：一棵非空的二叉树的先序遍历结果和后序遍历结果正好相反，则该二叉树一定满足只有一个叶子结点。

    例题：

    已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）

    A.ABDGHJKCEFILM
    B.ABDGJHKCEILMF
    C.ABDHKGJCEILMF
    D.ABDGJHKCEIMLF

    由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间

    故根：A

    A的左子树：JGDHKB A的右子树：ELIMCF

    A的左子树的根：B A的右子树的根：C

    B的左子树：JGDHK B的右子树：空 C的左子树：ELIM C的右子树：F

    B的左子树的根：D C的左子树根：E

    D的左子树的根：G D的右子树的根：H E的右子树的根:I

    故树的结构为：

    image-20220809185600804

    故前序遍历：

    A B D G J H K C E I L M F

    所以选择B

    层序遍历

    ​ 层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
    层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
    上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

    image-20220810090631143

    求二叉树结点数（入门）

    ​ 使用分治思想，将原问题划分为类同的若干个子问题再解决。要算整个二叉树的结点数，可以每次都划分为算当前根结点和左右子树的结点数，如图

    image-20220809120057798

    ​ 打个生活中的比方就是：学院要查人数，有可能让领导自己挨个地去统计吗？当然不可能，领导会把任务分解后派发下去给辅导员，辅导员分解任务到班级层面，把任务交给各班班长，班长再分解任务到宿舍层面，把任务交给宿舍长，那宿舍长还能再分解任务么？不能了，已经是最底层的了，要查人数直接瞟一眼宿舍就知道哪个在哪个不在了，然后各个宿舍长把自己宿舍的人数上报给各个班长，班长再把班级各个宿舍的人数统计后上报给辅导员，辅导员再把各个班级人数统计后上报给领导，最后领导就得到了学院人数情况。

    image-20220809162432067

    ​ 如果遇到空结点返回0，非空结点的话返回左右子树结点和+1（加1是因为要把根结点也算上）。

    int TreeSize(BTNode* root)
{
    return (root == NULL) ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

    • 1
    • 2
    • 3
    • 4

    递归图解

    image-20220810150747417

    image-20220810183746828

    image-20220810183757468

    求二叉树叶结点数

    ​ 其实这个就是上面那个问题的进阶版，因为上面求总结点数是遍历树，遇到非空结点就让返回值+1，而当前这个问题相当于增加了一个限制条件：叶结点，思路还是那么个思路，不断分解子问题到左右子树。

    ​ 遇到空结点不计入，遇到叶结点就返回1，而遇到非空且非叶的结点就返回左右子树的叶结点数之和。

    int TreeLeafNode(BTNode* root)
{
    if(root == NULL)
    	return 0;
        
    if(root->left == NULL && root->right == NULL)
        return 1;
    
    return TreeLeafNode(root->left) + TreeLeafNode(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    递归图示

    image-20220810153503572

    求二叉树的高度

    ​ 问题可以分解为求左右子树分别的高度，取较大的那个+1（加1是因为要把根结点那一层算上）。

    int TreeHeight(BTNode* root)
{
	if(root == NULL)
        return 0;
    
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);
    return leftHeight > rightHeight ? LeftHeight + 1 : rightHeight + 1;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    递归图解

    image-20220810155044916

    求二叉树第k层结点数

    ​ 问题转换成求取左右子树的分别的第k - 1层结点数之和。

    ​ 比如说以A为根结点，那么H所在层次是第四层，而以B为根结点，那么H所在的层次就是第3层，以E为根结点的话，H所在层次就是第2层，再以H为根结点的话，H所在层次就是第1层了，这时候就找到原先的第4层了，也就是说，随着问题分解，k逐渐递减，当递减到为1时，就说明到了我们要求的那一层次了。

    image-20220810173128575

    int TreeKLevelSize(BTNode* root, int k)
{
    assert(k > 0);
    
    if(root == NULL)
    	return 0;
        
    if(k == 1)
        return 1;
    
    return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    递归图解

    image-20220810175210322

    二叉树查找值为x的结点(及格门槛)

    ​ 还是用分治思想不断分解问题后求解，问题分解为到左右子树去查找。先看当前根结点的值是不是查找的值，不是的话去左子树找，找不到再去右子树找，还是找不到就说明当前子树结构中找不到目标值，就返回NULL。

    BTNode* TreeFind(BTNode* root, BTDataType x)
{
    if(root == NULL)
    	return NULL;
    if(root->data == x)
    	return root;
        
    BTNode* left = TreeFind(root->left, x);
    if(left)
		return left;
        
    BTNode* right = TreeFind(root->right, x);
 	if(right)
    	return right;
    
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    递归图解

    image-20220810183134385

    二叉树oj练习

    1. 单值二叉树。965. 单值二叉树 - 力扣（LeetCode）
    2. 检查两颗树是否相同。100. 相同的树 - 力扣（LeetCode）
    3. 对称二叉树。101. 对称二叉树 - 力扣（LeetCode）
    4. 二叉树的前序遍历。144. 二叉树的前序遍历 - 力扣（LeetCode）
    5. 二叉树中序遍历 。94. 二叉树的中序遍历 - 力扣（LeetCode）
    6. 二叉树的后序遍历 。145. 二叉树的后序遍历 - 力扣（LeetCode）
    7. 另一颗树的子树。572. 另一棵树的子树 - 力扣（LeetCode）

    在这里插入图片描述

  • 相关阅读:
    vant_radio组件实现勾选+取消勾选
    springboot对接postgres
    浅谈基于云计算的环境智能监控系统
    检测网络：让网络检测通过图表呈现 - gping
    【刷题（17）】技巧
    被vector动态扩容给坑了！
    javascript： Sorting Algorithms
    遇到python程序是通过sh文件启动的，如何调试
    Ubuntu 20.04中Nightingale二进制部署
    【数学建模】线性规划
  • 原文地址：https://blog.csdn.net/weixin_61561736/article/details/126283051