1. 树

1.1 树的概念和结构

树是一种非线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

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

树形结构中，子树之间不能有交集，否则就不是树形结构

以下三棵树是非树形结构：

• 子树是不相交的
• 除了根结点外，每个结点有且仅有一个父结点
• 一棵N个结点的树有N-1条边

1.2 树的相关术语

• 父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
• 子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
• 结点的度：一个结点有几个孩子，他的度就是多少；比如A的度为6，F的度为2，K的度为0
• 树的度：一棵树中，最大的结点的度称为树的度； 如上图：树的度为 6
• 叶子结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点
• 分支结点/非终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分支结点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)； 如上图： B、C 是兄弟结点
• 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推；
• 树的高度或深度：树中结点的最大层次； 如上图：树的高度为 4
• 结点的祖先：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先
• 路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
• 森林：由 m（m>0） 棵互不相交的树的集合称为森林；

2. 二叉树

2.1 二叉树的概念和结构

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树可以是空树，或者由一个根节点和两个互不相交的、分别被称为左子树和右子树的二叉树组成。

2.2 二叉树的特点

• 二叉树不存在度大于 2 的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的

2.3 特殊的二叉树

2.3.1 满二叉树

一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个个二叉树的层数为 k ，且结点总数是 2k − 1 ，则它就是满二叉树。

2.3.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是⼀种特殊的完全二叉树。

完全二叉树的性质：

• 节点排列紧密：除了最底层外，完全二叉树的每一层都被完全填满，且所有节点都尽可能地向左对齐。这意味着树的节点排列非常紧凑，没有空闲的空间。
• 叶子节点特性：完全二叉树的叶子节点只可能出现在最底层和次底层。在最底层，叶子节点从左到右依次排列；如果存在次底层，则次底层的叶子节点在根节点右子树的部分。
• 完全二叉树与满二叉树：满二叉树是完全二叉树的一个特例，其中每一层都被完全填满，没有任何空缺。完全二叉树则允许最后一层有空缺，但空缺必须全部集中在最右边。

2.4 二叉树的性质

二叉树第i层的结点个数：若规定根结点的层数为 1 ，则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点
二叉树的总结点个数：若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2^h-1
满二叉树的深度：若规定根结点的层数为 1 ，则具有 n 个结点的满二叉树的深度为h = log2 (n + 1) ( log以2为底， n+1 为对数)

3. 实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是⼀种特殊的二叉树，具有⼆叉树的特性的同时，还具备其他的特性。

3.1 堆的概念和结构

堆（Heap）是一种特殊的完全二叉树结构，其中每个节点的值都遵循特定的堆属性（heap property）。根据堆属性的不同，堆可以分为两种主要类型：最大堆（Max Heap）和最小堆（Min Heap）。

• 最大堆：在最大堆中，每个节点的值都大于或等于其子节点的值。这意味着根节点（堆顶）是堆中的最大值。
• 最小堆：在最小堆中，每个节点的值都小于或等于其子节点的值。因此，根节点（堆顶）是堆中的最小值。

堆具有以下性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，无双亲结点
2. 若 2i+1<n ，则左孩子序号： 2i+1 ； 若2i+1>=n 无左孩子
3. 若 2i+2<n ，则右孩子序号： 2i+2 ； 若2i+2>=n 无右孩子

下面来定义堆的顺序结构和具体要实现的功能：

typedef int HPDataType;
typedef struct Heap {HPDataType* arr;int capacity;//堆的空间大小int size;//堆的有效数据个数
}HP;
//初始化
void HPInit(HP* php);
//销毁
void HPDestroy(HP* php);
//入堆(堆尾)
void HPPush(HP* php, HPDataType x);
//出堆(堆顶)
void HPPop(HP* php);
//返回堆顶
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);
//交换
void Swap(int* a, int* b);

3.2 初始化

思路：将堆这个结构体的地址取过来用一级指针接收，实现形参改变实参，然后将指针置为空，空间大小和有效数据个数置为0即可

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

3.3 销毁

思路：如果动态数组不为空需要使用free函数对其空间进行释放，然后将堆的空间大小和有效数据个数置为0，如果动态数组为空，直接将堆的空间大小和有效数据个数置为0即可

//销毁
void HPDestroy(HP* php)
{assert(php);//php!=NULLif (php->arr){//销毁内存free(php->arr);}php->capacity = php->size = 0;
}

3.4 插入数据

思路：首先判断空间大小是否为满，如果空间大小满了(php->size == php->capacity)则需要使用realloc函数对原来的数组进行扩容，扩容成功后将数据插入堆尾，然后进行向上调整将数据的顺序重新调整，最后将堆的有效数据加一即可

//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//php!=NULLif (php->size == php->capacity){//空间不够需要扩容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;//先判断空间容量capacity是否为0，为0就默认扩容四个大小空间，不为0就扩容为原来的两倍HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));//因为是在原来空间上申请更大的空间，所以要使用realloc函数对数组进行扩容if (tmp == NULL){//申请失败，打印错误信息perror("realloc fail!");exit(1);}//申请成功php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//每次往堆里面插入数据都要向上调整AdjustUp(php->arr, php->size);php->size++;//最后堆的有效数据+1
}

3.5 向上调整算法

先将元素插入到堆的末尾,即最后一个孩子之后，插入之后如果堆的性质遭到破坏，将新插入的结点顺着其父节点往上调整到合适位置即可

思路：因为向上调整算法是不断调整父节点和孩子结点的顺序，如果是建小堆就判断父节点是否大于孩子结点，如果大于就交换父结点和孩子结点，然后更新父结点和孩子结点继续向上调整，使得堆里面所有的父结点都小于等于孩子结点。如果建的是大堆，则反之。

根据孩子结点得出父结点：parent = (child - 1) / 2

注意：当向上调整到根节点时就不用继续向上调整了，因为根节点没有父节点，所以循环条件为child>0

建小堆：

void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void AdjustUp(HPDataType* arr, int child)
{//建小堆int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){//如果父节点大于孩子结点就交换Swap(&arr[child], &arr[parent]);//更新孩子结点和父节点child = parent;parent = (child - 1) / 2;}else{break;}}
}

建大堆：

void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void AdjustUp(HPDataType* arr, int child)
{//建大堆int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){//如果孩子结点大于父结点就交换Swap(&arr[child], &arr[parent]);//更新父结点和孩子结点child = parent;parent = (child - 1) / 2;}else{break;}}
}

向上调整算法的时间复杂度为：O(log n)
向上调整算法建堆的时间复杂度：O(n ∗ log2 n)

3.6 删除数据(堆顶)

思路：既然要删除堆顶数据，所以堆的有效数据个数不能为空。先将堆顶和堆尾的数据进行交换，再将堆尾数据删除(堆的有效数据个数减一)，最后从根节点进行向下调整

//出堆
void HPPop(HP* php)
{assert(php&&php->size);//php!=NULL，php->size!=0//交换堆顶和堆尾的数据Swap(&php->arr[0], &php->arr[php->size - 1]);//有效数据-1--php->size;//从根节点开始向下调整AdjustDown(php->arr, 0, php->size);
}

3.7 向下调整算法

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。

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

已知一个父节点parent算出左右孩子节点：
左孩子：child = 2 * parent + 1
右孩子：child = 2 * parent + 2

向下调整算法：如果建的是小堆，首先从根节点作为父结点开始与其左右孩子进行比较，如果父节点大于左孩子节点或者大于右孩子节点(如果都大于则与最小的孩子节点进行交换)，然后更新父节点和孩子节点，继续向下调整，如果父节点小于左右孩子节点则停止，使得所有的父节点都小于或等于孩子节点。如果建的是大堆，则反之。

注意：当向下调整到最后一层的时候就停止，因为最后一层如果作为父节点是没有孩子节点的，所以不用继续向下调整了，所以循环条件为child<n

建小堆：

void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void AdjustDown(HPDataType* arr, int parent,int n)
{//建小堆int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] > arr[child + 1]){//如果右孩子节点比左孩子节点小，那么child++，使child变成右孩子节点的下标child++;}if (arr[child] < arr[parent]){//如果孩子节点比父节点小就交换Swap(&arr[child], &arr[parent]);//更新父节点和孩子节点，继续向下调整parent = child;child = 2 * parent + 1;}else{break;}}
}

建大堆：

void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void AdjustDown(HPDataType* arr, int parent, int n)
{//建大堆int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){//如果右孩子节点比左孩子节点大，那么child++，使child变成右孩子节点的下标child++;}if (arr[child] > arr[parent]){//如果孩子节点比父节点大就交换Swap(&arr[child], &arr[parent]);//更新父节点和孩子节点，继续向下调整parent = child;child = 2 * parent + 1;}else{break;}}
}

向下调整算法的时间复杂度为：O(log n)
向下调整算法建堆的时间复杂度：O(n)

3.8 返回堆顶数据

思路：因为要返回堆顶数据，所以堆不能为空。直接返回堆顶数据即可。

//返回堆顶
HPDataType HPTop(HP* php)
{assert(php);//php!=NULLassert(php->size);//堆的有效数据个数不为0return php->arr[0];//返回堆顶数据
}

3.9 判空

思路：如果堆的有效数据个数为0堆就为空

//判空
bool HPEmpty(HP* php)
{assert(php);//php!=NULLreturn php->size == 0;//如果堆的有效数据个数为0则为空
}

3.10 返回堆的有效数据个数

思路：直接返回堆的有效数据个数size

//返回堆的有效数据个数
int HPSize(HP* php)
{assert(php);//php!=NULLreturn php->size;
}

4. 堆的应用

4.1 堆排序

方法一：创建一个堆，如果要升序就建小堆，如果要排降序就建大堆，每次将堆顶数据给回数组a，再将堆顶数据删除并且向下调整，再返回堆顶数据…… 一直到堆为空为止

void HeapSort(int* a, int n)
{HP hp;for(int i = 0; i < n; i++){HPPush(&hp,a[i]);}int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);
}

该方法的时间复杂度为O(N)，空间复杂度也为O(N)

方法二：用原来的数组建堆(从数组的最后一个数据的父节点开始向下调整，向下调整完再将下标减一，继续向下调整，直到根节点向下调整完为止)，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整，然后不断地首尾交换和交换后的堆尾数据从堆中删掉，一直到堆尾数据等于堆顶数据即可。如果要排降序就建小堆，如果要升序就建大堆

void HeapSort(int* arr, int n)
{//向上调整算法建堆 O(n∗log2 n)//for (int i = 0; i < n; i++)//{//AdjustUp(arr, i);//}//向下调整算法建堆 O(n)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

堆排序时间复杂度为： O(nlog n) ，空间复杂度为：O(1)

4.2 TOP-K问题

TOP-K问题：即求数据集合中前k个最大的元素或者最小的元素，一般情况下数据量都比较大。

思路：先取数据集合的前k个元素来建堆，如果求前k个最大的元素就建小堆，如果是求前k个最小的元素就建大堆。然后用n-k个数据来跟堆顶比较，如果不满足条件，就替换堆顶元素并且向下调整，将剩余的元素全部跟堆顶比较完后，堆中的k个元素就是所求的前k个最大的元素或者最小的元素

void CreateNData()
{int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void TOPk()
{int k = 0;printf("请输入k: ");scanf("%d", &k);//从文件中读取前k个数据，建堆const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!");exit(1);}int* minHeap = (int*)malloc(k * sizeof(int));if (minHeap == NULL){perror("malloc fail!");exit(2);}//从文件中读取前k个数据for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}

随机生成十万个数据存储到文件data.txt中，为了可以知道所求的前k个数据是否正确，还要再设置一下这6个最大的数据

运行结果：

所求前6个最大的数据正是这6个。
时间复杂度： O(n) = k + (n − k)log2 k

对以上内容有不同看法的欢迎来讨论，希望对大家的学习有帮助，多多支持哦！