📔一.二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

📕（1）顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

📖（2）链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，以后学到高阶数据结构如红黑树等会用到三叉链。

二叉树的二叉链表三叉链表存储结构

// 二叉链
struct BinaryTreeNode
{
  struct BinTreeNode* _pLeft; // 指向当前节点左孩子
  struct BinTreeNode* _pRight; // 指向当前节点右孩子
  BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{
  struct BinTreeNode* _pParent; // 指向当前节点的双亲
  struct BinTreeNode* _pLeft; // 指向当前节点左孩子
  struct BinTreeNode* _pRight; // 指向当前节点右孩子
  BTDataType _data; // 当前节点值域
};

💰二.二叉树的顺序存储结构的实现

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的孩子和父亲下标关系：

🪙（1）堆的概念及结构

堆是一个可以看成完全二叉树的数组对象，在将它看成完全二叉树时候，完全二叉树的每一个父亲结点的值总是大于（小于）孩子结点的值，我们称之为大堆（小堆）或者大根堆（小根堆）。

堆得性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

小堆结构图

大堆结构图

🍗（2）堆的实现

🥞1.堆结构的定义初始化，及销毁

由于堆是一个可以看成完全二叉树的数组对象，所以在实现堆及其相关操作的时候，实际上都是对顺序表的操作。

typedef struct Heap
{
  HPDateType* a;    //数据域
  int size;         //数据个数
  int capacity;     //容量
}Heap;

//初始化
void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->size = 0;
}

//堆的销毁
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->capacity = php->size = 0;
}

🧇2.堆的插入

堆的插入需要保证插入以后还是一个堆，所以这里用到了向上调整算法。

在数组中就是，插入一个数在数组的尾上，再通过向上调整算法，调整到合适的位置。

在以堆的角度来看（小堆）为例，将新插入的值看作孩子与其父亲位置的值比较，如果比父亲位置的值还要小，那就将该值与父亲位置的值进行交换，交换后将父亲位置当作新的孩子，继续与其父亲位置的值比较，这样一直向上比较并交换，直到父亲位置的值比自己小或该位置已经没有父亲了，调整结束。

代码：

//交换
void Swap(HPDateType* n1, HPDateType* n2)
{
  HPDateType tmp = *n1;
  *n1 = *n2;
  *n2 = tmp;
}
//判断是否需要扩容
void JudgeCapacity(Heap*php)
{
  assert(php);
  if (php->capacity == php->size)
  {
    int newcaprcity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDateType* tmp = realloc(php->a, sizeof(HPDateType) * newcaprcity);
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcaprcity;
  }
}
//向上调整算法
void AdjustUp(HPDateType* a, int size, 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 HeapPush(Heap* php, HPDateType x)
{
  assert(php);
    //判断时候需要扩容
  JudgeCapacity(php);
    //在数组的尾上插入数据
  php->a[php->size++] = x;
    //将新插入的数据进行向上调整
  AdjustUp(php->a, php->size,php->size - 1);
}

测试：

void Print(Heap* php)
{
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
}
int main()
{
  //定义
  Heap hp;
  //初始化
  HeapInit(&hp);
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  int n = sizeof(array) / sizeof(array[0]);
  //数组数据一次插入堆中
  for (int i = 0; i < n; i++)
  {
    HeapPush(&hp, array[i]);
  }
  //打印堆的内容
  Print(&hp);
  //销毁堆
  HeapDestroy(&hp);
  return 0;
}

每一次插入都会经过一次向上调整，最后生成的就是妥妥的小堆。

🧀3.堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。这里用到的就是向下调整算法。

向下调整算法（大堆为例）:从第一个非叶子结点开始，找到其孩子结点中较大的一个与父亲位置进行交换，然后将孩子作为新的父亲，再次比较和交换，直到父亲结点比两个结点的值都大或者已经没有孩子了为止。

从第一个不为叶子的结点开始，一次往前都进行向下调整，最后得到的就是堆。

代码：

void Swap(HPDateType* n1, HPDateType* n2)
{
  HPDateType tmp = *n1;
  *n1 = *n2;
  *n2 = tmp;
}
//向下调整算法(大堆)
void AdjustDown(HPDateType* arr,int n, int parent)
{
    //找到第一个孩子
  int child = parent * 2 + 1;
  while (child < n)//求出的孩子，已经超过数组下标的大小
  {
        //与第二个孩子比较大小
    if (child + 1 < n && arr[child] < arr[child + 1])
    {
      child++;
    }
        //与其父亲的值比较，如果孩子的值比父亲大，就交换
    if (arr[child] > arr[parent])
    {
      Swap(&arr[child], &arr[parent]);
            //将孩子作为新的父亲，并找到新的孩子，继续进行比较
      parent = child;
      child = parent * 2 + 1;
    }
    else//如果父亲的值比孩子的大，此时以该父亲为根的完全二叉树已经是堆
    {
      break;
    }
  }
}
//对已经给出的数组进行建堆
void HeapCreate(Heap* php, HPDateType* arr, int n)
{
  assert(php);
    //初始化堆
  php->a = (HPDateType*)malloc(sizeof(HPDateType) * n);
  php->capacity = n;
  php->size = n;
    //数据拷贝到堆中
  memmove(php->a,arr,sizeof(arr[0]) * n);
  //找到第一个非叶子结点，并依次向下调整
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->a, n,i);
  }
}

测试：

void Print(Heap* php)
{
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
}
int main()
{
  //定义
  Heap hp;
  //初始化
  HeapInit(&hp);
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  int n = sizeof(array) / sizeof(array[0]);
  HeapCreate(&hp, array, n);
  //打印堆的内容
  Print(&hp);
  //销毁堆
  HeapDestroy(&hp);
  return 0;
}

🥣4. 堆的删除：

堆的删除删除堆顶数据，需要保证删除以后还是一个堆，我们通常的做法就是，将堆顶数据与堆的最后数据进行交换，再将堆的数据个数减一，为了保证删除以后还是一个堆，再将堆顶数据进行向下调整。

堆的删除

代码:

//堆的删除，删除堆顶数据，并保证删除以后仍是堆
void HeapPop(Heap* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&php->a[0], &php->a[php->size]-1);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}

测试：

void Print(Heap* php)
{
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
int main()
{
  //定义
  Heap hp;
  //初始化
  HeapInit(&hp);
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  int n = sizeof(array) / sizeof(array[0]);
  HeapCreate(&hp, array, n);
  Print(&hp);
  HeapPop(&hp);
  Print(&hp);
  HeapPop(&hp);
  Print(&hp);
  //销毁堆
  HeapDestroy(&hp);
  return 0;
}

🍿 5.拿到堆顶数据

//拿到堆顶数据
HPDateType HeapTop(Heap* php)
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}

🥗 6.堆的数据个数

//堆的数据个数
int HeapSize(Heap* php)
{
  assert(php);
  return php->size;
}

🍘7.堆的判空

bool HeapEmpty(Heap* php)
{
  assert(php);
  return php->size == 0;
}

🍙8.TopK问题

第一类TopK问题：

假如我们有一组数据，现在的需求就是，找这一组数据中的前k大的k个数。首先将数据建堆，我们可以通过不断地从大堆里面选堆顶数据的数，再将堆顶数据删除，循环选出k个数，这样选出来的就是前k大的k个数。

代码：

//topk问题
void HeapTopK(Heap* php, int k)
{
  assert(php);
  assert(k > 0);
  for (int i = 0; i < k; i++)
  {
    printf("%d ", HeapTop(php));
    HeapPop(php);
  }
  printf("\n");
}

测试：

int main()
{
  //定义
  Heap hp;
  //初始化
  HeapInit(&hp);
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  int n = sizeof(array) / sizeof(array[0]);
  HeapCreate(&hp, array, n);
  //选出前3大的3个数据
  HeapTopK(&hp, 3);
  //销毁堆
  HeapDestroy(&hp);
  return 0;
}

第二类TopK问题：

上述的TopK问题，有的小伙伴想到我们用一个排序，也能解决问题呀，为啥非要建堆呢？但是如果我们的数据量非常的大，数据有100G大小存储在我们的磁盘里面，此时我们再想寻选出TopK，如果使用排序就需要把数据加载到内存中，这个时候电脑的内存是不够加载的，也就无法排序；日过我们使用堆，我们只需要建可以容纳K个数据小堆，每次从磁盘中读取一个数据，读取的数据与堆顶数据比较，去过比堆顶数据大，就将该数据赋值到堆顶，并将堆顶数据进行一次向下调整，保证堆顶数据一直是堆中最小的。这里大家可以想象是打擂台。

注意：这里再选前K大的数的时候，只能建小堆，如果建大堆，我们读取的第一个数就是最大，并且放在了堆顶，后面的数据，就会被堵在外面，堆中的数据就会无法更新。

代码:

//topk 文件大数据量
void TopK_File(int k)
{
  //造数据,造1000个10000以下的随机数
  FILE* pfile = fopen("test.txt", "w");
  srand(time(0));
  for (int i = 0; i < 1000; i++)
  {
    fprintf(pfile, "%d\n", rand() % 10000);
  }
    fclose(pfile);
  //建小堆
  Heap hp;
  HeapInit(&hp);
  int* arr = (int*)malloc(sizeof(arr[0]) * k);
  for (int i = 0; i < k; i++)
  {
    arr[i] = INT_MIN;
  }
  HeapCreate(&hp, arr, k);
  //topK 选数
  FILE* pfile_ = fopen("test.txt", "r");  
  for (int i = 0; i < 1000; i++)
  {
    int tmp = 0;
    fscanf(pfile,"%d", &tmp);
    int hptop = HeapTop(&hp);
        //文件中读取的数据与堆顶数据比较
    if (tmp > hptop)
    {
      hp.a[0] = tmp;
      AdjustDown(hp.a, k, 0);
    }
  }
  fclose(pfile_);
  Print(&hp);
    HeapDestroy(&hp);
}

测试：

int main()
{
  //前5大的5个数据
  TopK_File(5);
}

🍛三.时间复杂度分析：

🍡（1）向上调整算法，插入建堆的时间复杂苏分析：

🥟（2）向下调整算法，直接建堆的时间复杂苏分析：

🥡 四.堆排序

🍠（1）排序思想

利用堆来排序主要有两个步骤：

1.建堆：排升序建大堆，排降序建小堆

2.利用堆删除的思想经行排序

首先我们来针对，排升序建大堆，来解释一下，我们知道大堆堆顶数据，是最大数据，如果我们将顶数据与最够一个数据进行交换，这样我们就可以将最大的数放在了最后，除去最后一个数据，将其他数据按栈顶数据数据进行向下调整。依次这样就可以达到排序的效果。

🍱（2）代码代码：

void HeapSort(int *arr,int n)
{
  //建大堆，选择时间复杂度比较小，向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
  //选数，排序
  int end = n - 1;
  while (end)
  {
        //每次选出堆顶数据往后放
    Swap(&arr[0], &arr[end]);
    AdjustDown(arr, end, 0);
    end--;
  }
}

数据结构——二叉树2.0