【数据结构】二叉树——顺序结构——堆及其实现

一、树

       1.1、树的概念和结构

树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成的一个具有层次关系的集合。

       树有一个特殊的节点，称为根节点，根节点没有前驱结点。

       除根节点外，其余部分被分为M（M>0）个互不相交的集合T1、T2、.....Tm，其中的每一个集合 Ti（1 <= i <= m）又是一颗结构与数类似的子树。每一颗子树的根节点都有且只有一个前驱节点，而可以有0个或者多个后继节点。

       树是递归定义的。

在树形结构中，子树之间不能存在交集

子树中存在交集，就不是树形结构了

除了根节点以外，每一个节点有且只有一个父节点

如图，E节点存在两个父节点，该图不是树形结构。

一颗N个节点的树有 N-1条边

       1.2、树的相关术语

在树形结构中，有一些相关术语：

       父节点（双亲节点）：如果一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A就是B的父节点。

       子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的子节点。

       节点的度：一个节点存在几个子节点，它的度就是多少；如上图：A的度为6、F的度为2、K的度为0.

       树的度：在一个树形结构中，最大的节点的度，称为树的度；如上图：树的度为6。

       叶子结点（终端节点）：度为0的节点就是叶子节点；简单来说，就是没有子节点（下一个节点）；如上图：B、C、H、I 等节点都是叶子结点。

       分支节点：度不为0的节点称为分支节点；如上图：D、E、F、G 等节点都是分支节点。

       兄弟节点：具有相同的父节点的节点称为兄弟节点；如上图：B和C是 兄弟节点。

       节点的层次：从树形结构的跟开始定义，跟为第 1 层，跟的子节点为第 2 层，以此类推。

       树的高度：树中节点的最大层次；如上图：树的高度是 4 。

       节点的祖先：从根到该节点所经过的分支上的所以节点。如上图：A是所有节点的祖先。

       路径：一条从树的任意节点出发，沿父节点-子节点连接，到达任意节点的序列。比如上图中A到Q的路径：A-E-J-Q。

       子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

       森林：右m（m>0）个互不相交的树组成的集合称为森林。

       1.3、树的表示

       树的表示相对于线性表就复杂了，想要存储表示起来就很麻烦了，这里既要保存值域，也要保存节点和节点之间的关系；树有很多中表示方法，就比如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法等

       这里看一下简单的孩子兄弟表示法

struct TreeNode
{
    struct Node* child; // 左边开始的第⼀个孩⼦结点
    struct Node* brother; // 指向其右边的下⼀个兄弟结点
    int data; // 结点中的数据域
};

   这样的一个树就可以表示成下面这种形式

       1.4、树形结构的分类和应用

树形结构分为很多种，具体如上图，

       树形结构实际应用：

       最典型的就是，计算机存储和管理文件的文件系统。它利用树形结构来组织和管理文件和文件夹。再文件系统中，树结构被广泛利用。通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关系

二、二叉树

       2.1、二叉树的概念与结构

       二叉树是树形结构的一种。

       根据上图，我们不难看出二叉树具备以下特点：

• 二叉树不存在度大于 2  的节点
• 二叉树的子树有左右之分，次序不能颠倒，因此，二叉树是有序树。

       2.2、特殊的二叉树

2.2.1、满二叉树

       一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是，如果二叉树的层数为k，且节点总数为2^k - 1，则它就是满二叉树。

2.2.2、完全二叉树

       完全二叉树是效率很高的 数据结构，完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时称之为完全 二叉树。要注意的是，满二叉树是一种特殊的二叉树。

2.2.3、二叉树的存储结构

       二叉树，我们可以使用两种结构存储；一种是顺序结构，另外一种就是链式结构。

顺序结构

       顺序结构，就是使用数组来存储；而数组一般只适合表示完全二叉树（如果用数组表示不完全二叉树，就会导致空间的浪费）。所以对于完全二叉树来说，就更适合使用顺序结构存储。

       我们通常使用堆（一种二叉树（数据结构））顺序结构的数组来存储二叉树顺序结构（完全二叉树）

链式结构

       对于链式结构，本篇不做详解；在下一篇文章会详细讲解二叉树的链式结构。

三、二叉树顺序结构——堆及其实现

       3.1、堆的概念

       堆是一种满足特定条件的完全二叉树，主要存在以下两种结构

小顶堆：任意节点的值 <= 其子节点的值

大顶堆：任意节点的值 >= 其子节点的值

根据图，我们可以看出堆具有一些特性：

• 最底层的节点靠左，其余层的节点都被填满
  
• 二叉树的根节点称为“堆顶”，底部最右边的节点称为“根节点”
• 大堆的堆顶元素的值是最大的；小堆的堆顶元素的值是最小的

这里补充：

       对于堆这样的数据结构存储二叉树：

对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i = 0 ， i 为根结点编号，无父节点
2. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子节点
3. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无有孩子节点

       3.2、堆的实现

       现在来实现这样一个堆结构。

堆的底层结构是一个数组，定义堆的结构

3.2.1、堆的结构

//堆的结构
typedef int HPDataType;
typedef struct HeapNode
{
  HPDataType* arr;
  int size; //有效数据个数
  int num;  //空间大小
}HP;

3.2.2、初始化和销毁

       这里堆的底层结构是数组，初始化和销毁与之前顺序表基本一样。

//初始化
void HPInit(HP* php)
{
  assert(php);
  php->arr = NULL;
  php->size = php->num = 0;
}
//销毁
void HPDesTroy(HP* php)
{
  assert(php);
  if (php->arr)
    free(php->arr);
  php->arr = NULL;
  php->size = php->num = 0;
}

3.3.3、判断堆是否为空

       判断堆是否为空，直接判断堆中数据个数是否为0即可。

//判断是否为空
bool HPEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

3.3.4、求堆中数据的个数

       因为堆结构中的size成员就是堆中数据的个数，直接返回。

//求数据个数size
int HPSize(HP* php)
{
  assert(php);
  return php->size;
}

3.3.5、插入数据

       这里向堆中插入数据，我们还要保证堆的结构不被破坏，就只好将数据插入堆之后，再调整数据（这里因为是在堆底（也就是数组的最后）插入的数据，我们就使用向上调整算法）

void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
  assert(arr);
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //小堆
    if (arr[parent] > arr[child])
    {
      Swap(&arr[parent], &arr[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
//插入数据
void HPPush(HP* php, HPDataType x)
{
  assert(php);
  //判断空间够不够
  if (php->num <= php->num)
  {
    int newnum = (php->num == 0) ? 4 : 2 * php->num;
    HPDataType* tmp = (HPDataType*)realloc(php->arr, newnum * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc filed");
      exit(1);
    }
    php->arr = tmp;
    php->num = newnum;
  }
  //空间足够，插入数据
  php->arr[php->size++] = x;
  //调整堆结构
  AdjustUp(php->arr, php->size - 1);
}

3.3.6、堆的向上调整算法

       堆的向上调整算法，这里以小堆为例

将新的数据插入到数组的尾上，我们用向上调整，直到满足堆的结构

       将元素插入到堆的末尾之后，再进行向上调整

       出入数据之后，如果不满足堆的结构（小堆就是，子节点大于父节点了），就将插入节点顺着父节点向上进行调整即可。

void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
  assert(arr);
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    //小堆
    if (arr[parent] > arr[child])
    {
      Swap(&arr[parent], &arr[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

3.3.7、删除数据

       删除数据，这里删除的是堆的堆顶数据，数据在删除后，堆结构可能被破坏，这里也需要进行调整，使用的是向下调整算法。

删除数据，先将堆顶数据和堆底数据进行调换，再从堆顶开始往下调整

//删除数据
void HPPop(HP* php)
{
  assert(php);
  Swap(&php->arr[0], &php->arr[php->size - 1]);
  php->size--;
  AdjustDown(php->arr, 0, php->size);
}

3.3.8、堆的向下调整算法

       向下调整算法，以小堆为例

如果该节点的值大于子节点，就向下调整，直到结束（结束条件，遍历完数组或者堆里的数据满足堆结构了）

void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
  assert(arr);
  int child = parent * 2 + 1;
  while (child < n)
  {
    //找到两个子节点中小的节点
    if (child<n - 1 && arr[child]>arr[child + 1])
    {
      child++;
    }
    if (arr[child] < arr[parent])
    {
      Swap(&arr[parent], &arr[child]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
    {
      break;
    }
  }
}

到这里，堆的基本操作就实现完了。

       3.3、堆的实际应用

3.3.1、堆排序

堆的一个应用就是堆排序，这里简单介绍一下，后面会有详细理解

       对于堆排序，我们可以基于本篇实现的堆结构来实现堆排序

如果要排升序，就建大堆；排降序，就排小堆。

基于堆结构来进行堆排序

void HeapSort(int* a, int n)
{
  // a数组直接建堆 
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

       这样来实现，时间复杂度为O(n*log n)。

当然，我们也可以脱离这样的堆结构，利用堆这种思想来实现堆排序，这个在后面有详细介绍。

3.3.2、TOP-K问题

       TOP-K 问题：求数据集合中前K个最大的元素或者最小的元素，（一般这样的数据量特别的大）。

而对于这种问题，能想到的最简单最直接的方法就是排序，而数据量如果很大很大，排序不可取了（数据不能一下子全部加载到内存中）。而堆就可以来解决这样的问题。

思路：

1> 取数据集合的前k个元素来建堆

       如果需要前k个最大的元素，就建小堆

       如果需要前k个最小的元素，就建大堆

2> 用剩余的数据依次和堆顶元素进行比较，如果不满足条件，就替换堆顶元素

       将剩余的元素依次和堆顶元素比较完之后，堆中剩余的k个元素就是所求的前k个最小或者最大的元素

这里简单实现一下这样的TOP-K问题

void CreateNDate()
{
  // 造数据
  int n = 100000;
  srand(time(0));
  const char* file = "data.txt";
  FILE * fin = fopen(file, "w");
  if (fin == NULL)
  {
    perror("fopen error");
    return;
  }
  for (int i = 0; i < n; ++i)
  {
    int x = (rand() + i) % 1000000;
    fprintf(fin, "%d\n", x);
  }
  fclose(fin);
}
void TOPk()
{
  int k = 0;
  printf("请输入k:");
  scanf("%d", &k);
 
  const char* file = "data.txt";
  FILE* fout = fopen(file, "r");
  if (fout == NULL)
  {
    perror("fopen fail!");
    exit(1);
  }
  int* minHeap = (int*)malloc(k * sizeof(int));
  if (minHeap == NULL)
  {
    perror("malloc fail!");
    exit(2);
  }
 
  //从文件中读取前K个数据
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minHeap[i]);
  }
 
  //建堆---小堆
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(minHeap, i, k);
  }
 
  int x = 0;
  while (fscanf(fout, "%d", &x) != EOF)
  {
    //读取到的数据跟堆顶的数据进行比较
    //比堆顶值大，交换入堆
    if (x > minHeap[0])
    {
      minHeap[0] = x;
      AdjustDown(minHeap, 0, k);
    }
  }
 
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minHeap[i]);
  }
 
  fclose(fout);
}

假设现在我们要从这十万个数据里取5个最大的数据

       先随机生成十万个数据存储到文件data.txt中，我们再设置一下这5个最大的数据

现在这5个数据是最大的（其余的数据都小于100000）

运行看一下结果 这里正是这5个数据。

感谢各位大佬支持并指出问题，

                       如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！