引言

在计算机科学中，二叉树是一种重要的数据结构，广泛应用于各种算法和程序设计中。本文将探讨二叉树的顺序实现，特别是堆的实现方式。

一、树

1.1树的概念与结构

• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

1.2树的基本术语 

1.3树的表示法

struct TreeNode{struct Node* child; 	// 最左边的孩子结点struct Node* brother; 	// 指向其右边的下一个兄弟结点int data; 				// 结点中的数据域
};

1.4树形结构实际运⽤场景

二、二叉树 

2.1二叉树的概念与结构

总结：

1. ⼆叉树不存在度⼤于 2 的结点

2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

2.2二叉树的基本术语

• 根节点（root node） ：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 节点所在的 层（level） ：从顶至底递增，根节点所在层为 1 。
• 节点的度（degree） ：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height） ：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth） ：从根节点到该节点所经过的边的数量。
• 节点的高度（height） ：从距离该节点最远的叶节点到该节点所经过的边的数量。

  

 2.3特殊二叉树

1.完美二叉树(满二叉树)

2.3.2 链式结构

三、实现顺序结构二叉树 

3.2堆的实现

我们以小堆为例进行实现：

3.2.1存储结构

二叉树的顺序存储通常使用数组来实现。对于一个节点在数组中的索引 i，可以通过以下方式找到其父节点和子节点的索引：

• 父节点：(i - 1) / 2（取整）
• 左子节点：2 * i + 1
• 右子节点：2 * i + 2

typedef struct Heap
{DataType *arr;int size;int capacity;
}HP;

这里可以看到堆的底层结构和动态顺序表一样。

3.2.2相关操作

1.初始化

//初始化
void HPInit(HP* p)
{assert(p);p->arr = NULL;p->size = p->capacity = 0;
}

2.销毁 

//销毁
void HPDestory(HP* p)
{assert(p);if (p->arr){free(p->arr);}p->arr = NULL;p->size = p->capacity = 0;
}
Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}

3.向上调整

💡 向上调整算法

• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后

• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

//堆的向上调整
void AdjustUp(DataType* arr, int child)
{int parent = (child - 1) / 2;//父节点while(child>0)//注意child可能会被调整到根节点，这时候就不能再调整了{if (arr[child] < arr[parent])//如果条件语句不成立，就说明堆已经成型{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;//循环以上步骤}else{break;}}
}

4.堆的插⼊

将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆。

//插入
void HPPush(HP* p, DataType x)
{assert(p);if (p->size == p->capacity)//判断空间是否足够{//扩容int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));if (tmp == NULL) {perror("realloc fail!");exit(1);}p->arr = tmp;p->capacity = NewCap;} p->arr[p->size] = x;AdjustUp(p->arr, p->size);++p->size;
}

5.向下调整法

💡 向下调整算法

• 将堆顶元素与堆中最后⼀个元素进⾏交换

• 删除堆中最后⼀个元素

• 将堆顶元素向下调整到满⾜堆特性为⽌

向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

//堆的向下调整
void AdjustDwon(DataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n) {//寻找左右孩子最小的那个if (child + 1 < n && arr[child] > arr[child + 1]){child++;}//这里和向上调整就一样了，比较，交换，循环if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

 6.堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏向下调整算法。

//删除,出堆顶数据
void HPPop(HP* p)
{assert(p && p->size);Swap(&p->arr[0], &p->arr[p->size - 1]);--p->size;AdjustDwon(p->arr, 0, p->size);
}

7.判空

//判空
bool HPEmpty(HP* p)
{assert(p);return p->size == 0;
}

8.返回堆顶元素

//返回堆顶元素
DataType HPTop(HP* p)
{assert(p && p->size);return p->arr[0];
}

四、完整代码

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//定义堆的结构--数组
typedef int DataType;
typedef struct Heap//小堆为例
{DataType *arr;int size;int capacity;
}HP;
//初始化
void HPInit(HP* p);
//销毁
void HPDestory(HP* p);
//插入
void HPPush(HP* p,DataType x);
//删除，出堆顶数据
void HPPop(HP* p);
//判空
bool HPEmpty(HP* p);
//返回堆顶元素
DataType HPTop(HP* p);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
//初始化
void HPInit(HP* p)
{assert(p);p->arr = NULL;p->size = p->capacity = 0;
}
//销毁
void HPDestory(HP* p)
{assert(p);if (p->arr){free(p->arr);}p->arr = NULL;p->size = p->capacity = 0;
}
Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//堆的向上调整
void AdjustUp(DataType* arr, int child)
{int parent = (child - 1) / 2;//父节点while(child>0)//注意child可能会被调整到根节点，这时候就不能再调整了{if (arr[child] < arr[parent])//如果条件语句不成立，就说明堆已经成型{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;//循环以上步骤}else{break;}}
}
//插入
void HPPush(HP* p, DataType x)
{assert(p);if (p->size == p->capacity)//判断空间是否足够{//扩容int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));if (tmp == NULL) {perror("realloc fail!");exit(1);}p->arr = tmp;p->capacity = NewCap;} p->arr[p->size] = x;AdjustUp(p->arr, p->size);++p->size;
}
//堆的向下调整
void AdjustDwon(DataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n) {//寻找左右孩子最小的那个if (child + 1 < n && arr[child] > arr[child + 1]){child++;}//这里和向上调整就一样了，比较，交换，循环if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//删除,出堆顶数据
void HPPop(HP* p)
{assert(p && p->size);Swap(&p->arr[0], &p->arr[p->size - 1]);--p->size;AdjustDwon(p->arr, 0, p->size);
}
//判空
bool HPEmpty(HP* p)
{assert(p);return p->size == 0;
}
//返回堆顶元素
DataType HPTop(HP* p)
{assert(p && p->size);return p->arr[0];
}

main.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
void test01()
{HP hp;HPInit(&hp);int arr[] = { 17,20,10,13,19,15 };for (int i = 0; i < 6; i++){HPPush(&hp, arr[i]);}//HPPop(&hp);while (!HPEmpty(&hp)){printf("%d-", HPTop(&hp));HPPop(&hp);}HPDestory(&hp);
}
int main()
{test01();return 0;
}

五、总结

通过顺序实现的方式，我们可以高效地存储和操作二叉树。堆作为一种特殊的二叉树，提供了快速的插入和删除操作，非常适合优先队列的实现。在许多应用场景中，如任务调度、图算法等，堆结构都发挥着重要作用。

希望本文能够帮助你理解二叉树的顺序实现及堆的基本操作。继续探索数据结构的世界，会发现更多有趣的应用和挑战！