前言
在编程的世界里，数据结构是构建高效、可靠软件大厦的基石。而当我们谈论起那些既经典又充满活力的数据结构时，堆无疑是一个不可忽视的存在。然而，在深入了解堆之前，让我们先回溯到其根源——树，这个在计算机科学中同样占据核心地位的数据结构。
一、树
1.树的概念与结构
与线性表不同，树是一种非线性的数据结构，它是由n（n>=0）个节点所构成的有层次关系的数据结构。它的层次关系看起来就像是一棵倒挂的树：
2.树的相关术语
相比于线性表，树的逻辑结构较为复杂，所以出现了一些常用的术语，便于我们对树的结构进行分析。接下来我们结合上图来一一介绍这些术语及其含义。
1.根节点：就像树根一样，树中所有节点都是从节点A发出的，这样的节点叫做根节点。（一棵树只有一个根节点）
2.边：连接两个节点的线叫做树的边（一棵有N个节点的树具有N-1条边）。
3.父节点/双亲节点：对于一个节点，父节点/双亲节点可以理解为与其连接的上面的节点。如图所示，B,C,D,E的父节点都是A。（除根节点之外，所有节点有且仅有一个父节点）
4.子节点/孩子节点：与父节点相反，你是我的父节点，那么我就是你的子节点。对于节点A，则B,C,D,E都是它的子节点。
5.节点的度：一个节点有多少个子节点，那么它的度就是多少。例如：节点A的度为4，节点B的度为3，节点C的度为0。
6.树的度：所有节点的度的最大值叫做树的度。如图，这颗树的度就是4。
7.叶子节点/终端节点：度为0的节点称之为叶子节点/终端节点。如图，这颗树中的叶子节点为：F,G,H,C,L,M,J,K。
8.分支节点/非终端节点：度不为0的节点称之为分支节点/非终端节点。除了叶子节点外，其他节点都是分支节点。
9.兄弟节点：具有相同父节点的节点互称为兄弟节点。例如，B,C,D,E是兄弟节点，F,G,H是兄弟节点。
10.节点的层次：由根节点开始，根节点为第一层；它的所有子节点为第二层；子节点的子节点为第三层；以此类推。
11.树的高度/深度：节点的最大层次叫做树的高度/深度。如图，这颗树的高度为4。
12.节点的祖先：对于一个节点，从根节点开始到该节点所经的所有节点（除该节点本身）都叫做该节点的祖先。例如：A,B是G的祖先，A,D,I是L的祖先。
13.路径：从任意节点开始，沿着边到达任意其他节点所经过的节点构成的序列叫做路径。例如：A到L的路径为：A-D-I-L。
14.子孙：与祖先相反，你是我的祖先，我就是你的子孙。例如，F,G,H是B的子孙；所有除A外的节点都是A的子孙。
15.森林：由m（m>0）棵互不相交的树（不同树之间没有相交节点）所构成的集合叫做森林。如图，如果将根节点A删除，剩下的子树组成的部分就是森林。
注意：树形结构当中，子树之间不能有相交的情况，否则就不是树。
如图，以下结构都不是树型结构：
3.树的表示方法
一般我们表示树时，会在节点中定义指向其子节点的指针，但是由于有些树各个节点的度不一定相同，定义的指针数也无法确定，所以就出现了孩子兄弟表示法。
顾名思义，孩子兄弟表示法就是定义指向子节点的指针和兄弟节点的指针：
struct TreeNode { int data;//数据域 struct TreeNode* child;//指向孩子的指针 struct TreeNode* brother;//指向兄弟的指针 };
这样只需要指向节点的其中一个子节点，然后令其指向更多的兄弟节点，这样就能够表示一个节点的所有子节点了。我们画图表示一下该结构：
4.树型结构的实际应用场景
树型结构在计算机中是被广泛使用的。例如：操作系统中文件根目录与子目录之间的关系、数据库的索引、编译器中的语法树、网络路由协议的构成等。在这些实例中，树形结构对文件的访问、程序的运行效率有很大的帮助。
二、二叉树
1.二叉树的概念与结构
在树形结构当中，最常用的一种数据结构就是二叉树。所谓二叉树，指的是每一个节点的度不超过2的树。
一棵二叉树可以分为根节点、左子树、右子树，对于每一棵子树，也可以这样细分，直到其子树不存在为止。这里要注意：左右子树的次序不能颠倒。
2.二叉树的性质
二叉树有以下基本性质：
1.一棵非空二叉树的第
层最多有
个节点。
2.高度为
的二叉树的最大节点个数是
。
3.对于任何一颗非空二叉树，设其度为2的节点个数为
，度为1的节点个数为
，叶子节点个数为
，边数为
，则有
、
、
。
3.满二叉树
满二叉树是一种特殊的二叉树。它的定义如下：对于一个二叉树，如果它每一层的节点数都达到最大值（ 
），它就是一个满二叉树。如图所示，这是一棵高度为3的满二叉树：
满二叉树的性质：具有 
个节点的满二叉树的高度 
。
4.完全二叉树
完全二叉树也是一种特殊的二叉树。通俗的讲，一个完全二叉树需要满足两个条件：
1.对于一棵高度为N的二叉树，第1层到第N-1层的节点数均达到最大值。
2.最后一层的节点必须是从左到右连续排列的状态。
如图，这就是一个完全二叉树：
可以看出，在最后一层，H、I、J三个节点是从左到右连续排列的状态，而其他层的节点数均达到了最大值。当然，由于满二叉树满足完全二叉树的条件，所以它是一种特殊的完全二叉树。
完全二叉树的性质：具有 
个节点的完全二叉树的高度 
。
5.二叉树的存储形式
一般来讲，二叉树的存储形式有两种：顺序存储结构和链式存储结构。
5.1 顺序存储结构
所谓顺序存储，就是用数组来存储二叉树的数据。我们画图表示一下数组存储二叉树数据的形式：
对比两图可以看出，对于非完全二叉树，它的顺序存储会浪费一定的空间，所以完全二叉树更适合顺序存储。
通常情况下，我们将采用顺序存储结构存储的完全二叉树叫做堆。
5.2 链式存储结构
与链表相同，链式存储结构是指用节点和指针来表示数据元素之间的逻辑关系。通常情况下，二叉树的链式存储结构分为二叉链和三叉链。二叉链的指针域包含左右孩子节点的地址；三叉链的指针域比二叉链多一个指向父节点的指针。
//二叉链 struct BTreeNode { int data; struct BTreeNode* leftchild; struct BTreeNode* rightchild; };
//三叉链 struct BTreeNode { int data; struct BTreeNode* leftchild; struct BTreeNode* rightchild; struct BTreeNode* parent; };
三、二叉树顺序结构--堆
之前我们提到，采用顺序存储结构存储的完全二叉树叫做堆。接下来我们深入学习堆并且尝试实现它的一些功能。
1.堆的结构特点和性质
堆除了满足完全二叉树的性质之外，它还有一些自身的特性。我们首先从堆的分类开始讲起。
堆可以被分为小堆和大堆。它们的区别如下：
1.小堆（小根堆）：根节点（堆顶）的值总是整个堆中的最小值，且堆中每个节点的值都小于等于其子节点的值。
2.大堆（大根堆）：根节点（堆顶）的值总是整个堆中的最大值，且堆中每个节点的值都大于等于其子节点的值。
注：堆的节点只是满足小于等于（大于等于）其子节点的值，而两兄弟节点之间的大小是没有要求的。
综上所述，堆具有以下性质：
1.堆总是一棵完全二叉树。
2.堆中的任意节点（非叶子节点）的值总是 小于等于/大于等于 其子节点的值。
由于堆的逻辑结构是完全二叉树，但是其物理结构是顺序存储的，为了体现其逻辑结构，有一套堆中节点关系的计算公式如下（重要）：
设堆中具有n个节点，按照数组下标
对应每一个节点，则对于下标
的节点：
1.其父节点的下标为：
( i 为0的节点无父节点)
2.其左孩子节点的下标为：
(孩子下标超过n-1，说明没有孩子节点)
3.其 右孩子节点 的下标为：
(孩子下标超过n-1，说明没有孩子节点)
2.堆的实现
2.1 堆的结构定义
看完了这么多的理论知识之后，我们正式开始实现一个小堆。由于堆的底层是数组，它的结构定义如下：
typedef int HPDataType; //定义堆的结构 typedef struct Heap { HPDataType* arr;//数组起始指针 int capacity;//堆的空间大小 int size;//堆中有效数据个数 }HP;
2.2 方法的声明
以下是堆的常用方法声明：
//初始化 void HPInit(HP* php); //销毁 void HPDestroy(HP* php); //判空 bool HPEmpty(HP* php); //辅助函数交换两数据 void Swap(HPDataType* x, HPDataType* y); //堆的向上调整 void AdjustUp(HPDataType* arr, int child); //堆的向下调整 void AdjustDown(HPDataType* arr, int parent, int n); //插入 void HPPush(HP* php, HPDataType n); //删除 void HPPop(HP* php); //取堆顶数据 HPDataType HPTop(HP* php);
2.3 方法的实现
2.3.1 初始化
由于堆的底层是数组，初始化和销毁时的操作与顺序表相同。
//初始化 void HPInit(HP* php) { assert(php);//防止传空指针 php->arr = NULL; php->capacity = php->size = 0; }
2.3.2 销毁
//销毁 void HPDestroy(HP* php) { assert(php);//防止传空指针 if (php->arr)//防止多次释放空间 { free(php->arr); } php->arr = NULL; php->capacity = php->size = 0; }
2.3.3 判空
当堆中有效数据为0时，堆即为空。
//判空 bool HPEmpty(HP* php) { assert(php); return php->size == 0; }
2.3.4 辅助函数交换两数据
这是一个辅助函数，用于之后插入和删除时交换堆中的数据元素。
//辅助函数交换两数据 void Swap(HPDataType* x, HPDataType* y) { HPDataType tmp = *x; *x = *y; *y = tmp; }
2.3.5 插入
一般情况下，我们进行插入操作时，是从数组尾部进行插入的。由于我们实现的是小堆，小堆的非叶子节点要小于等于其子节点的值，当我们从数组末尾插入数据时，新的元素可能会小于其父节点的值，就不满足堆的条件了。所以在数据插入之后，要对该数据进行向上调整，按照其值将其放在合适的位置。以下是一个元素进行向上调整的示例过程：
接下来，我们尝试实现插入操作和向上调整算法：
//插入 void HPPush(HP* php, HPDataType n) { assert(php); if (php->capacity == php->size)//空间已满，需要增容 { int NewCapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType));//申请内存空间 if (tmp == NULL)//内存申请失败，直接退出程序 { perror("realloc"); exit(1); } php->arr = tmp;//将申请好的空间赋值给起始指针 php->capacity = NewCapacity;//设置新的空间大小 } php->arr[php->size] = n;//插入新元素 //此时的size没有自增，表示新元素的下标 AdjustUp(php->arr, php->size);//向上调整 php->size++;//调整之后，元素个数+1 }
//堆的向上调整 void AdjustUp(HPDataType* arr, int child) { int parent = (child - 1) / 2;//先找到父节点的下标 while (parent >= 0)//父节点下标<0时，已越界 { if (arr[child] < arr[parent])//若孩子节点的值小于父节点的值，就需要调整 { Swap(&arr[child], &arr[parent]);//交换两元素 //此时，新的孩子节点跑到了原来父节点的位置 child = parent; parent = (child - 1) / 2;//确定新的父节点 } else//其他情况说明已经调整完成，退出循环 { break; } } }
2.3.6 删除
堆在进行删除操作时，一般情况是在堆顶出数据的。如果我们直接删除堆顶数据，剩下的部分就不满足堆的条件，并且重新建堆十分麻烦。所以我们首先需要将堆顶数据A与数组最后一个数据B进行交换，然后删除数据A，再针对数据B进行向下调整。以下是数据删除和向下调整的示例：
现在，我们尝试实现删除操作和向下调整算法：
//删除 void HPPop(HP* php) { assert(php); assert(!HPEmpty(php));//确保堆不为空 Swap(&php->arr[0], &php->arr[php->size - 1]);//交换堆顶元素和最后一个数据 php->size--;//空间大小-1，相当于将最后一个数据删除 //此时的size已经自减，表示有效数据个数 AdjustDown(php->arr, 0, php->size); }
//堆的向下调整 void AdjustDown(HPDataType* arr, int parent, int n) { int child = parent * 2 + 1;//先找到左孩子的下标 while (child < n)//当孩子节点下标>=n时，已越界 { //若右孩子存在，则将左孩子和右孩子进行比较，找到更小的子节点便于调整交换，保证小堆的特性 if (child + 1 < n && arr[child] > arr[child + 1]) { child++; } if (arr[parent] > arr[child])//父节点的值大于子节点，需要调整 { Swap(&arr[parent], &arr[child]); //此时父节点跑到了孩子节点的位置 parent = child; child = parent * 2 + 1;//确定新的孩子节点 } else//其他情况，调整完成退出循环 { break; } } }
2.3.7 取堆顶数据
由于堆存放在数组当中，堆顶数据即是数组的首元素，直接返回即可。
//取堆顶数据 HPDataType HPTop(HP* php) { assert(php && !HPEmpty(php)); return php->arr[0]; }
2.4 程序全部代码
程序全部代码如下：
typedef int HPDataType; //定义堆的结构 typedef struct Heap { HPDataType* arr;//数组起始指针 int capacity;//堆的空间大小 int size;//堆中有效数据个数 }HP; //初始化 void HPInit(HP* php); //销毁 void HPDestroy(HP* php); //判空 bool HPEmpty(HP* php); //辅助函数交换两数据 void Swap(HPDataType* x, HPDataType* y); //堆的向上调整 void AdjustUp(HPDataType* arr, int child); //堆的向下调整 void AdjustDown(HPDataType* arr, int parent, int n); //插入 void HPPush(HP* php, HPDataType n); //删除 void HPPop(HP* php); //取堆顶数据 HPDataType HPTop(HP* php); //初始化 void HPInit(HP* php) { assert(php);//防止传空指针 php->arr = NULL; php->capacity = php->size = 0; } //销毁 void HPDestroy(HP* php) { assert(php);//防止传空指针 if (php->arr)//防止多次释放空间 { free(php->arr); } php->arr = NULL; php->capacity = php->size = 0; } //判空 bool HPEmpty(HP* php) { assert(php); return php->size == 0; } //辅助函数交换两数据 void Swap(HPDataType* x, HPDataType* y) { HPDataType tmp = *x; *x = *y; *y = tmp; } //堆的向上调整 void AdjustUp(HPDataType* arr, int child) { int parent = (child - 1) / 2;//先找到父节点的下标 while (parent >= 0)//父节点下标<0时，已越界 { if (arr[child] < arr[parent])//若孩子节点的值小于父节点的值，就需要调整 { Swap(&arr[child], &arr[parent]);//交换两元素 //此时，孩子节点跑到了原来父节点的位置 child = parent; parent = (child - 1) / 2;//确定新的父节点 } else//其他情况说明已经调整完成，退出循环 { break; } } } //堆的向下调整 void AdjustDown(HPDataType* arr, int parent, int n) { int child = parent * 2 + 1;//先找到左孩子的下标 while (child < n)//当孩子节点下标>=n时，已越界 { //若右孩子存在，则将左孩子和右孩子进行比较，找到更小的子节点便于调整交换，保证小堆的特性 if (child + 1 < n && arr[child] > arr[child + 1]) { child++; } if (arr[parent] > arr[child])//父节点的值大于子节点，需要调整 { Swap(&arr[parent], &arr[child]); //此时父节点跑到了孩子节点的位置 parent = child; child = parent * 2 + 1;//确定新的孩子节点 } else//其他情况，调整完成退出循环 { break; } } } //插入 void HPPush(HP* php, HPDataType n) { assert(php); if (php->capacity == php->size)//空间已满，需要增容 { int NewCapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType));//申请内存空间 if (tmp == NULL)//内存申请失败，直接退出程序 { perror("realloc"); exit(1); } php->arr = tmp;//将申请好的空间赋值给起始指针 php->capacity = NewCapacity;//设置新的空间大小 } php->arr[php->size] = n;//插入新元素 //此时的size没有自增，表示新元素的下标 AdjustUp(php->arr, php->size);//向上调整 php->size++;//调整之后，元素个数+1 } //删除 void HPPop(HP* php) { assert(php); assert(!HPEmpty(php));//确保堆不为空 Swap(&php->arr[0], &php->arr[php->size - 1]);//交换堆顶元素和最后一个数据 php->size--;//空间大小-1，相当于将最后一个数据删除 //此时的size已经自减，表示有效数据个数 AdjustDown(php->arr, 0, php->size); } //取堆顶数据 HPDataType HPTop(HP* php) { assert(php && !HPEmpty(php)); return php->arr[0]; }
总结
今天我们学习了树、二叉树的概念，基本结构，以及二叉树顺序结构--堆的实现。由堆的特性所创造的排序算法--堆排序是一种效率很高的排序算法，在各种领域广泛使用。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
