二叉树（补充）

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中的breakwhile (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，因为左孩子和右孩子之间就相差1child++;}//孩子结点大于父节点，就需要交换，保证大堆的特性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]);//堆数据个数-1heap->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)，而向下调整就有点难以看出来了，我们来计算一下