树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
一、树的概念 概念： ※ 节点的度：一个节点 含有的子树的个数 称为该节点的度； 如上图：A的度为2。 ※ 叶节点或终端节点： 度为0的节点称为叶节点 ； 如上图：E、F、G、H...等节点为叶节点。 非终端节点或分支节点：度不为0的节点； 如上图：B、C、D...等节点为分支节点 ※ 双亲节点或父节点：若 一个节点含有子节点，则这个节点称为其子节点的父节点 ； 如上图：A是B的父节点 ※ 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点 ※ 兄弟节点：具有 相同父节点的节点互称为兄弟节点 ； 如上图：B、C是兄弟节点。 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为2。 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； ※ 树的高度或深度： 树中节点的最大层次 ； 如上图：树的高度为4 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：D、F互为堂兄弟节点。 ※ 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先。 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。 森林：由m（m>0）棵互不相交的树的集合称为森林； PS：有的地方根节点的层次是设为0的，那么要注意空树就为-1。
PS：树形结构中子树是不能有交集的！否则不是树形结构。
（要注意，虽然不是树，但是其并不是错误的，是别的数据结构。）
左孩子右兄弟表示法：typedef int DataType;
struct tree
{
struct treee* firstchild1; //指向孩子节点
struct tree* pNextBrother; //指向兄弟
DataType _data;
};
第一个指针，只指向子节点的左孩子节点，让第二个指针指向其兄弟节点，这样就能把树的结构表现出来。这里使用的是类似链表的方式。
这里A的孩子指针指向B。B的孩子指针指向D，兄弟指针指向C，C的孩子指针指向F、G，兄弟指针指向NULL。
孩子指针只指向第一个孩子节点，这里B只指向D，而E由D的兄弟指针指向。
（只养老大，老二让老大去带，老三让老二去带。）
PS：如果节点后面没有子节点或者兄弟节点了，其指针指向空。
二、二叉树 概念：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
PS：
- 1. 二叉树不存在度大于2的结点
- 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
满二叉树：除在二叉树最下层的节点外，每层的节点都有两个子节点。
完全二叉树：除最后一层外，其他各层的节点数都达到最大个数，且最后一层节点是从左到右的连续存在。
PS：满二叉树是一种特殊的完全二叉树。
二叉树的性质：下标(数组)计算父子间的关系：
leftchild = parent*2+1;
rightchile = parent*2+2;
parent= (child-1)/2 ; (不用考虑小数，整数运算会忽略小数）
PS：h为二叉树的高度，n是节点数。
(指数用^的话不太明确，这里就用图片了）
Q：具有2k个节点的完全二叉树中，叶子节点个数为？
A： n0+n2+n1=2k； 且 n2=n0 - 1；所以n0+n0 -1+n1=2k；
2n0-1+n1=2k； 这里度为1的节点（n1）要么为1要么为0，如果这里为0，n0是小数，但是节点数不可能是小数，所以这里n1为1。
所以n0=k；所以叶子节点数为k个。
顺序存储：
顺序结构存储就是使用数组来存储，如果节点为空，要把空间留出来。会造成空间浪费，适合存储满二叉树和完全二叉树。
链式存储：
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
三、数据结构-堆
小根堆：
1.是个完全二叉树。
2.树中所有的父亲都是小于等于孩子。
大根堆：
1.是个完全二叉树。
2.树中所有的父亲都是大于等于孩子。
这里是用的数组来模拟堆的结构。
插入数据：
因为使用的顺序表，其真实的存储是直接插入到尾部就可以了，但是怎么让其逻辑上成为一个堆呢？
现在我们给出一个数组，逻辑上看做一颗完全二叉树。新添加一个数据，使用向上调整算法可以把它调整成一个小堆。
int array[] = {10,15,19,18,28,34,65,49,25,37};
（这里用画图快速模拟一下堆）
这里假设已经有一个正确结构的堆，插入一个节点27，这里堆就不匹配了。那么这里就需要使用向上调整算法进行调整。
插入的节点跟父节点进行比较如果，父节点比较大，就把自己跟父节点进行交换。然后继续跟新的父节点进行比较，直到遇到比自己小的父节点。
这样堆就正确排列了。
PS：调整节点比较大小时，只需要跟相同祖先的节点进行比较，兄弟节点之间的大小不影响堆的建立。
代码：
//向上调整
void AdjustUp(int* arr,int pos)
{
int child = pos;
int parent = (child - 1) / 2; //父节点公式。
while ( child > 0 ) {
parent = (child - 1) / 2;
if (arr[child] < arr[parent]) {
Swap(&arr[child],&arr[parent]);
}
else {
break;
}
child = parent;
}
}
一开始是没数据的，每次插入一个数调整一下，这样堆就创建出来了。
这里求父节点的下标的时候，因为其是整数做除法，小数点会被忽略，子节点 4 和 5，算出来的父节点都是 2，刚好对应上。
这里最坏的情况是交换到根节点，那么就可以判断是否到了根节点来结束循环。注意不要使用parent>=0来判断，因为到最后 parent = -1/2 ，其结果为0，会造成死循环。
PS：这里创建的是小堆，如果要创建大堆，把父子节点的比较换成大于符号就可以了。
删除数据：
删除堆的根节点，不能直接删除，不然其逻辑结构失效，堆会被打乱。
首先要把根节点跟最后一个叶子节点进行交换，然后删除。再把新的根节点进行向下调整。
选择较小的子节点，如果其也比自己小，那么进行交换。如果其比自己大那么结束交换。（生成大堆的时候选择较大的数，如果比自己大进行交换）
并不是每个节点都有右节点，如果只有一个左节点直接交换就行了。如果自己孩子节点的下标超过了堆的大小，说明自己已经是叶子节点了，就要退出循环。
PS：向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
代码：void AdjustDown(int *arr ,int size,int parent)
{
int child = parent * 2 + 1;
while ( child < size ) {
//防止越界，因为有左孩子节点，不一定有右孩子节点。
if ( child + 1 < size && arr[child + 1]
有了插入和删除就可以写出堆的结构了。
堆代码实现：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
//交换
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType temp = *a;
*a = *b;
*b = temp;
}
//向上调整
void AdjustUp(int* arr,int pos)
{
//建立小堆，如果新加入的数据比父节点小，就交换,比父节点大就退出。
int child = pos;
int parent = (child - 1) / 2;
while ( child > 0 ) {
parent = (child - 1) / 2;
if (arr[child] < arr[parent]) {
Swap(&arr[child],&arr[parent]);
}
else {
break;
}
child = parent;
}
}
//向下调整
void AdjustDown(int *arr ,int size,int parent)
{
//取较小的子节点交换数据。
int child = parent * 2 + 1;
while ( child < size ) {
//防止越界，因为有左孩子节点，不一定有右孩子节点。
if ( child + 1 < size && arr[child + 1] _a = NULL;
hp->_capacity = 0;
hp->_size = 0;
}
//创建堆
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
assert(a);
for (int i = 0; i < n;i++) {
HeapPush(hp, a[i]);
}
}
//销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->_a);
hp->_a = NULL;
hp->_capacity = 0;
hp->_size = 0;
}
//插入数据
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
int newCpacity = 0;
if (hp->_capacity==hp->_size) {
newCpacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* temp=(HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newCpacity);
if (temp==NULL) {
perror("temp为NULL");
exit(-1);
}
hp->_a = temp;
hp->_capacity = newCpacity;
}
hp->_a[hp->_size] = x;
hp->_size++;
//向上调整，构建堆
AdjustUp(hp->_a,hp->_size-1);
}
//删除数据
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
//交换首尾元素，size--，然后把根节点的元素向下调整。
Swap(&hp->_a[0],&hp->_a[hp->_size-1]);
hp->_size--;
AdjustDown(hp->_a,hp->_size,0);
}
//取根数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->_a[0];
}
//堆的大小
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;
}
//堆是否为空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->_size==0;
}
测试：
画图来快速判断一下结构是否正确。
由于实际使用的是顺序表进行存储的，所以大多数代码的写法跟顺序表差不多。这里主要的是插入数据和删除数据的逻辑和思路。
堆排序：堆优势是选数的速度很快，那么可以就使用堆来进行排序。
直接利用上面已经写好的堆。
void HeapSort(int* a, int n)
{
Heap hp;
HeapInit(&hp);
for (int i = 0; i < n;i++) {
HeapPush(&hp,a[i]);
}
int i = 0;
while (!HeapEmpty(&hp)) {
a[i++] = HeapTop(&hp);
HeapPop(&hp);
}
}
测试：
这种写法有缺点，使用堆排序的时候，不用一定要把堆这个数据结构全部写出来，只需要用数组和算法来模拟出堆的结构就可以。
而且这里还使用了两个数组，空间复杂度也提升了。
这里可以直接使用向上调整算法和向下调整算法来对数组进行调整。
//方式1：
//直接从数组第二个元素开始向上调整构建堆 ，此时的时间复杂度为O(nlogn);
for (int i = 1; i < n;i++) {
AdjustUp(a, i);
}
直接把给进来的数组的数据向上调整，调整出来的是数组就是堆的结构，构成堆就可进行排序了。
PS：这里构建堆，要从第二个元素开始向上调整，一直到最后。
//方式2：
//直接从最后的叶子节点的父节点，往下调整构建堆，时间复杂度为O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
向下调整，需要节点左右有堆，这里第一个有堆的节点，是最后一个叶子节点的父节点。然后依次往上调整，调整到最后堆的结构就建立起来了。
PS：最后一个节点的下标就是数组的长度-1，然后它的父节点就是第一个开始调整的节点。
最后把调整出来的堆进行排序，这直接就可以用一个数组进行排序。
其思路是把跟节点跟最后一个节点的数据进行交换，然后把堆的大小减小一个（这样就遍历不到最后一个节点了），因为把数据交换到了根节点，所以要重新调整建堆，直接把新的根数据向下调整，然后继续交换，直到堆的大小变为0。
从上面的思路就可以知道，假设建立的是小堆，其根节点是堆中最小的数，把他放到数组后面，然后继续建堆，找到次小的数，再放到后面。最后会发现，放置的数据在数组中是从大到小排列，构成了一个降序的数组。（根据其逻辑可以知道，建立降序数组用小堆，建立升序数组，用大堆）
void HeapSort(int* a, int n)
{
//i是最后一个叶子节点的父节点
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
//注意升序建立小堆，降序建立大堆。
//把收尾数据交换，然后把根数据向下调整
int size = n-1;
while (size > 0) {
Swap(&a[0], &a[size]);
AdjustDown(a,size,0);
size--;
}
}
堆排序的时间复杂度：
向上调整的时间复杂度：
向上调整，开始的节点是第根节点的左节点，根节点不用调整。然后依次往下走。其最后一层占一半的节点，所以消耗比较多。
总的（最坏）调整次数T(h):
公式是等比值*等差值，这里使用错位相减法来化简。
可以发现前面就是一个等比数列，可以利用等比公式化简：
满二叉树的节点数就是 2^h-1，二叉树的高度 h=log(n+1)；所以可得：
这里影响n*logn大小是其最大的影响因素，所以其时间复杂度为O(n*logn)；
向下调整的时间复杂度：
向下调整，开始的节点是第一个非叶子节点，然后依次往上走。所以开始h层的数据不用调整，是从h-1层开始调整的。
这里第一个层有2^0个节点，最多调整h-1层（不包括自己这层）。h-1层有 2^(h-2)个节点，向下调整1层。
可以归纳出公式：
总的（最坏）调整次数T(h):
公式是等比值*等差值，这里使用错位相减法来化简。
前面是0-1*(h-1)；得1-h。中间系数相减都为1。后面是2^(h-1)-0；得2^(h-1)。
可以发现前面就是一个等比数列，可以利用等比公式化简：
满二叉树的节点数就是 2^h-1，二叉树的高度 h=log(n+1)；所以可得：
这里n的大小是其最大的影响因素，所以其时间复杂度为O(n)。
