一 树
1.1.树的概念与结构
数是一种非线性的数据结构，是由n(n>=0)个有限结点组成一个具有层次关系的集合。它之所以叫树，是因为它看起来像一颗倒挂的树，也就是说它的根朝上，叶朝下。
- 有一个特殊的结点，称为根节点，根节点没有前驱结点。
- 除根结点外，其余结点被分成M（M>0）个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti又是一科结构与树类似的子树。每颗子树的根节点有且只有一个前驱，可以又0个或多个后继。因此，树是递归定义的。
注意：
- 子树是不相交的（如果相交了就是“图”结构，如下图，本文章暂不过多介绍）
- 除了根节点外，每个结点有且仅有一个父节点
- 一课N个结点的树有N-1条边
1.2.树的相关术语
- 父结点/双亲结点:若一个结点含有子结点，则这个结点称为其子结点的父结点;如上图:A是B的父结点（注意父子节点必须相连，就比如A不能是G的父节点）
- 子结点/孩子结点:一个结点含有的子树的根结点称为该结点的子结点;如上图:B是A的孩子结点
- 结点的度:一个结点有几个孩子，他的度就是多少;比如A的度为3，D的度为2，E的度为0
- 树的度:一棵树中，最大的结点的度称为树的度;如上图:树的度为3
- 叶子结点/终端结点:度为0的结点称为叶结点;如上图:E、F、G、H等结点为叶结点
- 分支结点/非终端结点:度不为0的结点;如上图:B、C、D等结点为分支结点
- 兄弟结点:具有相同父结点的结点互称为兄弟结点(亲兄弟);如上图:B、C是兄弟结点
- 结点的层次:从根开始定义起，根为第1层，根的子结点为第2层，以此类推;
- 树的高度或深度:树中结点的最大层次;如上图:树的高度为3
- 结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
- 路径:一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列;比如A到I的路径为，A-D-I;
- 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙。
- 森林:由m(m>0)棵互不相交的树的集合称为森林:
森林示意图：
1.3.树的表示
首先分析树的结构组成，里面有父结点，子节点，兄弟结点。而每一个子节点又能组成一棵树，每一个兄弟结点也要组成一棵树。所以树最简单的表达方式就是孩子兄弟表示法
struct TreeNode
{
struct Node*child; //左边开始的第一个子节点
struct Node*brother;//指向其右边的下一位兄弟节点
int data; //结点中的数据
};
4.树形结构实际运用场景
在生活中最常见的就是文件的存储，计算机通过一层层的文件夹把数据进行分类，存储。
就比如D盘可以是里面所有文件的父节点，而里面的原神文件夹是其中的一个子节点。原神又可细分出无数个文件夹。
二 二叉树
2.1.概念和结构
二叉树是树的一种，是树里面最常用的结构，一课二叉树是结点的一个有限集合，该集合是由一个根节点加上两棵别称为左子树和右子树的二叉树组或者为空
2.2.二叉树的特点：
- 二叉树的结点的度最大为2
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
左子树 右子树
同时二叉树还有不同的形态，所有二叉树均是由以下几种情况融合而成的：
2.3.特殊的二叉树：
2.3.1满二叉树
一个二叉树，如果每层的结点的度都达到做大值，则这个二叉树就叫为满二叉树。也就是说，如果一个二叉树的层数为K，那么该二叉树的总结点数为(2^K ) - 1，则它就是二叉树。
2.3.2完全二叉树
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时称为二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
简单来说，完全二叉树除了最后一层，每层结点的个数达到最大。最后一层结点的个数不一定达到最大，不过要注意的是，完全二叉树的结点要从左到右依次排列。就比如下图就不是完全二叉树
2.4.二叉树的性质
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点
- 若规定根结点的层数为1，则深度为 h的二叉树的最大结点数是(2^k)-1
- 若规定根结点的层数为 1，具有n个结点的满二叉树的深度h = log2(n+1)(log以2为底，n+1为对数)
2.5.二叉树的的存储结构
二叉树一般用两种结构进行存储，一种是顺序结构，一种是链式结构。
2.5.1顺序结构
顺序结构就是通过数组来存储，一般使用数组只适合表示完全二叉树，因为不完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构进行存储。
标号顺序：按照完全二叉树的结构从上到下，从左到右。
当二叉树是非完全二叉树时，会发现很多标号是空的这样就造成了空间的浪费。如下图：
如果把空的位置替换了是不是就可以避免空间浪费了？（如把上图改成下图）
要知道任何存储方式都是为了方便还原数据结构，此时，为了通过数组还原二叉树，如果把空的下标替换掉会导致顺序乱掉，会把右子树改成左子树，那就不能正确还原了。所以标号的顺序不能改变。
2.5.2链式结构
二叉树的链式存储结构是指，用链来表示二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和做与指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，目前大多数运用的是二叉链。后期学习的红黑树则用到的是三叉链。
//二叉链
typedef struct Bitnode
{
int data;
struct Bitnode*lchild;
struct Bitnode*rchild;
}Bitnode, *Bitree;//三叉链
typedef struct Bitnode
{
int data;
struct Bitnode* lchild;
struct Bitnode* rchild;
struct Bitnode* father;//指向父结点
}Bitnode, *Bitree;三 使用顺序结构存储二叉树
3.1.堆的概念与结构
堆其实就是一种特殊的二叉树（完全二叉树）
小堆（小根堆）：根节点最小的堆 大堆（大根堆）：根节点最大的堆
根节点的值比左右孩子的值小或等于 根节点的值比左右孩子的值大或等于
不过要注意的是，大小堆并不能决定数组的升降序。
3.1.1二叉树的性质
对于具有n个结点的二叉树，如果从上至下，左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：
- 若i>0,i位置的双亲序号：（i-1）/2;若i=0,i为根节点，无双亲。
- 若2i+1<n，左孩子序号：2i+1,2i+1>=n则无左孩子。
- 若2i+2<n，右孩子序号：2i+2,2i+2>=n则无右孩子。
3.2.堆的实现
3.2.1.初始化：
注意传参的时候使用的是地址
3.2.2.销毁：
free之后要把arr置为空，防止野指针的出现
3.2.3插入：
小堆的插入与其他数据结构相同，需要判断数组的空间是否充足，如果不充足就需要开辟空间。
不过值得注意的是，如果直接把数据插入到数组里（如下图），会导致顺序变乱，不再是一个堆了。所以，需要把数据插入到合适的位置，以确保大小堆的性质。
这里采用循环比较，不断把数据调位到正确的位置。而大小堆的区别也就是循环体中的><号。
最后经过调试确保正确
小堆：
数组：10、35、15、56、70、25
大堆：
数组：70、56、25、10、35、15
3.2.4.打印：
3.2.5出堆：
出堆是让堆顶的元素移除，因为底层逻辑是数组，直接移移除arr[0]肯定不行，而数组的最后一个元素却很好删除，直接让size--便可达到移除的效果，所以直接利用交换，把堆头和堆尾进行交换实现出堆。
当把堆顶的数据移除后，并不能满足堆的性质，所以类似插入工具，还需要调整数组的顺序。与其不一样的是，出堆知道父节点的位置，所以利用的是向下调整。
要注意的是：插入与出堆的类型要一置。
如：若当插入的时候按照大堆插入的时候，出堆也要按照大堆的写法进行出堆。
3.2.6取堆顶：
在取堆顶测试的时候发现，直接打印堆的数组，与通过取堆顶打印出的数组顺序不同。
此时可以发现，利用取堆顶取出的数据是递增的，那么此时可以算作堆排序吗？
3.2.7堆排序：
为了验证想法，我们利用该方法写一个堆排序。
将数据数组传入堆数组后，利用取堆顶，确实可以达到排序的效果。但是问题来了，之前学过的排序都是更改的原数组的数据顺序，而此时原数据数组并没有被更改，所以造成了一个假排序，所以在while循环中，不能直接进行打印数据。
修改while循环，把原数组进行更改：
不过此时的堆排序需要借助堆的数据结构，每当使用的时候，还需依赖堆的数据结构，那么能不能借助堆的思想来排序。
堆排序最终：
1.首先要根据数组进行建堆：利用向下调整，不断向上更换父结点来实现建堆。
排升序：建大堆
排降序：建小堆
2.将堆顶和最后一个数据进行交换，--size，再次向下调整堆，并重复该过程。
