今天，我们来写一篇关于数据结构的二叉树的知识。
在学习真正的二叉树之前，我们必不可少的先了解一下二叉树的相关概念。
一：树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
除了根结点外，每个结点有且仅有一个父结点
一颗N节点的树又N-1条边
下面我们来具体给出树的相关名词：
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点树的度：
一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林
标注：红色的为常用的，橙色为概念
有了上面的铺垫后，我们来认识一下二叉树：
二叉树
图：
二叉树组成：
由三部分：根，左子树（左孩子），右子树（右孩子）
从上面，我们知道：
1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
3. 存在情况：
接下来，我们认识
特殊的二叉树：
1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
证明：满二叉树中高度为h的有多少个结点？
完全二叉树：前h-1都是满的
最后一层要求从左到右是连续的高度为h的完全二叉数，节点数量的范围是[2^(h-1),2^h-1]
由上面知道满二叉树为2^h-1.
根据完全二叉树的定义
2^(h-1)-1----不算最后一层的。然后再算最后一层：2^(h-1)-1+1==2^(h-1)
所以，它的范围：[2^(h-1),2^h-1]。
此外，对任何一颗二叉树，如果度为0的叶结点个数为n0，度为2的分支节点为2 ，则由n0=n2+1.
结论：度为0的永远比度为2的多1。
二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，
我们知道：顺序表是都一样的，实际上就是数组嘛
而链表不一样，我们通常用箭头那些是想象出来的，实际上并没有箭头的。
同样，二叉树也是：
逻辑结构 想象出来的
物理结构 实实在在内存中是如何存储的
反向过来，你把这棵树的一层一层的值依次往数组里面存储
如下图：
逻辑结构：（想象成这样）
物理结构：（实际就是数组）
另外，我们平时画图的时候，很麻烦画出第一张图那么标准，其实，我们也是可以画出这样子
简便：
通过观察上面得出的规律：
表示二叉树的值在数组位置中的父子下标关系
parent=（child-1）/2
leftchlid=parent*2+1
rightchlid=parent*2+2
注意，这里必须是从0开始，不然就乱了
有人会问了，能不能在完全二叉树那里使用呢？
这里用数组存储完全二叉数，有局限不适合。
因为浪费很多空间，数组存储表示二叉树只适合完全二叉树。
好了，有了上面的铺垫后，现在让我们来实现一下堆。
堆
概念：
什么是堆呢？
我们将堆分为大堆和小堆
小堆
大堆：
在写堆时，底层代码实际就是数组
注意：堆不是排序，堆只规定父亲的大小，并没有规定它的左右孩子的大小
插入时，可能会影响部分祖先。
实际控制的是数组，写的时候把它想象成树
一：定义结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;1.需要一个数组
2.要算出数组的大小
3.最大容量
二：初始化部分
void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}这里初始化跟之前的都差不多。
1.创建数组，用malloc
2.初始化size为0；
3.因为上面创建了数组：4个位置，所以初始化时的最大容量为4。
三：销毁部分
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}1.置空，置零就可以了。
四：Push部分
首先，我们得思考一下，堆咋push的。
由于本质上是数组，所以我们push在数组的最后那里插。
假如在下面数组push一个数字60.
因此我们会写成这样一个代码：
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;调整部分下面有讲AdjustUp(php->a, php->size - 1);
}但是呢，如果是像上面一样push了一个数字的话，堆就乱了：
变成了
面对这种问题，我们又该怎么办呢？
这里我们使用一种叫向上调整法解决这种问题：
我们以大堆来举例子：
我们发现上面是不是将30和60的位置交换了，就可以重新变成大堆了？
那么，我们又是怎么变成这一步的呢？
不能发现，你看
1.将分为左孩子和右孩子和根三部分。
2.比较左孩子和右孩子，拿出大的孩子，再跟根比较。
3.如果大的孩子的数字大于根，就交换。反之不换。
对上述做法叫做向上调整法。
对此我们写一个函数：
向上调整部分
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while(child > 0){if (a[child] > a[parent]){交换Swap(&a[child], &a[parent]);更新child = parent;parent = (child - 1) / 2;}else{break;}}
}解读：
除了child这个位置，前面数据构成堆
1.我们是不是得找到父亲结点。上面我们已经给出了父亲与孩子之间的公式变换了
2.由于交换这个代码内容在后面也是常用到的，所以我们单独封装一个函数
交换部分
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}3.这样容易忽略的问题是：
while的条件：弄成 while(child > 0) 而不要弄成while (parent >= 0)
这里看似都没有问题运行时，但是会不好。
parent >= 0，意味着parent<0才会中止，但是，parent会小于0吗？不会，因为这里最差的情况就是孩子等于0.
parent = (child - 1) / 2;即就是-1/2，按理是0.5，但是这里是整形，所以还是0，还是会进入循环。
但是呢？这个程序不会死循环，parent=0时，进入循环，但是它不满足if (a[child] > a[parent])条件，所以还是会到达break。
所以能正常跑，但是不好，最好用child>0.
删除部分
void HeapPop(HP* php)
{assert(php);后面讲到assert(!HeapEmpty(php));// 删除数据Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}
堆的删除部分，有人可能会想直接这样删
但是，接下来的堆就会变成这样：
直接挪动删除 ：
1.效率低下。
2.父子兄弟关系全乱了。
那么，我们想到用间接的方法来解决这种问题：
1.我们先把第一个和最后一个交换。
2.删除最后一个。
3.接着向下调整法。
1）什么是向下调整法，即从上面往下调
1.找到孩子中大的数字，与父亲比较，孩子大的就交换。反之不交换
向下调整部分
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩子中大的那一个if (child + 1 < n && a[child+1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}1.这里采用的是假设左孩子大，然后再循环里面再弄个if语句，如果右孩子大的话，就交换变成右孩子。（因为左右孩子再邻位，相差1）
2.接着再比较父亲结点，与大的孩子，大就交换，再更新父亲结点和孩子结点。反之就break，跳出循环。
返回顶位置
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}判断空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}返回大小
int HeapSize(HP* php)
{assert(php);return php->size;
}好了，最后
附上总代码
Heap.h部分
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPTypeData;
typedef struct Heap
{HPTypeData* a;int size;int capacity;}Heap;void HPInit(Heap* php);
void HPDestory(Heap* php);
void HPPush(Heap* php, HPTypeData x);
void HPPop(Heap* php);
HPTypeData HPtop(Heap* php);
bool HPEmpty(Heap* php);
int HPSize(Heap* php);Heap.c部分
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HPInit(Heap* php)
{assert(php);php->a =(HPTypeData*)malloc(sizeof(HPTypeData)*4);if (php->a == NULL){perror("malloc fail");return;}php->capacity = 4;php->size = 0;
}
void HPDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}void Swap(HPTypeData* p1,HPTypeData* p2)
{HPTypeData temp = *p1;*p1 = *p2;*p2 = temp;
}
void Adjustup(HPTypeData* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}
void HPPush(Heap* php, HPTypeData x)
{assert(php);if (php->a == php->capacity){HPTypeData* temp = (HPTypeData*)realloc(php->a, sizeof(HPTypeData) * php->capacity * 2);if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity *= 2;}php->a[php->size] = x;php->size++;//Adjustup(php->a,php->a[php->size-1]);Adjustup(php->a,php->size-1);}Adjustdown(HPTypeData* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[parent],&a[child]);parent = child;child= parent * 2 + 1;}else{break;}}
}
void HPPop(Heap* php)
{assert(php);assert(!HPEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;Adjustdown(php->a, php->size, 0);
}
HPTypeData HPtop(Heap* php)
{assert(php);return php->a[0];
}
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}
int HPSize(Heap* php)
{assert(php);return php->size;
}test.c部分
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"//int main()
//{
// HP hp;
// HeapInit(&hp);
// HeapPush(&hp, 4);
// HeapPush(&hp, 18);
// HeapPush(&hp, 42);
// HeapPush(&hp, 12);
// HeapPush(&hp, 21);
// HeapPush(&hp, 3);
// HeapPush(&hp, 5);
// HeapPush(&hp, 5);
// HeapPush(&hp, 50);
// HeapPush(&hp, 5);
// HeapPush(&hp, 5);
// HeapPush(&hp, 15);
// HeapPush(&hp, 5);
// HeapPush(&hp, 45);
// HeapPush(&hp, 5);
//
// int k = 0;
// scanf("%d", &k);
// while (!HeapEmpty(&hp) && k--)
// {
// printf("%d ", HeapTop(&hp));
// HeapPop(&hp);
// }
// printf("\n");
//
// return 0;
//}// 排升序 -- 建大堆
void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆for (int i = 1; i < n; ++i){AdjustUp(a, i);}// 自己先实现}int main()
{int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序HeapSort(a, 10);return 0;
}最后，到了本次鸡汤部分：
小小的人，有大大的梦想！干！
