• 一起学数据结构（8）——二叉树中堆的代码实现

    在上篇文章中提到，提到了二叉树中一种特殊的结构——完全二叉树。对于完全二叉树，在存储时，适合使用顺序存储。对于非完全二叉树，适合用链式存储。本文将给出完全二叉树的顺序结构以及相关的代码实现：

    1. 二叉树的结构建立、销毁及初始化：

    给出下图中二叉树的逻辑结构及存储结构：

    二叉树的逻辑结构只是根据想象创建出来的结构，但是在计算机存储时，并不存在逻辑结构这种形式。而是下方的存储结构。所以，以下所有操作的对象都是存储结构中连续的数组。例如需要在上述二叉树中插入一个新的结点，并且此结点存储了元素90。逻辑结构表示如下：

    对于存储结构而言，以上操作只是在已有数组的末尾插入了一个值。存储结构表示如下：
     

    所以，对于二叉树的结构建立，可以仿照之前的顺序表的结构，代码如下：

    1. typedef int HPDataType;
    2.  
    3. typedef struct Heap
    4. {
    5. 	HPDataType* a;
    6. 	int size;
    7. 	int capacity;
    8. }HP;

    其中，指针a用来后续进行连续空间的开辟，size表示数组的长度，capacity用来记录数据的容量，一旦size = capacity就需要进行扩容。

    对于二叉树的销毁与初始化，与前面的文章中方式相同，只给出代码，不做多余解释：

    二叉树的初始化如下：

    1. void HeapInit(HP* php)
    2. {
    3. 	assert(php);
    4. 	php->a = NULL;
    5. 	php->size = 0;
    6. 	php->capacity = 0;
    7. }

    二叉树的销毁如下：

    1. void HeapDestory(HP* php)
    2. {
    3. 	assert(php);
    4.  
    5. 	free(php->a);
    6. 	php->a = NULL;
    7. 	php->size = 0;
    8. 	php->capacity = 0;
    9. }

    2. HeapPush向二叉树中插入结点：

    2.1  HeapPush 向二叉树中插入结点：


    前面提到，二叉树的逻辑结构在计算机中并不存在，并且下面的代码操作都是针对二叉树的逻辑结构的。所以，向二叉树中插入元素这一操作，实际就是在数组的末尾插入一个元素。但是在插入元素之前，需要判定数组的空间是否有剩余，即满足：size < capacity。一旦size = capacity，则需要进行一次扩容。对于扩容这一步骤在之前的文章中多次使用，这里依旧直接给出代码：
     

    1. void HeapPush(HP* php, HPDataType* x)
    2. {
    3. 	assert(php);
    4.  
    5. 	if (php->size == php->capacity)
    6. 	{
    7. 		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    8. 		HPDataType* newnode = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    9. 		if (newnode == NULL)
    10. 		{
    11. 			perror("realloc");
    12. 			exit(-1);
    13. 		}
    14. 		php->a = newnode;
    15. 		php->capacity = newcapacity;
    16. 	}
    17. 	php->a[php->size] = x;
    18. 	php->size++;
    19.  
    20. }

    2.2 针对二叉树为小堆情况下，新插入元素的位置调整：

    2.2.1 结点调节的逻辑分析：

    例如对于上面给出的完全二叉树，可以看出，这个二叉树满足父结点数值<子结点数值，为小堆

     对于新结点中插入的数值，需要区分下列情况进行判定：

    1. 插入的值大于父结点中的数值56，即：


    此时插入的结点的数值为90，依旧满足子结点数值>父结点数值，因此不需要对结点的关系进行更改。

    2. 插入的值小于父结点中的数值56：

    此时插入的结点中存储的值为32。不满足小堆中父结点存储的值<子结点的关系。所以，需要对二叉树的关系进行更改，即对此时的子结点、父结点交换位置，效果如下：

    但是，如果插入的结点中存储的值，小于二叉树中任何结点的值，例如新插入结点中存储的值为1。此时调整后的二叉树的效果如下：

    对于调整父结点、子结点的关系，在上一篇文章中，根据完全二叉树的性质给出了下列的等式：

    对于一个父结点，假设其在数组中的下标为parent，则其左子结点的下标：

                                                     child1 = parent*2+1

    其右子结点的下标为：

                                                    child2 = parent*2+2

    对于任意子结点child（左、右子结点都适用），其父结点的下标可以用下面的等式表示，及：

                                                     parnet = (child-1)/2

    定义函数Adjustup用于完成对子结点、父结点关系的调整：
    前面提到，对于插入子结点，最极端的情况就是子结点中存储的值小于二叉树中任意结点的值，导致子结点需要一直与父结点进行替换，直至到根结点，即数组中下标为0的结点的位置。因此需要利用循环来控制结点的调整次数，通过上面的分析可以得出，循环的条件就是子结点对应的下标> 0，即：child> 0。

    2.2.2 Adjustup 结点调节的代码分析：
     

    对于上面的给出的向二叉树中插入元素的操作中，需要注意，在插入元素后，会对表示数组长度的size+1，所以，每次进行上述插入操作后：size-数组的实际长度=1。

    上面说到，会创建函数Adjustup函数来调整结点的位置，整个操作中，需要知道子结点、父结点的下标，因为父结点的下标可以通过上面给出的等式进行计算。所以，在对函数传递参数时，只需要传递数组的指针和插入的子结点的下标。因为插入的结点为数组的最后一位，所以，直接传递数组的实际长度，即size-1即可。

    对于交换子结点和父节点这一功能在后面需要多次适用，所以，为了方便，直接再创建一个交换函数Swap即可。交换函数对应的代码如下：
     

    1. void Swap(HPDataType* p1, HPDataType* p2)
    2. {
    3. 	HPDataType* tmp = *p1;
    4. 	*p1 = *p2;
    5. 	*p2 = tmp;
    6. }

    调整函数代码如下：

    1. void Adjustup(HPDataType* a, int child)
    2. {
    3. 	assert(a);
    4.  
    5. 	int parent = (child - 1) / 2;
    6. 	while (child > 0)
    7. 	{
    8. 		if (a[child] < a[parent])
    9. 		{
    10. 			Swap(&a[child], &a[parent]);
    11. 			child = parent;
    12. 			parent = (child - 1) / 2;
    13. 		}
    14. 		else
    15. 		{
    16. 			break;
    17. 		}
    18. 	}
    19. }

    对于上面已经给出的插入函数，在最后加上已经定义好的调整函数即可。

    为了验证前面的功能是否正常，再定义函数HeapPrint用于打印二叉树的结点。打印函数代码如下：

    1. void HeapPrint(HP* php)
    2. {
    3. 	assert(php);
    4. 	for (int i = 0; i < php->size; i++)
    5. 	{
    6. 		printf("%d ", php->a[i]);
    7. 	}
    8. }

    通过下面的代码，对插入并且调整结点的函数进行验证：

    1. #include"TreeNode.h"
    2.  
    3.  
    4. void Test1()
    5. {
    6. 	int a[] = { 9，8，7，5，4，3，2 };
    7. 	HP hp;
    8. 	HeapInit(&hp);
    9. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    10. 	{
    11. 		HeapPush(&hp, a[i]);
    12. 	}
    13. 	HeapPrint(&hp);
    14.  
    15.  
    16. 	HeapDestory(&hp);
    17.  
    18. }
    19. int main()
    20. {
    21. 	Test1();
    22. 	return 0;
    23. }

    运行结果如下：

    运行结果显示的是二叉树的存储结构，将上述存储结构转为逻辑结构，即：

         满足小堆的定义。         

    3.删除二叉树中的结点：                     

    3.1 删除二叉树中结点逻辑分析：           

    给定下列的二叉树：

    对于二叉树的删除结点而言，删除尾部结点的意义并不大，所以，一般的删除结点都是指删除二叉树的根结点。

    前面提到，对于二叉树的操作，是作用在二叉树的存储结构上，上图二叉树的存储结构如下：

     对于一个连续的数组，删除头结点的方式可以是让后面的元素依次向前覆盖。但是对于二叉树而言，向前覆盖来删除头结点的方式可能会造成二叉树的结构错误，例如，利用覆盖的方法删除了头结点的二叉树的逻辑结构如下：

    调整过后的二叉树，将不再满足上方的小堆关系，即子结点存储的数据>父结点存储的数据。并且，再顺序表的文章中就提到，对于依次覆盖这种方法，时间复杂度为O(N),效率并不高。

    为了解决上面的问题，给定下方的方法来完成对于根结点的删除：

    首先，将二叉树的尾结点和根结点替换，效果如下：

    对于二叉树的存储结构，可以随机访问数组的任意下标所对应的位置，并且尾插和尾删的效率为O(1)，所以，直接将尾结点删除，即：

    通过上述方法删除了二叉树的原根结点之后，此时二叉树的子树并没有受到影响，依旧是小堆，删除了二叉树的原根结点后，需要对二叉树中的结点的位置进行调整。

    在调整位置时，需要先比较结点的子结点所存储的数据的大小，例如根节点的子结点分别存储了数据5,3,由于根节点存储的数据4大于右子结点所存储的数据33，因此两个结点交换位置。

    需要注意，此处的调整并不同于上方给出的调整函数Adjustup。上方的函数调整的对象是针对于新插入的尾结点。调整的方向是总体向上的，本处的调整是针对于置换完后的新的根结点，总体的方向是自上而下的，因此，此处再构建另一个调整函数Adjustdown。

    3.2 代码分析——Adjustdown 删除二叉树中结点：

    对于调整函数Adjustdown，首先判断非叶子结点的子结点的大小关系，并找到较小的一个。可以先假设一个结点为小结点（此处默认左子结点为小结点），对于左子结点的下标，可以通过上面的等式

                                                            child=parent∗2+1

    得出，对于右子结点，可以表示为 child+1，再对两个结点中数据的大小进行判定，如果a[child+1]<a[child]，则表示右子结点为较小的结点，让child+1,反之不变。此处需要注意一种特殊情况，及：

    此时，存储数据3的结点只有左结点，没有右结点，child+1会引起数组的越界访问，所以，在进行结点大小判定之前，需要判定child+1<size。

    找到左、右子结点中较小的一个后，对父结点 、子结点的大小进行判定，如果子结点中存储的数据小于<父结点中的数据，则交换两个结点的位置。

    对于交换这一过程，最好的情况下是交换一次，最坏的情况下是交换到叶子结点。所以，判断循环是否进行的条件便是判断child的大小是否<size。对应代码如下：

    1. void Adjustdown(HPDataType* a, int size, int parent)
    2. {
    3. 	int child = parent * 2 + 1;
    4. 	while ( child < size)
    5. 	{
    6. 		if (child+1 < size && a[child + 1] < a[child])
    7. 		{
    8. 			child++;
    9. 		}
    10. 		if (a[parent] > a[child])
    11. 		{
    12. 			Swap(&a[parent], &a[child]);
    13. 			parent = child;
    14. 			child = parent * 2 + 1;
    15. 		}
    16. 		else
    17. 		{
    18. 			break;
    19. 		}
    20. 	}
    21. }

    3.3 代码分析——HeapPop 删除二叉树中的结点：

    删除结点一共需要下列步骤：

    1. 交换首位结点

    2. 删除尾结点

    3.通过调整函数对结点的位置进行调整

    对应代码如下：

    1. void HeapPop(HP* php)
    2. {
    3. 	assert(php);
    4. 	assert(php->size > 0);
    5.  
    6. 	Swap(&php->a[0], &php->a[php->size - 1]);
    7. 	php->size--;
    8.  
    9. 	Adjustdown(php->a, php->size, 0);
    10.  
    11. }

    4. 返回根结点所存储的数据：

    原理较为简单，只给出代码，不做解释：

    1. HPDataType HeapTop(HP* php)
    2. {
    3. 	assert(php);
    4. 	assert(php->size > 0);
    5.  
    6. 	return php->a[0];
    7. }

    5. 探空：

    原理较为简单，只给出代码，不做解释：

    1. bool Heapbool(HP* php)
    2. {
    3. 	assert(php);
    4.  
    5. 	return php->size == 0;
    6. }

    6. 代码总览：

    头文件如下：

    1. #pragma once
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8. typedef int HPDataType;
    9.  
    10. typedef struct Heap
    11. {
    12. 	HPDataType* a;
    13. 	int size;
    14. 	int capacity;
    15. }HP;
    16.  
    17.  
    18. void HeapInit(HP* php);
    19.  
    20. void HeapDestory(HP* php);
    21.  
    22. void HeapPush(HP* php, HPDataType* x);
    23.  
    24. void Adjustup(HPDataType* a, int child);
    25.  
    26. void Swap(HPDataType* p1, HPDataType* p2);
    27.  
    28. void HeapPrint(HP* php);
    29.  
    30. void Adjustdown(HPDataType* a, int size, int parent);
    31.  
    32. void HeapPop(HP* php);
    33.  
    34. HPDataType HeapTop(HP* php);
    35.  
    36. bool HeapEmpty(HP* php);

    TreeNode.c文件如下：

    1. #include"TreeNode.h"
    2.  
    3. void HeapInit(HP* php)
    4. {
    5. 	assert(php);
    6. 	php->a = NULL;
    7. 	php->size = 0;
    8. 	php->capacity = 0;
    9. }
    10.  
    11. void HeapDestory(HP* php)
    12. {
    13. 	assert(php);
    14.  
    15. 	free(php->a);
    16. 	php->a = NULL;
    17. 	php->size = 0;
    18. 	php->capacity = 0;
    19. }
    20. void HeapPrint(HP* php)
    21. {
    22. 	assert(php);
    23. 	for (int i = 0; i < php->size; i++)
    24. 	{
    25. 		printf("%d ", php->a[i]);
    26. 	}
    27. }
    28.  
    29. void Swap(HPDataType* p1, HPDataType* p2)
    30. {
    31. 	HPDataType* tmp = *p1;
    32. 	*p1 = *p2;
    33. 	*p2 = tmp;
    34. }
    35.  
    36. //新插入子结点向上升，
    37. void Adjustup(HPDataType* a, int child)
    38. {
    39. 	assert(a);
    40.  
    41. 	int parent = (child - 1) / 2;
    42. 	while (child > 0)
    43. 	{
    44. 		if (a[child] > a[parent])
    45. 		{
    46. 			Swap(&a[child], &a[parent]);
    47. 			child = parent;
    48. 			parent = (child - 1) / 2;
    49. 		}
    50. 		else
    51. 		{
    52. 			break;
    53. 		}
    54. 	}
    55. }
    56.  
    57. void HeapPush(HP* php, HPDataType* x)
    58. {
    59. 	assert(php);
    60.  
    61. 	if (php->size == php->capacity)
    62. 	{
    63. 		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    64. 		HPDataType* newnode = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    65. 		if (newnode == NULL)
    66. 		{
    67. 			perror("realloc");
    68. 			exit(-1);
    69. 		}
    70. 		php->a = newnode;
    71. 		php->capacity = newcapacity;
    72. 	}
    73. 	php->a[php->size] = x;
    74. 	php->size++;
    75.  
    76. 	Adjustup(php->a, php->size-1);
    77. }
    78. //健小堆
    79. void Adjustdown(HPDataType* a, int size, int parent)
    80. {
    81. 	int child = parent * 2 + 1;
    82. 	while ( child < size)
    83. 	{
    84. 		//找出较小的结点
    85. 		if (child+1 < size && a[child + 1] > a[child])
    86. 		{
    87. 			child++;
    88. 		}
    89. 		if (a[parent] < a[child])
    90. 		{
    91. 			Swap(&a[parent], &a[child]);
    92. 			parent = child;
    93. 			child = parent * 2 + 1;
    94. 		}
    95. 		else
    96. 		{
    97. 			break;
    98. 		}
    99. 	}
    100. }
    101.  
    102.  
    103. void HeapPop(HP* php)
    104. {
    105. 	assert(php);
    106. 	assert(php->size > 0);
    107.  
    108. 	Swap(&php->a[0], &php->a[php->size - 1]);
    109. 	php->size--;
    110.  
    111. 	Adjustdown(php->a, php->size, 0);
    112.  
    113. }
    114.  
    115. HPDataType HeapTop(HP* php)
    116. {
    117. 	assert(php);
    118. 	assert(php->size > 0);
    119.  
    120. 	return php->a[0];
    121. }
    122.  
    123. bool HeapEmpty(HP* php)
    124. {
    125. 	assert(php);
    126.  
    127. 	return php->size == 0;
    128. }
    129.

    Test.c文件：

    1. int main()
    2. {
    3. 	Test1();
    4. 	int a[] = { 70,65,100,32,50,60 };
    5. 	HPqort(a, sizeof(a) / sizeof(int));
    6. 	printf("\n");
    7. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    8. 	{
    9. 		printf("%d ", a[i]);
    10. 	}
    11. 	return 0;
    12. }

  • 相关阅读:
    ChatGPT桌面客户端支持gpt4模型，附使用说明
    90%的软件测试从业者，努力的方向都错了...你呢？
    JS数组方法map 和 forEach 的区别
    微信小程序手写文件解决日期少一天且格式无法切割问题
    刷爆力扣之公平的糖果交换
    黑客（网络安全）技术自学30天
    双节履带机械臂小车实现蓝牙遥控功能
    NEON优化：性能优化经验总结
    Java之网络编程
    MySQL 5与MySQL 8版本差异及MySQL 8的新功能
  • 原文地址：https://blog.csdn.net/2301_76836325/article/details/133089913