二叉树（补充）
二叉树
- 1.二叉树的基本特性
- 2.堆
- 2.1.堆的基本概念
- 2.2.堆的实现
- 2.2.1.基本结构
- 2.2.2.堆的初始化
- 2.2.3.堆的销毁
- 2.2.4.堆的插入
- 2.2.5.取出堆顶的数据
- 2.2.6.堆的删除
- 2.2.7.堆的判空
- 2.2.8.堆的数据个数
- 2.2.9.交换
- 2.2.10.打印堆数据
- 2.2.11.堆的创建
- 2.2.12.堆排序
1.二叉树的基本特性
上图展示的就是二叉树，我将它的规律也写在上面了
一般我们把二叉树的高度设置从1开始，从0开始的话，空树就是-1，就不太合适了
一棵N个结点的树有N-1条边
假设二叉树的第k层是满的，它的结点数为2^(k-1)个
我们的二叉树还分为满二叉树和完全二叉树，下图展示了二者的对比图
满二叉树：一个二叉树，如果每一层的结点都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2^k-1,则就是满二叉树。
完全二叉树：前N-1层是满的，最后一层可以不满，但是必须从左往右是连续的，满二叉树是一种特殊的完全二叉树。
我们先来分析一下满二叉树的特性：
假设满二叉树有k层，则它的最后一层的结点有2^(k-1)个
假设满二叉树有k层，一棵满二叉树一共有2^k-1个结点，计算方法如下：
其实还有一个小技巧：我们的二进制的每一位的值和二叉树的每一层的结点数相等的，假设我们的二进制为11111111，它是一个unsigned char类型的最大值，此时我们计算它的十进制就通过它的再高一位的值-1计算得出，即2^8-1=255。类比到二叉树，即下一层的结点数-1，设最后一层的结点个数为2 ^3，第4层，计算整棵二叉树的结点数为2 ^4-1。
设满二叉树的总结点数为N个，
树的高度为log₂(N+1)，通过2^k-1=N计算可得
完全二叉树的特性：
设完全二叉树有k层，完全二叉树总共结点最少就是最后一层只有一个，即2^(k-1)个；最多也就是满二叉树，即2 ^k-1个结点
最多不用讲怎么计算了，最少可以用之前讲的错位相减法来计算，也可以二叉树的规律来算：假设完全二叉树一共k层；那么根据前面讲的，除去最后一层一个结点，它就是一棵满二叉树，共k-1层，根据满二叉树的总共结点公式，总结点数为2^ (k-1)-1个；那么再加上去掉的一个结点，完全二叉树的总结点数即为2^(k-1)个，如下图
对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n2=n0+1
2.堆
2.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否则无右孩子
2.2.堆的实现
2.2.1.基本结构
//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型
typedef struct Heap
{
T* arr;//堆的存储位置
int size;//堆的数据个数
int capacity;//堆的容量
}Heap;
void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空
void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
上述代码已经将存储堆的结构体已经写好，同时把我们的堆的各种函数调用已经声明好了
2.2.2.堆的初始化
void HeapInit(Heap* heap)//堆的初始化
{
assert(heap);
heap->arr = NULL;
heap->capacity = heap->size = 0;
}
我们这边的写法是一开始不给数组任何的空间，后期直接使用realloc开辟
2.2.3.堆的销毁
void HeapDestory(Heap* heap)//将堆销毁
{
assert(heap);
free(heap->arr);//释放空间
heap->size = heap->capacity = 0;
}
不要忘记释放开辟的空间！！！
2.2.4.堆的插入
由于我们数组的特性，头插需要移动元素什么的，效率极低，但是可以尾插，所以说堆一般性就都是在尾部插入
//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{
int parent = (child - 1) / 2;//找父结点
//使用parent>=0有点不合理，倒数第二次运行循环时child已经是0了，应该结束
//但是（child-1）/2导致parent依旧为0，再次进入循环，然后通过else中的break
while (child>0)
{
//孩子结点大于父结点
if (arr[child] > arr[parent])
{
//交换
swap(&arr[child], &arr[parent]);
//继续向上调整
child = parent;
parent = (child - 1) / 2;
}
else
{
//如果孩子结点小于父结点，就不用向上调整了
break;
}
}
}
void HeapPush(Heap* heap, T x)//堆的插入
{
assert(heap);
//空间不足开辟内存
if (heap->size == heap->capacity)
{
int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;
//realloc的第一个元素是NULL的话，功能和malloc一样
T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));
if (newarr == NULL)
{
perror("realloc fail");
exit(-1);
}
//修改已经开辟好空间后的信息
heap->arr = newarr;//realloc可能不在原位扩容，所以说这一步是必要的
heap->capacity = newcapacity;
}
//正式插入
heap->arr[heap->size] = x;
heap->size++;//数据个数+1
//向上调整，保证是一个堆
AdjustUp(heap->arr, heap->size - 1);
}
我们默认建立的是大堆哈，如果想要建立小堆，只需要将向上调整中的比较孩子结点和父结点的>变成<即可
代码和图片也展示在了上面，可以通过图片来理解一下，之所以这样写是因为我们在没有进行插入前，我们的结构肯定是堆的，但是插入后，我们需要进行调整才能保证堆的结构，我们写的是大堆，
因此需要和父结点进行比较，如果比父结点大，那么继续交换。但是由于交换后，可能还是比祖父结点大，也就还需要不停地调整。向上调整是对插入结点的祖先进行调整
2.2.5.取出堆顶的数据
T HeapTop(Heap* heap)//取出堆顶数据
{
assert(heap);
assert(heap->size > 0);
return heap->arr[0];
}
我们的可以用于Top-k问题，举个例子，我们在10000个人里面，选出最有钱的人，我们的堆就发挥了大用处，因为它的堆顶的数据，即数组第一个元素是最大（最小）的，我们只需要取出后，再删除就可以选出第二大的…第n大的，因此我们还需要来实现一下删除才能彻底理解
2.2.6.堆的删除
void AdjustDown(T* arr, int size,int parent)
{
//选出左孩子和右孩子中较大的那个
//假设较大的是左孩子
int child = parent * 2 + 1;
//孩子结点存在才向下调整
while (child<size)
{
if (child + 1 < size && arr[child + 1] > arr[child])
{
//进行判断，如果右孩子大于左孩子，就+1，因为左孩子和右孩子之间就相差1
child++;
}
//孩子结点大于父节点，就需要交换，保证大堆的特性
if (arr[child] > arr[parent])
{
swap(&arr[child], &arr[parent]);
//继续向下调整
parent = child;
child = parent * 2 + 1;
}
else
{
//如果孩子结点小于父结点，说明不需要调整了，跳出循环
break;
}
}
}
void HeapPop(Heap* heap)//删除堆顶数据
{
assert(heap);
assert(heap->size>0);
//先将堆顶的元素和最后一个元素进行交换
swap(&heap->arr[0], &heap->arr[heap->size - 1]);
//堆数据个数-1
heap->size--;
//向下调整
AdjustDown(heap->arr,heap->size,0);
}
上面已经给出了代码和交换的图片，我们首先来讲一下为什么需要通过交换才能删除这个最大（最小）元素，究其原因还是它在根节点的原因，没有办法对它进行一个直接删除，一旦直接删除，就会导致整体的一个堆结构就乱掉了。我们根结点的左子树和右子树是堆，不能破坏它，那么最好的方法就是和尾元素进行交换，然后进行向下调整，这样不但保证了结构的完整性，效率还高。
向下调整如下图:
2.2.7.堆的判空
bool HeapEmpty(Heap* heap)//堆是否为空
{
assert(heap);
return heap->size == 0;
}
2.2.8.堆的数据个数
int HeapSize(Heap* heap)//堆的数据个数
{
assert(heap);
return heap->size;
}
2.2.9.交换
void swap(T* x, T* y)//交换
{
T tmp = *x;
*x = *y;
*y = tmp;
}
2.2.10.打印堆数据
void HeapPrint(Heap* heap)//将堆数据打印出来
{
for (int i = 0; i < heap->size; ++i)
{
printf("%d ", heap->arr[i]);
}
printf("\n");
}
2.2.11.堆的创建
//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{
assert(heap);
HeapInit(heap);
for (int i = 0; i < n; i++)
{
HeapPush(heap, a[i]);
}
}
void AdjustDown(T* arr, int size, int parent);//定义在下面，这边要使用，声明一下
void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{
assert(heap);
HeapInit(heap);
//开辟空间
heap->arr = (T*)malloc(sizeof(T) * n);
if (heap->arr == NULL)
{
perror("malloc fail");
exit(-1);
}
//拷贝数据
memcpy(heap->arr, a, n*sizeof(T));
heap->size = heap->capacity = n;
//从下至上进行向下调整
for (int end = (n - 1 - 1) / 2; end >= 0; end--)
{
AdjustDown(heap->arr, n, end);
}
}
上面展示了代码和图片，堆的创建我们用了两种方法，第一种就比较直接，循环push即可，但它的效率不是很高，于是我们有了第二种方法，想要保证一组毫无序列的元素变成堆，就需要保证每一个子树的父节点都大于（小于）孩子节点，因此我们只能从最后一棵子树开始向下调整（叶子结点不需要调整了），这样当调整到上一层时，下层都已经是堆了，只需要对当前节点也是向下调整即可。一直到根节点完成最后一次向下调整就可以完成堆的构建。
在代码中end两次-1，第一次-1是为了找到最后一个元素在数组中的位置，第二次-1是为了找到父结点。
2.2.12.堆排序
在我们讲述堆排序前，我们先来讨论一下，当我们对于一个随机的数组，将它变成一个堆，是使用向上调整好还是向下调整好呢？我们接下来分析一下
可以看到，向下调整和向上调整都能建堆，如果简单来看的话会认为向上调整的时间复杂度是都是O(N*logN)，而向下调整就有点难以看出来了，我们来计算一下
