数据结构-二叉树_堆
一. 树的概念
树在我们的日常生活中随处可见，人们将生活中的树转换成存放数据的树形结构，就成了数据结构中的“树”。
如上图所示，自然界中的树有树根，有树枝，有树叶，当我们将其转换成树形结构时， 只需将其倒转过来，将树根，树枝的岔口，树枝的顶部画一个圆，就成了一个完美的树形结构：
树型结构是一种非线性的数据结构，它是由N（N>0）个结点组成的一个数据的集合，我们称这种数据结构为“树”。
树的根部结点称为根结点，根结点是没有前驱结点的，
除了根结点外，其余结点被分成互不相交的集合，
每个集合都是结构与树类型相似的子树，每棵子树的根结点有且仅有一个前驱结点，后 继结点可以有0个或多个。
每棵子树是互不相交的，如果相交则为“图”不为“树”
除了根结点外，每个结点都只有一个父结点
假设一棵树有N个结点，那么这条数有N-1条边
二. 树的相关术语
父结点：如果一个结点有子节点，那么这个结点是子节点的父节点
子结点： 一个结点含有的子树的根结点称为该结点的子结点
结点的度：一个结点有N个子结点，那么这个结点的度为N
树的度：最大的结点的度称为树的度
叶子结点：度为0的结点
分支结点：度不为0的结点
结点的层次：从根开始定义，根为第一层，根的子结点为第二层，以此类推
树的高度：树中结点的最大层次
三. 二叉树的概念
二叉树是树的一种，也是我们最常用的树形结构，一棵二叉树是结点的一个有限集合，该集合由一个根结点和两棵分别称为“左子树”和“右子树”的二叉树组成。
上图是一棵二叉树，通过上图我们可知二叉树有以下特点：
1. 二叉树的结点的度不大于2
2. 二叉树的子树有左右之分，因此二叉树是有序树
3. 二叉树可以是空树，可以只有根结点，左子树可以为空，右子树可以为空，左右子树均在
四. 满二叉树
对于每个结点的度数都达到最大值，我们称这种二叉树为满二叉树。
一棵树的层数为N，最大结点数为2*N-1，下图是一棵满二叉树，层数为3，最大节点数为7
五. 完全二叉树
完全二叉树是由满二叉树引出来的，对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到N的结点一一对应时称为完全二叉树。
注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
六. 顺序结构的二叉树
顺序结构的二叉树底层为数组，但是只适合完全二叉树，不然会造成空间的浪费
对于完全二叉树，因为其结点都有连续对应的编号，因此适合用数组存储，数组的下标代替了结点的编号
对于非完全二叉树，如果使用数组来实现，有内存空间的浪费：
七. 顺序结构二叉树的实现（本文以小堆为例）
我们一般用堆来实现顺序结构的数组，堆其实是一种特殊的二叉树，它有着二叉树的性质，也有许多其他的特性，同时堆也是一棵完全二叉树。
堆也分为大堆和小堆：
大堆：根结点存放的数据最大，每个父结点都比其子结点要大
小堆：根结点存放的数据最小，每个父结点都比其子结点要小
子结点与父结点的关系：
对于子结点： 若子结点 i 在该堆中有效，则其父结点对应的序号为：(i-1)/2，当i=0时，无
父结点，因为i=0时为根结点，根结点没有父结点
对于父结点：若父结点的序号为i, 左孩子序号为2*i+1，右孩子序号为：2*i+2，
对于结点数位n的完全二叉树，若2*i+1>=n，则无左孩子， 若2*i+2>=n,则无右孩子
（都大于最大结点数了，不可能还有子结点的，总不能凭空加上去吧）
1.堆的结构定义
堆的底层结构是数组，和顺序表很相似，其实在定义结构体中也是十分相似的
typedef int HPDataType;
//堆的定义
//堆的底层为数组
typedef struct Heap {
HPDataType* arr;//指向动态开辟内存的地址
int size;//堆的有效数据个数
int capacity;//堆的最大容量
}HP;2.堆的初始化
初始化操作与顺序表一致，这里就不再赘述
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}3.堆的销毁
销毁操作与顺序表一致，不再赘述
void HPDestroy(HP* php) {
assert(php);
if (php->arr) {
free(php->arr);
}
php->capacity = php->size = 0;
php->arr = NULL;
}4.入堆
在入堆操作时，是在堆尾进行插入的，在插入前需要检查当前堆的空间是否足够容纳新数据，空间不足的话需要先扩容再进行入堆。
因为堆分为大堆和小堆，我们在入堆操作后，新数据所在的位置不一定满足堆的性质，这里我们所以我们需要将新数据向上调整，直到新数据所处的位置满足堆的性质，新数据调整完后更新堆的有效个数。
void HPPush(HP* php, HPDataType x) {
assert(php);
//检查空间是否不足
if (php->capacity == php->size) {
//如果堆空间为0,扩容
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* ret = (HPDataType*)realloc(php->arr, newcapacity*sizeof(HPDataType));
if (ret == NULL) {
perror("relloc");
exit(1);
}
php->arr = ret;
php->capacity = newcapacity;
}
//在当前位置入堆
php->arr[php->size] = x;
AdjustUp(php->arr,php->size);
//堆的有效个数+1,为什么要到最后才更新堆的有效个数，
//因为向上调整法需要传递新插入结点的下标，插入堆后下标刚好是size
//当然更新有效个数后再进行向上调整也是可以的，修改向上调整函数的第二个参数就行
++ php->size;
}那么，对入堆数据的向上调整时是如何实现的呢？
5.向上调整法（堆的插入后需要调整）
毫无疑问，入堆的数据成为了某一个结点的子结点，向上调整我们需要知道当前结点的父结点，
利用当前结点在数组所对应的下标，入堆对应的下标其实就是有效数据个数size
新结点入堆后，开始进行向上调整，当前结点与其父结点相比较， 然后更新父结点与子结点，因为我们建立的是小堆，所以当子结点大于父结点时，便不再需要继续向上调整
//交换函数
void Swap(HPDataType* x, HPDataType* y) {
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法,子求父： （子-1）/2
void AdjustUp(HPDataType* arr, int child) {
int parent = (child - 1) / 2;
while (child > 0) {//确保当前节点 child 有一个有效的父节点可以进行比较和调整。
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);//传址调用
}
else {
break;
}
}
}
向上调整法图示：
6.出堆
对于堆而言：出堆的结点是堆顶，也就是树的根结点
你或许会想：堆的底层结构为数组，那么我们直接将数组下标为0的数据删除就好。那么真的可以这样操作吗？
如下图，假如我们直接将数组下标为0的结点直接出堆，出堆后既不是大堆也不是小堆，而且原本结点的父子关系也错误了
正确的出堆方法：将堆顶的结点与堆底相调换，再删除堆底结点，再让新的堆顶结点向下调整
因为数组最后一位删除后，堆的结构不会发生改变
堆顶和堆底相交换后，删除新的堆底，然后新的堆顶向下调整，如果子结点比父结点大，则两者向交换，直到子结点比父结点小或者子结点处于非法范围
7.向下调整法（堆的删除后需要调整）
在小堆的出堆后，要进行向下调整的结点毫无疑问是堆顶，向下调整，我们需要知道其最小的子结点，当我们找到最小的子结点后，将最小的子结点与父结点比较，如果子结点比父结点小，则交换，然后更新父结点和子结点。否则不需要向下调整
//向下调整算法，父求子：父*2+ 1/2
void AdjustDown(HPDataType* arr, int parent, int n) {//n 是数组的大小
int child = parent*2 + 1;//假设左孩子最小
while (child < n)//孩子不能超过数组的界限
{
//找左右孩子中找最小的
if (child + 1 < n && arr[child] > arr[child + 1])//child + 1 < n检查是否有右孩子，没有右孩子就不进入
{
child++;
}
if (arr[child] < arr[parent])//父比子大，交换，因为是形成小堆，最小的要在堆顶
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}8.堆的判空
返回堆的有效数据个数即可判断堆是否为空
//判空
bool HPEmpty(HP* php) {
assert(php);
return php->size==0;
}9.取堆顶数据
//取堆顶
HPDataType HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}八.全码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
//堆的定义
//堆的底层为数组
typedef struct Heap {
HPDataType* arr;
int size;
int capacity;
}HP;
//小堆
//初始化
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
//销毁
void HPDestroy(HP* php) {
assert(php);
if (php->arr) {
free(php->arr);
}
php->capacity = php->size = 0;
php->arr = NULL;
}
//交换函数
void Swap(HPDataType* x, HPDataType* y) {
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法,子求父： （子-1）/2
void AdjustUp(HPDataType* arr, int child) {
int parent = (child - 1) / 2;
while (child > 0) {//确保当前节点 child 有一个有效的父节点可以进行比较和调整。
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
}
else {
break;
}
}
}
//向下调整算法，父求子：父*2+ 1/2
void AdjustDown(HPDataType* arr, int parent, int n) {//n 是数组的大小
int child = parent*2 + 1;//假设左孩子最小
while (child < n)//孩子不能超过数组的界限
{
//找左右孩子中找最小的
if (child + 1 < n && arr[child] > arr[child + 1])//child + 1 < n检查是否有右孩子，没有右孩子就不进入
{
child++;
}
if (arr[child] < arr[parent])//父比子大，交换，因为是形成小堆，最小的要在堆顶
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//入堆
void HPPush(HP* php, HPDataType x) {
assert(php);
//检查空间是否不足
if (php->capacity == php->size) {
//如果堆空间为0,扩容
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* ret = (HPDataType*)realloc(php->arr, newcapacity*sizeof(HPDataType));
if (ret == NULL) {
perror("relloc");
exit(1);
}
php->arr = ret;
php->capacity = newcapacity;
}
//在当前位置入堆
php->arr[php->size] = x;
AdjustUp(php->arr,php->size);
//堆的有效个数+1,为什么要到最后才更新堆的有效个数，
//因为向上调整法需要传递新插入结点的下标，插入堆后下标刚好是size
++ php->size;
}
//出堆
void HPPop(HP* php) {
//出堆，出的是堆顶，但是不能直接删除堆顶，这样堆就混乱了
//将堆顶元素和顶底交换，然后删除堆底
//最后向上调整算法向上调整
assert(php);
Swap(&php->arr[0], &php->arr[php->size - 1]);
-- php->size;
AdjustDown(php->arr, 0, php->size);
}
//判空
bool HPEmpty(HP* php) {
assert(php);
return php->size==0;
}
//取堆顶
HPDataType HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}