数据结构7——二叉树的顺序结构以及堆的实现

在上篇文章数据结构6——树与二叉树中，我们了解了树和二叉树的概念，接着上篇文章，在本篇文章中我们学习二叉树顺序结构的实现。

---

---

目录

1. 二叉树的顺序存储结构

2. 堆的概念及结构

1. 堆的概念

2. 堆的结构

3. 堆的实现

1. 堆节点

2. 交换节点

3. 打印

4. 堆的插入

向上调整：

插入：

5. 堆的删除

向下调整：

删除：

6. 初始化

7. 销毁

验证：

源代码：

Heap.h:

Heap.c:

test.c:

---

1. 二叉树的顺序存储结构

二叉树一般可以使用两种结构存储，一种是顺序结构，一种是链式结构。本篇文章我们先来研究二叉树的顺序存储，下篇文章详解二叉树的链式存储。

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

如图： 完全二叉树顺序存储：

非完全二叉树顺序存储：

2. 堆的概念及结构

1. 堆的概念

简单来说，堆除了是一棵完全二叉树之外，还要满足堆序性。

堆中每个节点的值都大于等于其子节点的值，根节点是堆中最大的元素，这样的堆称为最大堆或大根堆；

相反的，堆中每个节点的值都小于等于其子节点的值，根节点是堆中最小的元素，这样的堆称为最小堆或小根堆；

2. 堆的结构

3. 堆的实现

（本篇文章只实现最小堆，最大堆与最小堆是相同的道理）

1. 堆节点

typedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2. 交换节点

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

3. 打印

//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

4. 堆的插入

可是现在堆属性并不满足，因为30在5的上面，这是一个最小堆，我们需要将小的数字在上面。

为了恢复堆属性，我们需要交换30和5：

可是现在仍旧没有满足最小堆的堆属性，所以还需要交换10和5：

此时才得到了最小堆。

因此在插入数据后每次都要进行向上调整，于是向上调整的实现为：

向上调整：

//向上调整
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 = (parent - 1) / 2;}else{break;}}
}

插入：

//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//检查是否扩容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//传数组的最后一个数据
}

5. 堆的删除

由于堆顶是最大或最小元素，为了满足堆属性，所以堆中每次只能删除堆顶元素，一般的做法是先将堆顶元素与数组末尾元素先交换，再删除末尾元素。

可是现在40在了堆顶，反而成了最大的元素，并不满足最小堆，这时就需要向下调整：

每次删除都要调整，所以向下调整的具体实现为：

向下调整：

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续往下调整parent = child;child = parent * 2 + 1;}else{break;}}
}

删除：

//删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}

6. 初始化

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

7. 销毁

//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

验证：

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}

---

---

源代码：

Heap.h:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//初始化
void HeapInit(HP* php);//向上调整
void AdjustUP(HPDataType* a, int child);
//插入
void HeapPush(HP* php, HPDataType x);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//删除
void HeapPop(HP* php);//销毁
void HeapDestroy(HP* php);

Heap.c:

#include "Heap.h"//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}//向上调整
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 = (parent - 1) / 2;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//检查是否扩容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//传数组的最后一个数据
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续往下调整parent = child;child = parent * 2 + 1;}else{break;}}
}//删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

test.c:

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}