• DS二叉树的存储

    前言

    我们上一期已经介绍了树相关的基础知识，了解了树相关的概念和结构、二叉树的概念和结构以及性质、也介绍了他的存储方式！本期我们来根据上期介绍的对二叉树的顺序存储和链式存储分别进行实现！

    本期内容介绍

    二叉树的顺序结构

    堆的概念以及结构

    堆的实现

    堆的应用

    二叉树的链式结构

    二叉树的遍历

    二叉树的基本问题

    一、二叉树的顺序结构

    1、二叉树的顺序结构

    上一期我们介绍了一般的二叉树是不适合用数组来存储的，原因是可能会造成大量的空间浪费！但完全二叉树是适合用数组存储的！现实中的堆（完全二叉树）就是这么玩的！注意这里的堆是一种数据结构，不是内存中说的那个堆（操作系统的概念）！

    2、堆的概念以及结构

    如果有一个关键码集合K={k0,k1,k2,...,kn-1}把他们的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2*i+1 && Ki <= K2*i+2（Ki >= K2*i+1 && Ki >= K2*i+2) i = 0,1,2....则称为小堆（大堆），将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

    堆的性质：

    堆中的某个节点的值总数不大于或不小于父节点的值！

    堆总是一颗完全二叉树！

    大堆：父节点的值大于或等于其孩子节点的值！

    小堆：父节点的值小于或等于其孩子节点的值！

    OK，画个图来解释一下：

    3、堆的实现

    堆结构声明

    1. typedef int HPDataType;
    2. typedef struct Heap 
    3. {
    4. 	HPDataType* a;//存储数据的数组
    5. 	int size;//有效个数
    6. 	int capacity;//数组容量
    7. }HP;

    堆的初始化、销毁和打印

    这里和顺序表、顺序栈玩的一样就不再解释了，直接上代码！

    1. //初始化
    2. void HPInit(HP* p)
    3. {
    4. 	assert(p);
    5. 	p->a = NULL;
    6. 	p->size = 0;
    7. 	p->capacity = 0;
    8. }
    9.  
    10. //销毁
    11. void HPDestory(HP* p)
    12. {
    13. 	assert(p);
    14. 	free(p->a);
    15. 	p->size = p->capacity = 0;
    16. }
    17.  
    18. //打印
    19. void HPPrint(HP* p)
    20. {
    21. 	assert(p);
    22. 	for (int i = 0; i < p->size; i++)
    23. 	{
    24. 		printf("%d ", p->a[i]);
    25. 	}
    26. 	printf("\n");
    27. }

    堆的插入

    由于这里堆是按照完全二叉树的顺序存到数组中的，所以对于数组的插入而言，尾插是效率和操作最好的！也符合这里堆的特点。但插入后要继续保证是堆就要做出一些调整了！这里有两种方式，一个是向上调整、一个是向下调整！我们先来介绍调整算法！

    向上调整算法

    当在堆中插入一个数据后即在数组尾插了一个元素后，可能改数组已经不是一个堆了，要变成堆需要进行向上调整（待会介绍向下调整）！

    向上调整的思路：

    当孩子节点的值小于（小堆）或大于（大堆）父亲节点时则需要堆孩子和父亲进行交换！由于具体插入的值会影响多少，具体不知道，所以对要对该节点的每一层的祖先节点逐一层对比，即父节点的值小于或大于交换，否则不交换结束掉！交换后孩子到父亲的位置，父亲到他父亲的位置（-1除2），一直循环判断...。到底交换（调整）到什么时候循环才结束呢？我们一般想的是：父亲小于0时结束，但！父亲不可能小于0，即使父亲是0号位置，（0-1）/2 == 0，C语言是会取整的！所以，用父亲判断不行。那就只能用孩子判断了，当孩子调整到0位置时就不能在调了（再调就越界了）即就结束了！

    具体调整过程：

    代码实现：

    1. void AdjsutUp(HPDataType* a, int child)
    2. {
    3. 	int parent = (child - 1) / 2;//第一次找孩子的父亲
    4. 	while (child > 0)//当孩子为0结束
    5. 	{
    6. 		if (a[child] < a[parent])//孩子比父亲小(小堆)
    7. 		{
    8. 			Swap(&a[child], &a[parent]);//交换
    9. 			child = parent;//孩子到父亲的位置
    10. 			parent = (parent - 1) / 2;//父亲到他父亲的位置
    11. 		}
    12. 		else
    13. 		{
    14. 			break;//孩子和父亲相等或大于父亲时结束
    15. 		}
    16. 	}
    17. }

    复杂度分析：这里少调整0次，最多调整高度(h = log2(N+1))次，所以时间复杂度是：O(lg(N)),空间复杂度：额外使用临时变量的个数是常数个，所以空间复杂度：O（1）

    要实现插入这里还要实现一个向下调整算法！我们来实现一下：

    向下调整算法

    要进行向下调整的前提是：左右子树必须是堆！！！

    向下调整算法的思路：

    当该节点的左右子树都是堆（大堆或小堆）且该节点的值小于（大堆）或大于（小堆）左右子树的根节点的值时，要保证还是堆则需要向下调整。此时就得找出该节点左右子树中较小或较大的那个节点，进行与该节点进行交换，但具体交换的层数确定，所以得逐一对下每一层比较！当父亲节点的值和要交换的那个孩子节点交换后，父亲到孩子的位置，孩子在到孩子的孩子的位置，继续判断，当碰到该节点等于或大于的子树的节点时直接结束！否则继续循环判断！什么时候循环结束呢？当父亲到最后一层此时孩子的位置再*2+1就超过数组长度结束掉！但这里要注意一点就是，该节点有左孩子不一定有右孩子，所以在找较小或较大的那个孩子时一定要判断他的右孩子是否存在即*2+1 是否 < n

    具体调整过程：

    这里就是一个他的右孩子不存在的情况（会导致越界）：

    代码实现：

    1.  
    2. //向下调整算法
    3. void AdjustDown(HPDataType* a, int n, int parent)
    4. {
    5. 	int child = parent * 2 + 1;//假设第一个孩子就是要交换的那个孩子
    6. 	while (child < n)
    7. 	{
    8. 		//假设错误，调整
    9. 		if (child + 1 < n && a[child] > a[child + 1])
    10. 		{
    11. 			++child;
    12. 		}
    13.  
    14. 		if (a[child] < a[parent])//父亲比孩子大（小堆）
    15. 		{
    16. 			Swap(&a[child], &a[parent]);//交换
    17. 			parent = child;//父亲到孩子的位置
    18. 			child = parent * 2 + 1;//孩子到他孩子的位置
    19. 		}
    20. 		else
    21. 		{
    22. 			break;//当父亲和孩子相等或父亲大于孩子时结束
    23. 		}
    24. 	}
    25. }

    向下调整算法也是最多调整高度次，最少调整0次。所以，时间复杂度：O(lg(N))，额外使用临时变量的个数为常数个，所以空间复杂度：O（1）

    堆插入数据的代码：

    1. void HPPush(HP* p, HPDataType x)
    2. {
    3. 	assert(p);
    4. 	//判断扩容
    5. 	if (p->capacity == p->size)
    6. 	{
    7. 		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
    8. 		HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * newcapacity);
    9. 		if (tmp == NULL)
    10. 		{
    11. 			perror("realloc failed");
    12. 			exit(-1);
    13. 		}
    14.  
    15. 		p->a = tmp;
    16. 		p->capacity = newcapacity;
    17. 	}
    18.  
    19. 	//插入
    20. 	p->a[p->size++] = x;
    21. 	//向上调整
    22. 	AdjustUp(p->a, p->size - 1);
    23. }

    时间复杂度是向上调整的复杂度：O(lg(N))， 额外使用的空间个数是常量个即空间复杂度为O(1),

    堆的创建

    这里创建堆的思路就是把数组中的元素逐一插入到堆中，每次插入都会向上调整，最后就变成了堆！

    1. void Test()
    2. {
    3. 	int a[] = { 65,100,70,32,50,60 };
    4. 	HP hp;
    5. 	HPInit(&hp);
    6. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    7. 	{
    8. 		HPPush(&hp, a[i]);
    9. 	}
    10. 	HPPrint(&hp);
    11.  
    12. 	HPDestory(&hp);
    13. }

    时间复杂度：n个元素，每插入一次为lgN，所以整体是:O(N*lgN)。

    空间复杂度：创建堆要为其底层数组开空间，假设数组长度为N,即 O(N）

    注意：这里如果想要大堆的话可以在向上调整算法那里把大于号改小于符号即可实现！

    堆的删除

    堆的物理存储时数组，所以我们本质操作的还是数组！堆的删除是，删除堆顶的数据。但不能直接删掉堆顶的数据，如果直接干掉堆顶的数据剩下的数据就不一定是堆了！下次插入或删除时就得重新建堆（O（N*(N*lgN)),向上调整建堆为O(N*lgN),这里每删一个建一次堆，有N个元素就是O（N*(N*lgN)，整体复杂度会变的很高！所以这种方式是不行的。这里的玩法是，第一个与最后一个先交换，然后删除最后一个（--size)然后再让0号位置的元素进行向下调整！时间复杂度：O(lg(N))

    代码实现

    1. //删除
    2. void HPPop(HP* p)
    3. {
    4. 	assert(p);
    5. 	assert(p->size > 0);//数组为空就不要删了
    6. 	//先把堆的第一个数据与最后一个数据交换，然后--size
    7. 	Swap(&p->a[0], &p->a[p->size - 1]);
    8. 	--p->size;
    9. 	//向下调整
    10. 	AdjustDown(p->a, p->size, 0);
    11. }

    判空和返回堆顶数据

    1. //取堆顶的数据
    2. HPDataType HPTop(HP* p)
    3. {
    4. 	assert(p);
    5. 	assert(p->size > 0);//没有元素
    6. 	return p->a[0];
    7. }
    8.  
    9. //判断是否为空
    10. bool IsEmpty(HP* p)
    11. {
    12. 	assert(p);
    13. 	return p->size == 0;
    14. }

    整体测试一下：

    1. void Test()
    2. {
    3. 	int a[] = { 65,100,70,32,50,60 };
    4. 	HP hp;
    5. 	HPInit(&hp);
    6. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    7. 	{
    8. 		HPPush(&hp, a[i]);
    9. 	}
    10. 	HPPrint(&hp);
    11.  
    12. 	while (!IsEmpty(&hp))
    13. 	{
    14. 		printf("%d ", HPTop(&hp));
    15. 		HPPop(&hp);
    16. 	}
    17.  
    18. 	HPDestory(&hp);
    19. }

    这里取堆里的数据并删除后一趟下来后直接变得有序了！但这并不是堆排序！待会再介绍堆排是解释！

    堆的全部代码

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7.  
    8. typedef int HPDataType;
    9. typedef struct Heap 
    10. {
    11. 	HPDataType* a;//存储数据的数组
    12. 	int size;//有效个数
    13. 	int capacity;//数组容量
    14. }HP;
    15.  
    16. //初始化
    17. void HPInit(HP* p);
    18. //销毁
    19. void HPDestory(HP* p);
    20. //打印
    21. void HPPrint(HP* p);
    22. //交换
    23. void Swap(HPDataType* a, HPDataType* b);
    24. //向上调整算法
    25. void AdjustUp(HPDataType* a, int child);
    26. //向下调整算法
    27. void AdjustDown(HPDataType*a, int n, int parent);
    28. //插入
    29. void HPPush(HP* p, HPDataType x);
    30. //删除
    31. void HPPop(HP* p);
    32. //取堆顶的数据
    33. HPDataType HPTop(HP* p);
    34. //判断是否为空
    35. bool IsEmpty(HP* p);
    1. #include "Heap.h"
    2.  
    3. //初始化
    4. void HPInit(HP* p)
    5. {
    6. 	assert(p);
    7. 	p->a = NULL;
    8. 	p->size = 0;
    9. 	p->capacity = 0;
    10. }
    11.  
    12. //销毁
    13. void HPDestory(HP* p)
    14. {
    15. 	assert(p);
    16. 	free(p->a);
    17. 	p->size = p->capacity = 0;
    18. }
    19.  
    20. //打印
    21. void HPPrint(HP* p)
    22. {
    23. 	assert(p);
    24. 	for (int i = 0; i < p->size; i++)
    25. 	{
    26. 		printf("%d ", p->a[i]);
    27. 	}
    28. 	printf("\n");
    29. }
    30.  
    31. //交换
    32. void Swap(HPDataType* a, HPDataType* b)
    33. {
    34. 	HPDataType tmp = *a;
    35. 	*a = *b;
    36. 	*b = tmp;
    37. }
    38.  
    39. //向上调整算法
    40. void AdjustUp(HPDataType* a, int child)
    41. {
    42. 	int parent = (child - 1) / 2;//第一次找孩子的父亲
    43. 	while (child > 0)//当孩子为0结束
    44. 	{
    45. 		if (a[child] < a[parent])//孩子比父亲小(小堆)
    46. 		{
    47. 			Swap(&a[child], &a[parent]);//交换
    48. 			child = parent;//孩子到父亲的位置
    49. 			parent = (parent - 1) / 2;//父亲到他父亲的位置
    50. 		}
    51. 		else
    52. 		{
    53. 			break;//孩子和父亲相等或大于父亲时结束
    54. 		}
    55. 	}
    56. }
    57.  
    58. //向下调整算法
    59. void AdjustDown(HPDataType* a, int n, int parent)
    60. {
    61. 	int child = parent * 2 + 1;//假设第一个孩子就是要交换的那个孩子
    62. 	while (child < n)
    63. 	{
    64. 		//假设错误，调整
    65. 		if (child + 1 < n && a[child] > a[child + 1])
    66. 		{
    67. 			++child;
    68. 		}
    69.  
    70. 		if (a[child] < a[parent])//父亲比孩子大（小堆）
    71. 		{
    72. 			Swap(&a[child], &a[parent]);//交换
    73. 			parent = child;//父亲到孩子的位置
    74. 			child = parent * 2 + 1;//孩子到他孩子的位置
    75. 		}
    76. 		else
    77. 		{
    78. 			break;//当父亲和孩子相等或父亲大于孩子时结束
    79. 		}
    80. 	}
    81. }
    82.  
    83. //插入
    84. void HPPush(HP* p, HPDataType x)
    85. {
    86. 	assert(p);
    87. 	//判断扩容
    88. 	if (p->capacity == p->size)
    89. 	{
    90. 		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
    91. 		HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * newcapacity);
    92. 		if (tmp == NULL)
    93. 		{
    94. 			perror("realloc failed");
    95. 			exit(-1);
    96. 		}
    97.  
    98. 		p->a = tmp;
    99. 		p->capacity = newcapacity;
    100. 	}
    101.  
    102. 	//插入
    103. 	p->a[p->size++] = x;
    104. 	//向上调整
    105. 	AdjustUp(p->a, p->size - 1);
    106. }
    107.  
    108. //删除
    109. void HPPop(HP* p)
    110. {
    111. 	assert(p);
    112. 	assert(p->size > 0);//数组为空就不要删了
    113. 	//先把堆的第一个数据与最后一个数据交换，然后--size
    114. 	Swap(&p->a[0], &p->a[p->size - 1]);
    115. 	--p->size;
    116. 	//向下调整
    117. 	AdjustDown(p->a, p->size, 0);
    118. }
    119.  
    120. //取堆顶的数据
    121. HPDataType HPTop(HP* p)
    122. {
    123. 	assert(p);
    124. 	assert(p->size > 0);//没有元素
    125. 	return p->a[0];
    126. }
    127.  
    128. //判断是否为空
    129. bool IsEmpty(HP* p)
    130. {
    131. 	assert(p);
    132. 	return p->size == 0;
    133. }
    1. #include "Heap.h"
    2.  
    3. void Test()
    4. {
    5. 	int a[] = { 65,100,70,32,50,60 };
    6. 	HP hp;
    7. 	HPInit(&hp);
    8. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    9. 	{
    10. 		HPPush(&hp, a[i]);
    11. 	}
    12. 	HPPrint(&hp);
    13. 	int k = 5;
    14.  
    15. 	while (!IsEmpty(&hp) && k--)
    16. 	{
    17. 		printf("%d ", HPTop(&hp));
    18. 		HPPop(&hp);
    19. 	}
    20.  
    21. 	HPDestory(&hp);
    22. }
    23.  
    24. int main()
    25. {
    26. 	Test();
    27. 	return 0;
    28. }

    4、堆的应用

    堆的应用有两个，一个是堆排序，另一个是TopK问题！堆排序就不用说了，就是对一个数组进行排序的。TopK问题也是日常中很常见的问题！例如：你平时点外卖，显示当地烤鸭饭第几的那个排名就是TopK，以及你们全专业前十的人，都是TopK问题！

    堆排序

    我们上面的堆虽然已经能实现排序了！但我们说他不是堆排序，原因是，你平时对数组排序时没有堆这中数据结构啊！这个结构虽然简单但也有200行，手搓是不是并不划算呀！另一方面即使你搓了出来，堆也是要开辟空间的，会有空间消耗，我们一般的排序是给个数组排出来即可！如何操作呢？这里有两种方式：向上调整建堆+向下调整排序，向下调整建堆+向下调整排序！

    关于升降序：升序--->建大堆        降序----->建小堆

    我们一般想的是升序建小堆，但如果是小堆取走最小的那一个堆顶数据后其他的数据组成的不一定是堆，要想继续排序就得建堆，我们上面分析过，复杂度变高了！所以这里采用删除的思想，把最大或最小的换到最后，然后对前N-i（i=1，2，3...n)个进行向下调整！

    向上调整建堆

    1. void HeapSort(HPDataType* a, int n)
    2. {
    3. 	//向上调整建堆
    4. 	//O(N*lgN)
    5. 	for (int i = 1; i < n; i++)
    6. 	{
    7. 		AdjustUp(a, i);
    8. 	}
    9.  
    10. 	//向下调整排序
    11. 	//O(N*lgN)
    12. 	int end = n - 1;
    13. 	while (end)
    14. 	{
    15. 		Swap(&a[0], &a[end]);
    16. 		AdjustDown(a, end, 0);
    17. 		--end;
    18. 	}
    19. }

    这里的向上调整建堆和上面堆的插入是一个思路！时间复杂度是O(lgN*N),向下调整排序的时间复杂度是：O(N*lgN)---->有n个元素，每排好一个一下下标，也就是上面的删除的思路！

    向下调整建堆

    1. void HeapSort(HPDataType* a, int n)
    2. {
    3. 	//向下调整建堆
    4. 	//O(N)
    5. 	for (int i = (n - 1) / 2; i >= 0; i--)
    6. 	{
    7. 		AdjustDown(a, n, i);
    8. 	}
    9.  
    10. 	//向下调整排序
    11. 	//O(N*lgN)
    12. 	int end = n - 1;
    13. 	while (end)
    14. 	{
    15. 		Swap(&a[0], &a[end]);
    16. 		AdjustDown(a, end, 0);
    17. 		--end;
    18. 	}
    19. }

    向下调整建堆，就是从倒数第一个元素的父节点开始向下调整为堆！这样越往上层节点的左右子树必定是堆！

    向下调整建堆的空间复杂度和上面向上调整建堆的一样！也是O(N*lgN)，关于向下调整建堆的时间复杂度是O(N),这里来推到一下！

    其实向上调整建堆的时间的复杂度也是这样算的！我们也可以来算一下：

    TopK问题

    TopK顾名思义就是找到数据集合中的前K个最大或最小的元素，一般情况下数据量都很大！

    例如：找世界企业500强，专业前5，游戏中活跃度最高的100位玩家等！而对于以上问题一般正常想到的就是对数据排序。但是如果量非常大的话，内存中可能根本存不下或数据一下子加载不到内存。此时排序就无法解决！这里最佳的解决方案是用堆！思路如下：

    1、用数据中的前K个在内存中建堆（前K个最大的，建小堆； 前K个最小的，建大堆）

    2、用剩下的n-k个元素依次与堆顶数据比较，不满足则进行替换堆顶元素

    3、以上这两步做完后，堆中剩余的K个元素就是最大或最小的前K个

    下面我在文件中写如10万个数据，查找前5个最大的为例：

    创造数据

    1. //创造数据
    2. void CreateData()
    3. {
    4. 	int n = 100000;
    5. 	srand((size_t)time(NULL));//产生随机数
    6. 	const char* file = "data.txt";//文件名
    7. 	FILE* fin = fopen(file, "w");//用fopen打开文件
    8. 	if (fin == NULL)
    9. 	{
    10. 		perror("fopen failed");//打开失败，直接终止程序
    11. 		exit(-1);
    12. 	}
    13.  
    14. 	for (int i = 0; i < n; i++)
    15. 	{
    16. 		int x = (rand() + i) % 100000;//产生随机数
    17. 		fprintf(fin, "%d\n", x);//把x以%d的形式写入fin指向的文件中
    18. 	}
    19.  
    20. 	fclose(fin);//关闭文件
    21. }

    可以来看看：

    TopK

    1. //TopK
    2. void PrintTopK(const char* filename, int k)
    3. {
    4. 	FILE* fout = fopen(filename, "r");//打开文件以读的形式
    5. 	if (fout == NULL)
    6. 	{
    7. 		perror("fopen failed");
    8. 		exit(-1);
    9. 	}
    10.  
    11. 	int* minheap = (int*)malloc(sizeof(int) * k);//创建k个空间的数组
    12. 	if (minheap == NULL)
    13. 	{
    14. 		perror("malloc failed");
    15. 		exit(-1);
    16. 	}
    17.  
    18. 	for (int i = 0; i < k; i++)
    19. 	{
    20. 		fscanf(fout, "%d", &minheap[i]);//从fout指向的文件中以%d形式读取k个，放到数组中
    21. 	}
    22.  
    23. 	//向下调整建堆
    24. 	for (int i = (k - 2) / 2; i >= 0; i--)
    25. 	{
    26. 		AdjustDown(minheap, k, i);
    27. 	}
    28.  
    29. 	int x = 0;
    30. 	while (~fscanf(fout, "%d", &x))//当fscanf没有读取失败即文件中还有数据时一直读取
    31. 	{
    32. 		//判断是否入堆
    33. 		if (x > minheap[0])
    34. 		{
    35. 			//替换入2堆
    36. 			minheap[0] = x;
    37. 			AdjustDown(minheap, k, 0);//向下调整
    38. 		}
    39. 	}
    40.  
    41. 	//输出
    42. 	for (int i = 0; i < k; i++)
    43. 	{
    44. 		printf("%d ", minheap[i]);
    45. 	}
    46. 	printf("\n");
    47. 		
    48. 	free(minheap);//释放malloc的空间，防止内存泄露
    49. 	fclose(fout);//关闭文件
    50. }

    前面这些都是C语言文件那块的基础知识，我加了很详细的注释就不再赘述了！这里来解释一下，为什么最大的K个元素要建立小堆，而最小的K个元素要建立大堆！以及为什么最后剩下的就是TopK元素！

    这是TopK最大元素，最小的也是同理！

    OK，对上面的TopK测试一下：

    但有个问题就是我们如何知道他这个是正确的呢？我们的解决方案就是在data.txt文件中随机位置添加5个较大的值，然后和运行结果对比！

    OK，结果一致！这就是TopK问题。

    二、二叉树的链式结构

    二叉树的链式结构即用链表结构来存储二叉树，这里和完全二叉树不一样没有限制，所有的二叉树都可以用链式结构来存储！我们在上一期二叉树基础介绍过，链式二叉树的组成有三部分：根、左子树、右子树。这里根据二叉树的结构（左右子树又可以分为根和左右子树）可以看出他是很适合用递归结构处理的！

    二叉树的遍历

    二叉树的遍历即按照某种特殊的规则依次对二叉树的每个节点进行访问的操作（每个节点只能访问一次）！遍历方式有四种（递归）：前序遍历、中序遍历、后序遍历和层序遍历！

    在遍历之前得现有一棵二叉树，所以先得搞一个二叉树出来！

    二叉树的节点声明：

    1. typedef char BTDataType;
    2. typedef struct BinaryTreeNode
    3. {
    4. 	BTDataType data;
    5. 	struct BinaryTreeNode* left;
    6. 	struct BinaryTreeNode* right;
    7. }BT;

    二叉树的创建

    创建这里我们采用二叉树的前序创建(如果不知道先序，可到下面先看先序)！# 表示该节点为NULL，否则表示该节点的值！这里我们在遍历之前，必须得有树，我们可以输入二叉树的先序包含NULL（#）的字符串，然后在去依次遍历字符串创建！

    思路：

    依次遍历str指向的字符串，当时 # 时跳过，表示该节点为NULL，否则去给该值开节点，然后跳过该字符。并依次用同样的思路创建其左右子树！当左右子树都创建完了返回改根节点！

    1. //创建
    2. BT* CreateBT(char* str, int* i)
    3. {
    4. 	if (str[*i] == '#')//如果是#即为NULL
    5. 	{
    6. 		++(*i);//跳过
    7. 		return NULL;//返回当前节点的值为空
    8. 	}
    9.  
    10. 	BT* root = (BT*)malloc(sizeof(BT));//否则为该值开空间
    11. 	if (root == NULL)
    12. 	{
    13. 		perror("malloc failed");
    14. 		exit(-1);
    15. 	}
    16.  
    17. 	root->data = str[*i];//吧改值赋给当前开的节点的数据域
    18. 	(*i)++;//跳过当前字符
    19. 	root->left = CreateBT(str,i);//继续构建该节点的左子树
    20. 	root->right = CreateBT(str,i);//继续构建该节点的右子树
    21.  
    22. 	return root;//构建好了当前子树返回根节点
    23. }

    我来画个图解释一下：

    前序遍历

    二叉树的前序遍历（Preorder Traversal）是先访问根节点再访问左子树，最后访问右子树的遍历方式！

    1. //前序遍历
    2. void PrveOrder(BT* root)
    3. {
    4. 	if (root == NULL)//如果该节点已经为空，直接返回NULL
    5. 		return;
    6.  
    7. 	printf("%c ", root->data);//先访问该节点的值
    8. 	PrveOrder(root->left);//然后访问其左子树
    9. 	PrveOrder(root->right);//访问其右子树
    10. }

    这里前、中、后序的递归遍历很类似，我这里画一个前序的具体遍历递归展开图，中后序同理！

    中序遍历

    二叉树的中序遍历（Inorder Traversal）是先访问左子树再访问根节点，最后访问右子树的遍历方式！

    1. //中序遍历
    2. void InOrder(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return;
    6.  
    7. 	InOrder(root->left);
    8. 	printf("%c ", root->data);
    9. 	InOrder(root->right);
    10. }

    后序遍历

    二叉树的后序遍历（Postorder Traversal）是先访问左子树再访问右子树,最后访问根节点的遍历方式！

    1. //后序遍历
    2. void PostOrder(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return;
    6.  
    7. 	PostOrder(root->left);
    8. 	PostOrder(root->right);
    9. 	printf("%c ", root->data);
    10. }

    OK，测试一下：

    1. void Test()
    2. {
    3. 	char str[100] = { 0 };
    4. 	printf("请输入二叉树序列的字符串:> ");
    5. 	gets(str);
    6. 	int i = 0;
    7. 	BT* root = CreateBT(str, &i);
    8. 	PrveOrder(root);
    9. 	printf("\n");
    10. 	InOrder(root);
    11. 	printf("\n");
    12. 	PostOrder(root);
    13. }

    OK，没有问题！我们来介绍一下另外一种遍历---层序遍历！

    层序遍历

    二叉树的层序遍历即从根节点开始，从上至下一层一层，每一层从左至右依次的访问每个节点的方式！要实现这个算法需要借助我们以前介绍过的一个数据结构--->队列来辅助是实现。

    思路：根节点如果不为空，则入队。然后判断队列是否为空，不为空的话，取队头节点的系节点，然后判断取出来的队头节点的左右孩子是否为空，不为空则入队了，否则不入！然后pop一下队头节点，继续执行新队头节点的判断！

    举个例子画个图来理解一下：

    代码实现

    1. //层序遍历
    2. void LevelOrder(BT* root)
    3. {
    4. 	Queue q;
    5. 	QInit(&q);
    6. 	if (root)
    7. 		QPush(&q, root);
    8.  
    9. 	while (!QEmpty(&q))
    10. 	{
    11. 		BT* front = QTop(&q);
    12. 		printf("%c ", front->data);
    13.  
    14. 		if (front->left)
    15. 			QPush(&q, front->left);
    16.  
    17. 		if (front->right)
    18. 			QPush(&q, front->right);
    19.  
    20. 		QPop(&q);
    21. 	}
    22. 	printf("\n");
    23.  
    24. 	QDestory(&q);
    25. }

    二叉树的基本问题

    这里的基本问题主要是：求二叉树节点的个数、求二叉树叶子节点的个数、二叉树第k层的节点个数、二叉树的按值查找、二叉树的高度等基本问题。

    求二叉树节点的个数

    思路：左子树的总结点 + 右子树的总结点 + 根节点

    1. //节点个数
    2. int BTNodeSize(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return 0;
    6. 	
    7. 	return BTNodeSize(root->left) + BTNodeSize(root->right) + 1;
    8. }

    求叶子节点的个数

    思路：叶子节点的特征是左右子树都为空。当一个节点的左右子树都为空时就是叶子节点

    1. //叶子节点的个数
    2. int BTLeafNodeSize(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return 0;
    6.  
    7. 	if (!root->left && !root->right)
    8. 		return 1;
    9.  
    10. 	return BTLeafNodeSize(root->left) + BTLeafNodeSize(root->right);
    11. }

    第K层节点的个数

    思路：第K层的节点是根节点的k层，k的孩子的k-1层。所以依次把问题给孩子，逐层-1去找，直到k==1时即为K层的节点。注意的是：必须对K判断大于0

    1. //第k层的节点个数
    2. int BTLevelKSize(BT* root, int k)
    3. {
    4. 	assert(k > 0);
    5. 	if (root == NULL)
    6. 		return 0;
    7.  
    8. 	if (k == 1)
    9. 		return 1;
    10.  
    11. 	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k -1);
    12. }

    二叉树的高度

    思路：二叉树的整体高度为左右子树中较高的那一个+根节点

    1. //二叉树的高度
    2. int BTDepth(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return 0;
    6.  
    7. 	int Left = BTDepth(root->left);
    8. 	int Right = BTDepth(root->right);
    9.  
    10. 	return Left > Right ? Left + 1 : Right + 1;
    11. }

    二叉树按值查找

    思路：从根节点开始查找，找到了返回节点地址，没有找到，继续去左右子树中去找

    1. //按值查找
    2. BT* BTFind(BT* root, BTDataType x)
    3. {
    4. 	if (root == NULL)
    5. 		return NULL;
    6.  
    7. 	if (x == root->data)
    8. 		return root;
    9.  
    10. 	return BTFind(root->left, x) ? BTFind(root->left, x) : BTFind(root->right, x);
    11. }

    这种写法可能可读性不好，也可以用下面这种！

    1. BT* BTFind(BT* root, int x)
    2. {
    3. 	if (root == NULL)
    4. 		return NULL;
    5.  
    6. 	if (root->data == x)
    7. 		return root;
    8.  
    9. 	BT* ret = NULL;
    10. 	ret = BTFind(root->left, x);
    11. 	if (ret)
    12. 		return ret;
    13.  
    14. 	ret = BTFind(root->right, x);
    15. 	if (ret)
    16. 		return ret;
    17.  
    18. 	return NULL;
    19. }

    或这种也可以：

    1. //按值查找
    2. BT* BTFind(BT* root, BTDataType x)
    3. {
    4. 	if (root == NULL)
    5. 		return NULL;
    6.  
    7. 	if (x == root->data)
    8. 		return root;
    9.  
    10. 	BT* ret = BTFind(root->left, x);
    11. 	if (ret)
    12. 		return ret;
    13.  
    14. 	return BTFind(root->right, x);
    15. }

    判断是否是完全二叉树

    思路：完全二叉树的特点是前k-1层是满二叉树，第k层的节点是连续的（必须是先左孩子，在右孩子，没有左孩子一定没有右孩子）。所以根据这一特性，当我们用层序遍历节点时，只要遇到NULL直接终止层序遍历。然后再去看队列中是否还有非空的节点，如果有就是非完全二叉树，否则就是完全二叉树！注意：当找到对类中还有非空节点时，在返回false之前需要把队列的空间释放了，否则会造成内存泄漏！！

    1. //判断是否是完全二叉树
    2. bool IsCompleteBT(BT* root)
    3. {
    4. 	Queue q;
    5. 	QInit(&q);
    6. 	if (root)
    7. 		QPush(&q, root);
    8.  
    9. 	while (!QEmpty(&q))
    10. 	{
    11. 		BT* front = QTop(&q);
    12.  
    13. 		if (front == NULL)
    14. 		{
    15. 			break;
    16. 		}
    17.  
    18. 		QPush(&q, root->left);
    19. 		QPush(&q, root->right);
    20.  
    21. 		QPop(&q);
    22. 	}
    23.  
    24. 	while (!QEmpty(&q))
    25. 	{
    26. 		BT* front = QTop(&q);
    27. 		if (front)
    28. 		{
    29. 			QDestory(&q);
    30. 			return false;
    31. 		}
    32. 		QPop(&q);
    33. 	}
    34.  
    35. 	QDestory(&q);
    36. 	return true;
    37. }

    二叉树的销毁

    思路：先销毁左子树，然后销毁右子树，最后在销毁根

    1. //二叉树的销毁
    2. void BTDestory(BT* root)
    3. {
    4. 	if (root == NULL)
    5. 		return;
    6.  
    7. 	BTDestory(root->left);
    8. 	BTDestory(root->right);
    9. 	free(root);
    10. }

    测试一下：

    链式存储的全部代码：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #pragma once
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. typedef char BTDataType;
    9. typedef struct BinaryTreeNode
    10. {
    11. 	BTDataType data;
    12. 	struct BinaryTreeNode* left;
    13. 	struct BinaryTreeNode* right;
    14. }BT;
    15.  
    16. //创建
    17. BT* CreateBT(char* str, int* i);
    18. //前序遍历
    19. void PrveOrder(BT* root);
    20. //中序遍历
    21. void InOrder(BT* root);
    22. //后序遍历
    23. void PostOrder(BT* root);
    24. //层序遍历
    25. void LevelOrder(BT* root);
    26. //节点个数
    27. int BTNodeSize(BT* root);
    28. //叶子节点的个数
    29. int BTLeafNodeSize(BT* root);
    30. //第k层的节点个数
    31. int BTLevelKSize(BT* root, int k);
    32. //二叉树的高度
    33. int BTDepth(BT* root);
    34. //按值查找
    35. BT* BTFind(BT* root, BTDataType x);
    36. //判断是否是完全二叉树
    37. bool IsCompleteBT(BT* root);
    38. //二叉树的销毁
    39. void BTDestory(BT* root);
    1. #include "BinaryTree.h"
    2. #include "Queue.h"
    3. //创建
    4. BT* CreateBT(char* str, int* i)
    5. {
    6. 	if (str[*i] == '#')
    7. 	{
    8. 		++(*i);
    9. 		return NULL;
    10. 	}
    11.  
    12. 	BT* root = (BT*)malloc(sizeof(BT));
    13. 	if (root == NULL)
    14. 	{
    15. 		perror("malloc failed");
    16. 		exit(-1);
    17. 	}
    18.  
    19. 	root->data = str[*i];
    20. 	(*i)++;
    21. 	root->left = CreateBT(str,i);
    22. 	root->right = CreateBT(str,i);
    23.  
    24. 	return root;
    25. }
    26.  
    27. //前序遍历
    28. void PrveOrder(BT* root)
    29. {
    30. 	if (root == NULL)
    31. 		return;
    32.  
    33. 	printf("%c ", root->data);
    34. 	PrveOrder(root->left);
    35. 	PrveOrder(root->right);
    36. }
    37.  
    38. //中序遍历
    39. void InOrder(BT* root)
    40. {
    41. 	if (root == NULL)
    42. 		return;
    43.  
    44. 	InOrder(root->left);
    45. 	printf("%c ", root->data);
    46. 	InOrder(root->right);
    47. }
    48.  
    49. //后序遍历
    50. void PostOrder(BT* root)
    51. {
    52. 	if (root == NULL)
    53. 		return;
    54.  
    55. 	PostOrder(root->left);
    56. 	PostOrder(root->right);
    57. 	printf("%c ", root->data);
    58. }
    59.  
    60. //层序遍历
    61. void LevelOrder(BT* root)
    62. {
    63. 	Queue q;
    64. 	QInit(&q);
    65. 	if (root)
    66. 		QPush(&q, root);
    67.  
    68. 	while (!QEmpty(&q))
    69. 	{
    70. 		BT* front = QTop(&q);
    71. 		printf("%c ", front->data);
    72.  
    73. 		if (front->left)
    74. 			QPush(&q, front->left);
    75.  
    76. 		if (front->right)
    77. 			QPush(&q, front->right);
    78.  
    79. 		QPop(&q);
    80. 	}
    81. 	printf("\n");
    82.  
    83. 	QDestory(&q);
    84. }
    85.  
    86. //节点个数
    87. int BTNodeSize(BT* root)
    88. {
    89. 	if (root == NULL)
    90. 		return 0;
    91. 	
    92. 	return BTNodeSize(root->left) + BTNodeSize(root->right) + 1;
    93. }
    94.  
    95. //叶子节点的个数
    96. int BTLeafNodeSize(BT* root)
    97. {
    98. 	if (root == NULL)
    99. 		return 0;
    100.  
    101. 	if (!root->left && !root->right)
    102. 		return 1;
    103.  
    104. 	return BTLeafNodeSize(root->left) + BTLeafNodeSize(root->right);
    105. }
    106.  
    107. //第k层的节点个数
    108. int BTLevelKSize(BT* root, int k)
    109. {
    110. 	assert(k > 0);
    111. 	if (root == NULL)
    112. 		return 0;
    113.  
    114. 	if (k == 1)
    115. 		return 1;
    116.  
    117. 	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k -1);
    118. }
    119.  
    120. //二叉树的高度
    121. int BTDepth(BT* root)
    122. {
    123. 	if (root == NULL)
    124. 		return 0;
    125.  
    126. 	int Left = BTDepth(root->left);
    127. 	int Right = BTDepth(root->right);
    128.  
    129. 	return Left > Right ? Left + 1 : Right + 1;
    130. }
    131.  
    132. //按值查找
    133. BT* BTFind(BT* root, BTDataType x)
    134. {
    135. 	if (root == NULL)
    136. 		return NULL;
    137.  
    138. 	if (x == root->data)
    139. 		return root;
    140.  
    141. 	BT* ret = BTFind(root->left, x);
    142. 	if (ret)
    143. 		return ret;
    144.  
    145. 	return BTFind(root->right, x);
    146. }
    147.  
    148.  
    149. //BT* BTFind(BT* root, int x)
    150. //{
    151. //	if (root == NULL)
    152. //		return NULL;
    153. //
    154. //	if (root->data == x)
    155. //		return root;
    156. //
    157. //	BT* ret = NULL;
    158. //	ret = BTFind(root->left, x);
    159. //	if (ret)
    160. //		return ret;
    161. //
    162. //	ret = BTFind(root->right, x);
    163. //	if (ret)
    164. //		return ret;
    165. //
    166. //	return NULL;
    167. //}
    168.  
    169.  
    170. //判断是否是完全二叉树
    171. bool IsCompleteBT(BT* root)
    172. {
    173. 	Queue q;
    174. 	QInit(&q);
    175. 	if (root)
    176. 		QPush(&q, root);
    177.  
    178. 	while (!QEmpty(&q))
    179. 	{
    180. 		BT* front = QTop(&q);
    181.  
    182. 		if (front == NULL)
    183. 		{
    184. 			break;
    185. 		}
    186.  
    187. 		QPush(&q, front->left);
    188. 		QPush(&q, front->right);
    189.  
    190. 		QPop(&q);
    191. 	}
    192.  
    193. 	while (!QEmpty(&q))
    194. 	{
    195. 		BT* front = QTop(&q);
    196. 		if (front)
    197. 		{
    198. 			QDestory(&q);
    199. 			return false;
    200. 		}
    201. 		QPop(&q);
    202. 	}
    203.  
    204. 	QDestory(&q);
    205. 	return true;
    206. }
    207.  
    208. //二叉树的销毁
    209. void BTDestory(BT* root)
    210. {
    211. 	if (root == NULL)
    212. 		return;
    213.  
    214. 	BTDestory(root->left);
    215. 	BTDestory(root->right);
    216. 	free(root);
    217. }

    队列代码

    1. #include "Queue.h"
    2.  
    3. //初始化
    4. void QInit(Queue* p)
    5. {
    6. 	assert(p);
    7. 	p->head = p->tail = NULL;
    8. 	p->size = 0;
    9. }
    10.  
    11. //销毁
    12. void QDestory(Queue* p)
    13. {
    14. 	assert(p);
    15. 	QNode* cur = p->head, *next = NULL;
    16. 	while (cur)
    17. 	{
    18. 		next = cur->next;
    19. 		free(cur);
    20. 		cur = next;
    21. 	}
    22. 	p->head = p->tail = NULL;
    23. 	p->size = 0;
    24. }
    25.  
    26. //开一个新节点
    27. QNode* BuyNode(QDataType x)
    28. {
    29. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    30. 	if (newnode == NULL)
    31. 	{
    32. 		perror("malloc failed");
    33. 		exit(-1);
    34. 	}
    35. 	newnode->data = x;
    36. 	newnode->next = NULL;
    37.  
    38. 	return newnode;
    39. }
    40.  
    41. //入队列
    42. void QPush(Queue* p, QDataType x)
    43. {
    44. 	assert(p);
    45. 	QNode* node = BuyNode(x);
    46. 	if (p->head == NULL)
    47. 	{
    48. 		p->head = p->tail = node;
    49. 	}
    50. 	else
    51. 	{
    52. 		p->tail->next = node;
    53. 		p->tail = node;
    54. 	}
    55. 	p->size++;
    56. }
    57.  
    58. //出队列
    59. void QPop(Queue* p)
    60. {
    61. 	assert(p);
    62. 	assert(p->head);
    63.  
    64. 	QNode* next = p->head->next;
    65. 	free(p->head);
    66. 	p->head = next;
    67. 	p->size--;
    68. }
    69.  
    70. //获取队列头的数据
    71. QDataType QTop(Queue* p)
    72. {
    73. 	assert(p);
    74. 	assert(p->size > 0);
    75.  
    76. 	return p->head->data;
    77. }
    78.  
    79. //获取队列尾的数据
    80. QDataType QTail(Queue* p)
    81. {
    82. 	assert(p);
    83. 	assert(p->size > 0);
    84.  
    85. 	return p->tail->data;
    86. }
    87.  
    88. //是否为空
    89. bool QEmpty(Queue* p)
    90. {
    91. 	assert(p);
    92. 	return p->size == 0;
    93. }
    94.  
    95. //获取队列的元素个数
    96. int QSize(Queue* p)
    97. {
    98. 	assert(p);
    99. 	return p->size;
    100. }
    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. typedef struct BinaryTreeNode* QDataType;
    8. typedef struct QListNode
    9. {
    10. 	QDataType data;
    11. 	struct QListNode* next;
    12. }QNode;
    13.  
    14. typedef struct Queue
    15. {
    16. 	QNode* head;
    17. 	QNode* tail;
    18. 	int size;
    19. }Queue;
    20.  
    21. //初始化
    22. void QInit(Queue* p);
    23.  
    24. //销毁
    25. void QDestory(Queue* p);
    26.  
    27. //开一个新节点
    28. QNode* BuyNode(QDataType x);
    29.  
    30. //入队列
    31. void QPush(Queue* p, QDataType x);
    32.  
    33. //出队列
    34. void QPop(Queue* p);
    35.  
    36. //获取队列头的数据
    37. QDataType QTop(Queue* p);
    38.  
    39. //获取队列尾的数据
    40. QDataType QTail(Queue* p);
    41.  
    42. //是否为空
    43. bool QEmpty(Queue* p);
    44.  
    45. //获取队列的元素个数
    46. int QSize(Queue* p);

    OK，本期分享就到这里！好兄弟，我们下期再见！

  • 相关阅读:
    芯片加速器 Accelerator
    GaussDB整体性能慢分析
    讯飞有一个可以根据描述文本自动生成PPT的AI接口，有趣
    ​LeetCode解法汇总337. 打家劫舍 III
    ffmpeg转码生成的m3u8格式详解
    JVM主要组成部分及其作用
    【云驻共创】华为云AI之《情感专家》在线分析影评情感基调
    MySQL常用操作
    1. pip和conda的区别
    C#---第22：Newtonsoft中json/array的解析、创建、SelectToken（获取指定values）方法
  • 原文地址：https://blog.csdn.net/m0_75256358/article/details/134410826