数据结构-二叉树

一. 树的概念

树在我们的日常生活中随处可见，人们将生活中的树转换成存放数据的树形结构，就成了数据结构中的“树”。

如上图所示，自然界中的树有树根，有树枝，有树叶，当我们将其转换成树形结构时，只需将其倒转过来，将树根，树枝的岔口，树枝的顶部画一个圆，就成了一个完美的树形结构：

树型结构是一种非线性的数据结构，它是由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];
}