• 【数据结构与算法】＜==＞二叉树下

     

    目录

    堆的应用

    1.堆排序：

    1. 建堆

    2.向下调整的时间复杂度

    3.向上调整建堆的时间复杂度

    ​

    二叉树链式结构的实现

    遍历操作

    其他操作

    堆的应用

    1.堆排序：

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

    1. 建堆

    升序：建大堆

    序：建大堆（如果建小堆的话，小堆不一定有序，只是堆顶最小，那下一个最小的数呢？如何依次选最小的数据？就算是选出来了之后，结点之间的关系就全乱了，无法继续利用优势，只能重新建堆O(N)，选出次小的数据，效率太低了）建大堆直接交换堆顶和最后一个，进行向下调整即可

    降序：建小堆
    2.堆利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。回顾一下向下调整的过程：
    image-20220809232058329

    这里的建堆，是直接用数组进行建堆，可以用向上调整算法进行建堆，也可以利用向下调整建堆，有什么区别？我们先来看代码的实现：

    1. //建堆——a，利用向上调整建堆——O（N*logN）
    2. 	//直接插入
    3. 	/*for (int i = 1; i < n; i++)
    4. 	{
    5. 		AdjustUp(a, i);
    6. 	}*/
    7. 	//建完堆之后无序，我们排个序
    8.  
    9.  
    10. 	//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整，直到根)——O(N)
    11. 	for (int i = (n-1-1)/2; i>=0; i--)
    12. 	{
    13. 		AdjustDown(a, n, i);
    14. 	}

    两种的时间复杂度不一样：向上调整建堆的时间复杂度是O（N*logN）;向下调整建堆的时间复杂度是O（N）。所以我们选用的是向下调整算法进行建堆，关于向下调整算法时间复杂度的推导过程：

    2.向下调整的时间复杂度

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

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

    3.向上调整建堆的时间复杂度

     

    了解完后我们下面来实现排序

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include<stdio.h>
    3. //向下调整
    4. void swap(int* p1, int* p2)
    5. {
    6. 	int tmp = *p1;
    7. 	*p1 = *p2;
    8. 	*p2 = tmp;
    9. }
    10. void adjustdown(int* a, int n, int parent)
    11. {
    12. 	//默认左孩子为最小值
    13. 	int minchild = parent * 2 + 1;
    14. 	while (minchild < n)
    15. 	{
    16. 		if (minchild + 1 < n && a[minchild] > a[minchild + 1])
    17. 		{
    18. 			minchild++;
    19. 		}
    20. 		if (a[minchild] < a[parent])
    21. 		{
    22. 			swap(&a[minchild], &a[parent]);
    23. 			parent = minchild;
    24. 			minchild = parent * 2 + 1;
    25. 		}
    26. 		else
    27. 		{
    28. 			break;
    29. 		}
    30. 	}
    31. }
    32. //建堆
    33. void HeapSort(int* a, int n)
    34. {
    35. 	//建堆——a，利用向上调整建堆
    36. 	//直接插入
    37. 	/*for (int i = 1; i < n; i++)
    38. 	{
    39. 		AdjustUp(a, i);
    40. 	}*/
    41. 	//建完堆之后无序，我们排个序
    42.  
    43.  
    44. 	//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整，直到根)
    45. 	int i = 0;
    46. 	for (i = (n - 1 - 1) / 2; i >= 0; i--)
    47. 	{
    48. 		adjustdown(a, n, i);
    49. 	}
    50. 	//选数
    51. 	i = 1;
    52. 	while (i < n)
    53. 	{
    54. 		swap(&a[0], &a[n - i]);
    55. 		adjustdown(a, n - i, 0);
    56. 		i++;
    57. 	}
    58. }
    59. int main()
    60. {
    61.  
    62. 	int a[] = { 15,1,19,25,8,34,65,4,27,7 };
    63. 	HeapSort(a, sizeof(a) / sizeof(int));
    64.  
    65. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    66. 	{
    67. 		printf("%d ", a[i]);
    68. 	}
    69. 	printf("\n");
    70. 	return 0;
    71. 	
    72. }

    这里建的是小堆所以是降序 

     

    二叉树链式结构的实现

    在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。为了降低学习成本，此处手动快速创建一棵简单的二叉树，这里以简单的实现为主。后续在来讨论其创建方式：

    image-20220810163832470

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include <stdio.h>
    3. #include <assert.h>
    4. #include <stdlib.h>
    5. typedef int BTDataType;
    6.  
    7. typedef struct BinaryTreeNode
    8. {
    9. 	BTDataType data;
    10. 	struct BinaryTreeNode* left;
    11. 	struct BinaryTreeNode* right;
    12. }BTNode;
    13.  
    14.  
    15. BTNode* CreatTree()
    16. {
    17. 	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    18. 	assert(n1);
    19. 	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    20. 	assert(n2);
    21. 	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    22. 	assert(n3);
    23. 	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    24. 	assert(n4);
    25. 	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    26. 	assert(n5);
    27. 	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    28. 	assert(n6);
    29.  
    30. 	n1->data = 1;
    31. 	n2->data = 2;
    32. 	n3->data = 3;
    33. 	n4->data = 4;
    34. 	n5->data = 5;
    35. 	n6->data = 6;
    36.  
    37. 	n1->left = n2;
    38. 	n1->right = n4;
    39. 	n2->left = n3;
    40. 	n2->right = NULL;
    41. 	n3->left = NULL;
    42. 	n3->right = NULL;
    43. 	n4->left = n5;
    44. 	n4->right = n6;
    45. 	n5->left = NULL;
    46. 	n5->right = NULL;
    47. 	n6->left = NULL;
    48. 	n6->right = NULL;
    49.  
    50. 	return n1;
    51. }
    52.  
    53. int main()
    54. {
    55. 	BTNode* root = CreatTree();
    56. 	return 0;
    57. }

    这就大概搭建起了二叉树的框架，下面，来说一说其操作：

    遍历操作

    先序、中序、后序遍历递归操作： 
    1. //前序
    2. void PreOrder(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		printf("NULL ");
    7. 		return;
    8. 	}
    9. 	printf("%d ", root->data);
    10. 	PreOrder(root->left);
    11. 	PreOrder(root->right);
    12. }
    13. //中序
    14. void InOrder(BTNode* root)
    15. {
    16. 	if (root == NULL)
    17. 	{
    18. 		printf("NULL ");
    19. 		return;
    20. 	}
    21. 	InOrder(root->left);
    22. 	printf("%d ", root->data);
    23. 	InOrder(root->right);
    24. }
    25. //后续
    26. void PostOrder(BTNode* root)
    27. {
    28. 	if (root == NULL)
    29. 	{
    30. 		printf("NULL ");
    31. 		return;
    32. 	}
    33. 	PostOrder(root->left);
    34. 	
    35. 	PostOrder(root->right);
    36. 	printf("%d ", root->data);
    37. }

    我们不难发现，二叉树的遍历操作通过递归实现非常地简单，实现并不难，但是你真的理解了吗函数怎么执行的（我们这里以前序遍历为例）

    image-20220810165526334

    image-20220810165556180

     完整代码

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include <stdio.h>
    3. #include <assert.h>
    4. #include <stdlib.h>
    5. typedef int BTDataType;
    6.  
    7. typedef struct BinaryTreeNode
    8. {
    9. 	BTDataType data;
    10. 	struct BinaryTreeNode* left;
    11. 	struct BinaryTreeNode* right;
    12. }BTNode;
    13.  
    14.  
    15. BTNode* CreatTree()
    16. {
    17. 	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    18. 	assert(n1);
    19. 	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    20. 	assert(n2);
    21. 	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    22. 	assert(n3);
    23. 	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    24. 	assert(n4);
    25. 	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    26. 	assert(n5);
    27. 	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    28. 	assert(n6);
    29.  
    30. 	n1->data = 1;
    31. 	n2->data = 2;
    32. 	n3->data = 3;
    33. 	n4->data = 4;
    34. 	n5->data = 5;
    35. 	n6->data = 6;
    36.  
    37. 	n1->left = n2;
    38. 	n1->right = n4;
    39. 	n2->left = n3;
    40. 	n2->right = NULL;
    41. 	n3->left = NULL;
    42. 	n3->right = NULL;
    43. 	n4->left = n5;
    44. 	n4->right = n6;
    45. 	n5->left = NULL;
    46. 	n5->right = NULL;
    47. 	n6->left = NULL;
    48. 	n6->right = NULL;
    49.  
    50. 	return n1;
    51. }
    52. //前序
    53. void PreOrder(BTNode* root)
    54. {
    55. 	if (root == NULL)
    56. 	{
    57. 		printf("NULL ");
    58. 		return;
    59. 	}
    60. 	printf("%d ", root->data);
    61. 	PreOrder(root->left);
    62. 	PreOrder(root->right);
    63. }
    64. //中序
    65. void InOrder(BTNode* root)
    66. {
    67. 	if (root == NULL)
    68. 	{
    69. 		printf("NULL ");
    70. 		return;
    71. 	}
    72. 	InOrder(root->left);
    73. 	printf("%d ", root->data);
    74. 	InOrder(root->right);
    75. }
    76. //后续
    77. void PostOrder(BTNode* root)
    78. {
    79. 	if (root == NULL)
    80. 	{
    81. 		printf("NULL ");
    82. 		return;
    83. 	}
    84. 	PostOrder(root->left);
    85. 	
    86. 	PostOrder(root->right);
    87. 	printf("%d ", root->data);
    88. }
    89. int main()
    90. {
    91. 	BTNode* root = CreatTree();
    92. 	PreOrder(root);
    93. 	printf("\n");
    94. 	InOrder(root);
    95. 	printf("\n");
    96. 	PostOrder(root);
    97. 	return 0;
    98. }

    其他操作

    结点个数

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

     叶结点个数

    1. //叶子结点个数
    2. int TreeLeafSize(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 		return 0;
    6. 	if (root->left == NULL && root->right == NULL)
    7. 		return 1;
    8. 	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
    9. }

    高度

    1. //高度
    2.  
    3. int TreeHeighrt(BTNode* root)
    4. {
    5. 	if (root == NULL)
    6. 	{
    7. 		return 0;
    8. 	}
    9. 	int left = TreeHeighrt(root->left);
    10. 	int right = TreeHeighrt(root->right);
    11. 	return left > right ? left + 1 : right + 1;
    12. }

     

    求第K层结点个数

    1. //k层的结点数
    2. int TreeLeveL(BTNode* root, int k)
    3. {
    4. 	assert(k > 0);
    5. 	if (root == NULL)
    6. 	{
    7. 		return 0;
    8. 	}
    9. 	if (k == 1)
    10. 	{
    11. 		return 1;
    12. 	}
    13. 	return TreeLeveL(root->left, k - 1) + TreeLeveL(root->right, k - 1);
    14. }

     

    返回x所在的结点

    1. //返回X所在的结点
    2. BTNode* TreeFind(BTNode* root, BTDataType x)
    3. {
    4. 	if (root == NULL)
    5. 		return NULL;
    6. 	if (root->data == x)
    7. 		return root;
    8. 	//先去左树找
    9. 	BTNode* left = TreeFind(root->left, x);
    10. 	if (left != NULL)
    11. 		return left;
    12. 	//左树找不到，在去右树找
    13. 	BTNode* right = TreeFind(root->right, x);
    14. 	if (right != NULL)
    15. 		return right;
    16. 	return NULL;
    17. }

     

    完整代码

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include <stdio.h>
    4. #include <assert.h>
    5. #include <stdlib.h>
    6. typedef int BTDataType;
    7.  
    8. typedef struct BinaryTreeNode
    9. {
    10. 	BTDataType data;
    11. 	struct BinaryTreeNode* left;
    12. 	struct BinaryTreeNode* right;
    13. }BTNode;
    14.  
    15.  
    16. BTNode* CreatTree()
    17. {
    18. 	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    19. 	assert(n1);
    20. 	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    21. 	assert(n2);
    22. 	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    23. 	assert(n3);
    24. 	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    25. 	assert(n4);
    26. 	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    27. 	assert(n5);
    28. 	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    29. 	assert(n6);
    30.  
    31. 	n1->data = 1;
    32. 	n2->data = 2;
    33. 	n3->data = 3;
    34. 	n4->data = 4;
    35. 	n5->data = 5;
    36. 	n6->data = 6;
    37.  
    38. 	n1->left = n2;
    39. 	n1->right = n4;
    40. 	n2->left = n3;
    41. 	n2->right = NULL;
    42. 	n3->left = NULL;
    43. 	n3->right = NULL;
    44. 	n4->left = n5;
    45. 	n4->right = n6;
    46. 	n5->left = NULL;
    47. 	n5->right = NULL;
    48. 	n6->left = NULL;
    49. 	n6->right = NULL;
    50.  
    51. 	return n1;
    52. }
    53. //前序
    54. void PreOrder(BTNode* root)
    55. {
    56. 	if (root == NULL)
    57. 	{
    58. 		printf("NULL ");
    59. 		return;
    60. 	}
    61. 	printf("%d ", root->data);
    62. 	PreOrder(root->left);
    63. 	PreOrder(root->right);
    64. }
    65. //中序
    66. void InOrder(BTNode* root)
    67. {
    68. 	if (root == NULL)
    69. 	{
    70. 		printf("NULL ");
    71. 		return;
    72. 	}
    73. 	InOrder(root->left);
    74. 	printf("%d ", root->data);
    75. 	InOrder(root->right);
    76. }
    77. //后续
    78. void PostOrder(BTNode* root)
    79. {
    80. 	if (root == NULL)
    81. 	{
    82. 		printf("NULL ");
    83. 		return;
    84. 	}
    85. 	PostOrder(root->left);
    86.  
    87. 	PostOrder(root->right);
    88. 	printf("%d ", root->data);
    89. }
    90. //结点个数
    91. int TreeSize(BTNode* root)
    92. {
    93. 	if (root == NULL)
    94. 		return 0;
    95. 	return TreeSize(root->left) +
    96. 		TreeSize(root->right) + 1;
    97. }
    98. //叶子结点个数
    99. int TreeLeafSize(BTNode* root)
    100. {
    101. 	if (root == NULL)
    102. 		return 0;
    103. 	if (root->left == NULL && root->right == NULL)
    104. 		return 1;
    105. 	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
    106. }
    107. //高度
    108.  
    109. int TreeHeighrt(BTNode* root)
    110. {
    111. 	if (root == NULL)
    112. 	{
    113. 		return 0;
    114. 	}
    115. 	int left = TreeHeighrt(root->left);
    116. 	int right = TreeHeighrt(root->right);
    117. 	return left > right ? left + 1 : right + 1;
    118. }
    119. //k层的结点数
    120. int TreeLeveL(BTNode* root, int k)
    121. {
    122. 	assert(k > 0);
    123. 	if (root == NULL)
    124. 	{
    125. 		return 0;
    126. 	}
    127. 	if (k == 1)
    128. 	{
    129. 		return 1;
    130. 	}
    131. 	return TreeLeveL(root->left, k - 1) + TreeLeveL(root->right, k - 1);
    132. }
    133. //返回X所在的结点
    134. BTNode* TreeFind(BTNode* root, BTDataType x)
    135. {
    136. 	if (root == NULL)
    137. 		return NULL;
    138. 	if (root->data == x)
    139. 		return root;
    140. 	//先去左树找
    141. 	BTNode* left = TreeFind(root->left, x);
    142. 	if (left != NULL)
    143. 		return left;
    144. 	//左树找不到，在去右树找
    145. 	BTNode* right = TreeFind(root->right, x);
    146. 	if (right != NULL)
    147. 		return right;
    148. 	return NULL;
    149. }
    150.  
    151. int main()
    152. {
    153. 	BTNode* root = CreatTree();
    154. 	PreOrder(root);
    155. 	printf("\n");
    156. 	InOrder(root);
    157. 	printf("\n");
    158. 	PostOrder(root);
    159. 	printf("\n");
    160. 	printf("Size:%d\n", TreeSize(root));
    161. 	printf("LeafSize:%d\n", TreeLeafSize(root));
    162. 	printf("LeafHeighrt:%d\n", TreeHeighrt(root));
    163. 	printf("TreeLeveL:%d\n", TreeLeveL(root,3));
    164. 	printf("Tree Find:%p\n", TreeFind(root, 8));
    165.  
    166. 	return 0;
    167. }

     

     

  • 相关阅读:
    极智Coding | OpenMP 多线程使用
    IT人必看 | 2022年春招市场行情报告——高薪职业榜首是这些！
    物理学专业英语（词汇整理）--------07
    Java实现ORM第一个api-FindAll
    透过等待看数据库
    Springboot企业的信息管理系统5qs0a计算机毕业设计-课程设计-期末作业-毕设程序代做
    记一次地级市某行业专项攻防演练
    数仓4.0（可视化报表）
    Qt ffmpeg音视频转换工具
    【汇编】其他转移指令、call指令和ret指令
  • 原文地址：https://blog.csdn.net/weixin_67900732/article/details/126378925