数据结构与算法（二叉树）
鲸饮未吞海，剑气已横秋。
前言
这是我学习数据结构的第五份笔记，有关二叉树的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有栈与列队，没看过的同学可以去看看： 有关栈与列队的笔记
树
树的概念与结构
1. 树是⼀种非线性的数据结构，它是由 n 个有限结点组成的⼀个具有层次关系的集合。 2. 之所以把它叫做树，是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下。 2. 有⼀个特殊的结点，称为根结点，根结点没有前驱结点（父节点）。 3. 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合，其中每⼀个集合又是⼀棵结构与树类似的子树。 4. 每棵子树的根结点有且只有⼀个前驱，可以有 0 个或多个后继（子节点）。因此，树是递归定义的。 5. 树形结构中，子树之间不能有交集，否则就不是树形结构。 6. 除了根结点外，每个结点有且仅有⼀个父结点（根节点没有父节点）。 7. ⼀棵N个结点的树有N-1条线（每多一个节点，就多一条线）。
树的相关术语
1. 父结点：若⼀个结点含有子结点，则这个结点就称为其子结点的父结点； 如上图：A是B的父结点。 2. 子结点：⼀个结点含有的子树的根结点，就称为该结点的子结点； 如上图：B是A的子结点。 3. 结点的度：⼀个结点有几个子节点，他的度就是多少；比如A的度为6，F的度为2，K的度为0。 4. 兄弟结点：具有相同父结点的结点，互称为兄弟结点； 如上图： B、C 是兄弟结点。 5. 树的度：⼀棵树中，最大的结点的度称为树的度； 如上图：树的度为 6。 6. 叶子结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I... 等结点为叶结点。 7. 分支结点：度不为 0 的结点； 如上图： D、E、F、G... 等结点为分支结点。 8. 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推。 9. 树的高度（深度）：树中结点的最大层次； 如上图：树的高度为 4。 10. 结点的祖先：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先。 11. 结点的子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的子孙。 12. 路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q。 13. 森林：由 m 棵互不相交的树的集合称为森林。
树的表示
1. 相对线性表结构，树结构更加复杂，既然保存值域，也要保存结点和结 点之间的关系。 2. 实际中，树有很多种表示方法如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子 兄弟表示法等。 3. 我们这里就简单的了解其中最常用的 孩子 兄弟表示法。
#define _CRT_SECURE_NO_WARNINGS
typedef struct TreeNode
{
struct TreeNode* child;
struct TreeNode* brother;
int data;
}TreeNode;
二叉树
1. 在树形结构中，我们最常用的就是二叉树，⼀棵二叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左子树和右子树的二叉树组成（或者为空）。 2. 二叉树不存在度大于 2 的结点。 3. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
满二叉树
1. ⼀个二叉树，如果每⼀个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果⼀个二叉树的层数为 K ，且结点总数是 2^k − 1 ，则它就是满二叉树。
完全二叉树
1. 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。 2. 要注意的是满二叉树是⼀种特殊的完全二叉树。 3. 假设二叉树层数为K层，除了第K层外，每层节点的个数达到最大节点的个数，而第K层节点个数不一定达到最大节点数，并且第K层节点顺序是严格从左到右的，那么这个二叉树就是完全二叉树。
二叉树的性质
1. 若规定根结点的层数为 1 ，则⼀棵非空二叉树的第 i 层上最多有 2^（i−1）个结点。 2. 若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2^h − 1。 3. 若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 h = log2 (n + 1) ( log 以2为底，（ n+1） 为对数)。
二叉树存储结构
二叉树⼀般可以使用两种结构存储，⼀种顺序结构，⼀种链式结构。
顺序结构
1. 二叉树的顺序结构存储就是使用数组来存储，⼀般使用数组只适合表示完全⼆叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。 2. 我们通常把堆（⼀种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。 3. 根据数学关系我们可以得到数学公式，再根据顺序结构中不能跳的原则，从而得出节点的信息。
链式结构
1. 二叉树的链式存储结构是指：用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 2. 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩 子所在的链结点的存储地址 。 3. 链式结构又分为二叉链和三叉链（多了一个指向父节点的指针），博客中⼀般都是二叉链。
堆
1. 堆是⼀种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。 2. 堆一般使用顺序结构的数组来实现。
堆的性质与结构
1. 堆中某个结点的值总是不大于或不小于其父结点的值。（可以等于） 2. 越往上，值越大的堆，就是大根堆；越往上，值越小的堆，就是小根堆。 3. 小根堆的堆顶是最小值；大根堆的堆顶是最大值。 4. 堆总是⼀棵完全二叉树。
1. 对于具有 n 个结点的完全二叉树，按照从上至下、从左至右的数组顺序对所有结点从 0 开始编号，最后节点的序号为（n-1）。 2. 若 i>0 ，则 i 结点的父节点序号为： ( i - 1 ) / 2 ；若 i=0 ，则 i 为根结点编号，无父结点。 3. 若 2i+1<n ，左孩子序号： 2i+1 ； 2i+1>=n 否则无左孩子，发生了越界。 4. 若 2i+2<n ，右孩子序号： 2i+2 ； 2i+2>=n 否则无右孩子，发生了越界。
分步实现堆的功能
定义一个堆的结构体
typedef int DataType;
typedef struct Heap//定义一个堆的结构体
{
DataType* arr;
int size;
int capacity;
}Heap;堆的初始化
void HeapInit(Heap* sp)
{
assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
sp->arr = NULL;
sp->capacity = sp->size = 0;
}交换两边值函数
void Swap(DataType* a, DataType* b)//小心不要搞成交换指针
{
DataType tmp = *a;
*a = *b;
*b = tmp;
}向上调整算法（为了实现小堆）
void UpAdjust(DataType* arr, DataType child)//child都是序号，而储存的数据是arr[child]
{
int parent = (child - 1) / 2;
while (child > 0)//不需要等于，如果孩子节点序号为0，则已经是根节点，不需要再向上调整。
{
if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}向堆中插入数据
void HeapPush(Heap* sp, DataType x)
{
assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
if (sp->capacity == sp->size)
{
int newcapacity = sp->capacity == 0 ? 4 : 2 * sp->capacity;
DataType* tmp = (DataType*)realloc(sp->arr, sizeof(DataType)* newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
sp->arr = tmp;
sp->capacity = newcapacity;
}
sp->arr[sp->size] = x;
UpAdjust(ps->arr, ps->size);//变成小堆
ps->size++;
}向下调整算法（为了实现小队）
void DownAdjust(DataType* arr, DataType parent, DataType n)
{
DataType 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 HeapPop(Heap* ps)
{
assert(ps->arr);//删除数据时候，堆里面要有数据,即ps->arr不能为空
Swap(&(ps->arr[0]), &(ps->arr[ps->size-1]));
ps->size--;
DownAdjust(ps->arr, 0, ps->size-1);
}查询堆顶元素
DataType HeapTop(Heap* ps)
{
assert(ps->size!=0);
return ps->arr[0];//返回的是堆顶元素
}判断堆是否为空
bool HeapEmpty(Heap* ps)
{
return (ps->size == 0);//不能通过判断ps->arr是否为NULL从而判断堆是否为空，因为即使ps->arr不是NULL，堆也可能为空（即ps->size==0）。
}销毁堆
void HeapDestroy(Heap* sp)
{
assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
if (sp->arr != NULL)
{
free(sp->arr);
}
sp->arr = NULL;
sp->capacity = sp->size = 0;
}完整代码实现
<heap.h>文件
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int DataType;
typedef struct Heap
{
DataType* arr;
int size;
int capacity;
}Heap;
void HeapInit(Heap* ps);
void HeapDestroy(Heap* ps);
void HeapPush(Heap* ps, DataType x);
void UpAdjust(DataType* arr, DataType child);
void HeapPop(Heap* ps);
void Swap(DataType* a, DataType* b);
void DownAdjust(DataType* arr, DataType parent, DataType n);
DataType HeapTop(Heap* ps);
bool HeapEmpty(Heap* ps);<heap.c>文件
#include "heap.h"
void HeapInit(Heap* ps)
{
assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
void HeapDestroy(Heap* ps)
{
assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
if (ps->arr != NULL)//判断指向动态数组的指针是否为空
{
free(ps->arr);//如果不为空，则释放动态数组的空间
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
void HeapPush(Heap* ps, DataType x)
{
assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
DataType* tmp = (DataType*)realloc(ps->arr, sizeof(DataType)* newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->size] = x;
UpAdjust(ps->arr, ps->size);//变成小堆
ps->size++;
}
void Swap(DataType* a, DataType* b)//小心不要搞成交换指针
{
DataType tmp = *a;
*a = *b;
*b = tmp;
}
void UpAdjust(DataType* arr, DataType child)//child都是序号，而储存的数据是arr[child]
{
int parent = (child - 1) / 2;
while (child > 0)//不需要等于，如果孩子节点序号为0，则已经是根节点，不需要再向上调整。
{
if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPop(Heap* ps)
{
assert(ps->arr);//删除数据时候，堆里面要有数据,即ps->arr不能为空
Swap(&(ps->arr[0]), &(ps->arr[ps->size-1]));
ps->size--;
DownAdjust(ps->arr, 0, ps->size-1);
}
void DownAdjust(DataType* arr, DataType parent, DataType n)
{
DataType 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;
}
}
}
DataType HeapTop(Heap* ps)
{
assert(ps->size!=0);
return ps->arr[0];//返回的是堆顶元素
}
bool HeapEmpty(Heap* ps)
{
return (ps->size == 0);//不能通过判断ps->arr是否为NULL从而判断堆是否为空，因为即使ps->arr不是NULL，堆也可能为空（即ps->size==0）。
}<test.c>文件
#include "heap.h"
int main()
{
Heap heap;
HeapInit(&heap);
HeapPush(&heap, 1);
HeapPush(&heap, 2);
HeapPush(&heap, 3);
HeapPush(&heap, 4);
HeapPush(&heap, 5);
HeapPop(&heap);
while (!HeapEmpty(&heap))
{
printf("%d ", HeapTop(&heap));
HeapPop(&heap);
}
HeapDestroy(&heap);
return 0;
}致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
腾讯云开发者
