【数据结构】树、二叉树与堆（长期维护）（1）-阿里云开发者社区

下面是关于树、二叉树、堆的一些知识分享，有需要借鉴即可。

一、初识树（了解即可）

1.树的概念

概念：一种非线性数据结构，逻辑形态上类似倒挂的树

树的构成：由一个根+左子树+右子树构成，其中子树又可以拆分为根、左子树、右子树…

2.树的相关概念

结点的度：一个结点的孩子个数
叶节点（终端结点）：没有孩子的结点
分支节点（非终端结点）：有孩子的结点
父节点（双亲结点）：结点的上一层结点
子节点（孩子结点）：孩子
兄弟节点：相同父节点的结点
树的度：一课树中最大的结点的度
结点的层次：树的高度，从1开始计算
树的高度/深度：一棵树中最大的层次
结点的祖先：一个节点的上面层级的结点都可以是该节点的祖先
子孙：孩子，孩子的孩子…
森林：两颗或者多棵树

3.树的表示方法

树的表示方法有很多，下面来展示树的主流表示方法。

#pragma once
//方法1：结点指针数组
//前提：明确树的度
#define N 100
typedef struct TreeNode
{
  int val;
  struct TreeNode* childArr[N];//结点指针数组
}TreeNode;
//方法1：不推荐，浪费空间
//方法2：顺序表
typedef struct TreeNode
{
  int val;
  //顺序表
  struct TreeNode* arr;
  int capacity;
  int size;
}TreeNode;
//方法2：可以使用，借助其他数据结构，不够方便
//方法3：左孩子右兄弟
typedef struct TreeNode
{
  int val;
  struct TreeNode* leftchild;
  struct TreeNode* rightchild;
}TreeNode;
//方法3：十分推荐，不依赖其他数据结构，且高效表示

4.树的应用

树的应用场景最典型的两个：一是linux树状目录结构；二是windows森林状分盘

二、二叉树

(一)、初识二叉树(了解即可)

1.二叉树的相关概念

二叉树概念：二叉树属于一种特殊的树，需要具备两个条件的树才可以成为二叉树：

首先是树
树的度<=2

满二叉树的概念：一种特殊的二叉树、同时满足二叉树、且满足树的每一层都是满的

完全二叉树概念：一种特殊的二叉树、同时满足二叉树、且树前h-1层满的+第h层是自左向右是连续的

思考1：探索满二叉树/完全二叉树总结点个数与层数关系

思考2：区分各种树的包含关系？

答：

2.二叉树的意义

二叉树意义：为后面的搜索二叉树、红黑树、AVL树等高阶数据结构做铺垫。

本身树的意义并不大，二叉树的意义单从存储数据来说也没有什么意义，但是二叉树是组成搜索二叉树、哈夫曼树的基础，有了搜索二叉树大大方便数据搜索但也存在一些问题，有些搜索二叉树可能会退化为类似链表的树，因而AVL树、红黑树、M阶B树也随之而来解决问题。

3.二叉树的存储结构

一般来说二叉树具有两种存储方式，一是数组存储、二是链式存储。

顺序存储（数组存储）

//完全二叉树顺序结构表示
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
};

链式存储

思考：该如何选择存储方式？

如果是完全二叉树/满二叉树，选择顺序结构，如果是一般的二叉树，要选择链式结构进行存储。

至于为什么，下面来进行解答：

如果是完全二叉树，放在数组中，其数组下标在父子关系上存在公式，也就是说知道孩子的结点下标就可以算出父亲的数组下标，这样一来就很方便了，但如果不是完全二叉树就不具备这个关系。

父子间公式：

leftchild = 2 * parent + 1;

rightchild = 2 * parent + 2;

parent = (child - 1)/2;

4.二叉树的相关性质

拓展练习题：

(二)、堆

1.堆的概念

数据结构堆，需要满足两个条件：

是完全二叉树
父子间满足父>=子(父<=子)

注：我们称父>=子的堆为大堆，反之为小堆

下面是堆的所有接口一览：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
/*
//方法1：结点指针数组
//前提：明确树的度
#define N 100
typedef struct TreeNode
{
  int val;
  struct TreeNode* childArr[N];//结点指针数组
}TreeNode;
//方法1：不推荐，浪费空间
//方法2：顺序表
typedef struct TreeNode
{
  int val;
  //顺序表
  struct TreeNode* arr;
  int capacity;
  int size;
}TreeNode;
//方法2：可以使用，借助其他数据结构，不够方便
//方法3：左孩子右兄弟
typedef struct TreeNode
{
  int val;
  struct TreeNode* leftchild;
  struct TreeNode* rightchild;
}TreeNode;
//方法3：十分推荐，不依赖其他数据结构，且高效表示
*/
//完全二叉树顺序结构表示
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php); 
void HeapPush(HP* php, HPDataType x);
void AdjustUp(HPDataType* a, int child);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
HPDataType HeapTop(HP* php);

2.堆的初始化与销毁接口

堆的底层我们使用顺序表实现，所以堆的初始化与销毁 == 顺序表的初始化与销毁

void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->size = 0;
}
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);//本身free对空会进行检查
  php->a = NULL;
  php->capacity = php->size = 0;
}

3.堆的插入接口

思路：底层是数组，也就是顺序表，顺序表尾插成本很低，因而我们进行尾插。

问题：但是出现一个问题，尾插之后还是堆吗？（还满足父子间结点下标关系吗？）—>向上调整算法

void Swap(HPDataType* p1, HPDataType* p2)
{
  int temp = *p1;
  *p1 = *p2;
  *p2 = temp;
}
//小堆
void AdjustUp(HPDataType* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child > 0) //思考：请思考while括号内的结束条件是什么？
  {                 //提示选项如下：1.parent>=0 2.child>=0 3.child>0          
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //扩容
  if (php->capacity == php->size)
  {
    int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
    HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    if (temp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    php->a = temp;
    php->capacity = newcapacity;
  }
  
  php->a[php->size++] = x;
  AdjustUp(php->a, php->size - 1);
}

数据测试：

#include"Tree.h"
int main()
{
  int a[9] = { 1,4,7,2,5,8,3,6,9 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    HeapPush(&hp, a[i]);
  }
  HeapDestroy(&hp);
  return 0;
}

测试结果：

思考1：请思考while括号内的结束条件是什么？

提示选项如下：1.parent>=0 2.child>=0 3.child>0

答：while(child>0)，原因如下图。

思考2：向上调整的使用前提是什么？前面的数据是堆。

4.堆的删除接口

堆数据结构中规定：删除堆顶的数据。

意义：可以找出下一个最小值（最大值），也就是这一串数据中的次小值（次大值）。

怎么删除？

使用挪动数据删除,存在问题：

父子间的关系全乱
每次删除重建堆，时间复杂度(O(N^2))*

所以我们使用另一种思路：首尾交换，尾删，向下调整算法，原因如下：

首尾交换删除之后，左右子树还存在父子关系
顺序表尾删的成本低
向下调整算法时间复杂度低（O(logN)）

void AdjustDown(int* a, int size, int parent)
{
  int child = parent * 2 + 1;
  while (child < size)//思考1：while的结束条件是什么？
  {
    // 假设左孩子小，如果解设错了，更新一下
    if (child + 1 < size && a[child + 1] < a[child])//思考2：if中“child + 1 < size”的意义是什么？
    {
      ++child;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapPop(HP* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  
  AdjustDown(php->a, php->size, 0);
}

思考1：while中的条件是什么？

答：child < size

思考2：if中“child + 1 < size”的意义是什么？防止右孩子不存在。

思考3：向下调整算法的使用前提条件是什么？左右子树保证是堆。

测试（删除接口的意义之一）：删除的应用：用来找一列数中前k小/大的K个数字：

#include"Tree.h"
int main()
{
  int a[9] = { 1,4,7,2,5,8,3,6,9 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    HeapPush(&hp, a[i]);
  }
  //假设找堆中前三小的数字
  for (int i = 0; i < 3; i++)
  {
    int num = hp.a[0];
    HeapPop(&hp);
    printf("%d ", num);
  }
  HeapDestroy(&hp);
  return 0;
}

5.其他接口

bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
HPDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}

测试（堆的意义之一），可以打印出一组有序数据（注：这里并不是堆排序）：

思考：为什么打印出有序数据!=堆排序？

答：两者的最大区别在于两点

有序打印没有改变原数组，而堆排序是对原数组进行排序

有序打印需要空间复杂度为O(N)，而堆排序空间复杂度O(1)

#include"Tree.h"
int main()
{
  int a[9] = { 1,4,7,2,5,8,3,6,9 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    HeapPush(&hp, a[i]);
  }
  假设找堆中前三小的数字
  //for (int i = 0; i < 3; i++)
  //{
  //  int num = hp.a[0];
  //  HeapPop(&hp);
  //  printf("%d ", num);
  //}
  while (!HeapEmpty(&hp))
  {
    printf("%d ", HeapTop(&hp));
    HeapPop(&hp);
  }
  HeapDestroy(&hp);
  //system("pause");
  return 0;
}

6.堆排序的应用：TopK问题

场景：如果现在有100亿的个整形数据，找出前一百个小的值。

方法1：对100亿个数据建堆，top，pop一百次即可。
显然这种方法有问题，下面为分析：
方法2：升序，借助堆
思想：排升序，建K个值大小的大堆，然后让(10亿-K)个数据依次与大堆中的堆顶进行比较，比堆顶小的值进行替换，然后向下调整…不断进行比较，直到结束。

思考1：为什么排升序要建大堆？

这其实利用了大堆的小数向下沉的性质，从而巧妙地保护了小数，防止小数被替换掉。

思考2：排升序建小堆可以吗？

可以，但是因为效率低下，还不如冒泡排序效率高。

下面是1万的数据的代码示例：

void MakeData()
{
  int n = 10000;
  srand(time(0));
  const char* pfile = "data.txt";
  FILE* pf = fopen(pfile, "w");
  if (pf == NULL)
  {
    perror("open fail");
    exit(-1);
  }
  for (int i = 0; i < n; i++)
  {
    int num = rand()%1000;
    fprintf(pf, "%d\n", num);
  }
  fclose(pf);
}
void Select_TopK(int n)
{
  int k = 10;
  FILE* pf = fopen("data.txt", "r");
  if (pf == NULL)
  {
    perror("fopen 'r' fail");
  }
  //建堆
  HPDataType* minheap = (HPDataType*)malloc(sizeof(HPDataType) * k);
  if (minheap == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  for (int i = 0; i < k; i++)
  {
    fscanf(pf, "%d", &minheap[i]);
  }
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(minheap, k, i);
  }
  int x = 0;
  while (fscanf(pf, "%d", &x) != EOF)
  {
    // 读取剩余数据，比堆顶的值大，就替换他进堆
    if (x > minheap[0])
    {
      minheap[0] = x;
      AdjustDown(minheap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minheap[i]);
  }
  
  free(minheap);
  fclose(pf);
}
test_TopK()
{
  //MakeData();
  Select_TopK(10000);
}
int main()
{
  //test_heap();
  test_TopK();
  return 0;
}

小技巧1：在面对庞大数据的随机数选前最值时候，如何快速测试自己代码得到结果是对的？

首先要控制数据范围，然后手动随机对每个数据修改为最值，看是否代码可以选出来。

小技巧2：手动条件断点，如果上面代码我只想看大于1万的值是怎么进堆的，所以我可以这样：

冷知识：没有完整语句的地方不能打断点，下面定义xx = 0目的在于打断点。

7.堆排序

方法1：借用堆push接口实现堆排序。
过程略。
方法2：对数组直接进行建堆，大致过程如下：

假如说要对N个数的数组进行排序，要求降序

第一步建堆：

思想：将数组中第一个视为堆，将第二个数字进行向上调整，使前两个数字成为堆，将第三个数字向上调整…以此类推，对整个数组向上调整。

显然，现在这只是形成了小堆，并不是有序并且也不是降序。

思考：在数组直接建堆时候可以用向下调整算法吗？

可以，只需要从倒数第一个非叶子开始，依次向上对每个结点进行调整就好了。

思考：为什么要从倒数第一个非叶子开始使用向下调整算法？

因为向下调整算法的使用前提是左右子树是堆。

第二步：选数排序：

思想：建好小堆之后，首尾交换，再将尾数据不视为堆，这样，最小的数字就到了最后，同理，再次对前N-1个数字进行建堆，然后首尾交换，这样第二小的数字就到了倒数第二个位置…以此类推。

思考：如果要升序，建大堆还是小堆，如果要降序，建大堆还是小堆？为什么？

答：

升序 —> 建大堆

降序 —> 建小堆
至于为什么，是因为无论大堆还是小堆，只能确保堆顶的数据是最大值/最小值，而我们利用了堆删除接口的思想，首尾交换，因而说升序 —> 建大堆 - 降序 —> 建小堆。

void HeapSort(int* a, int n)
{
  // a数组直接建堆 O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)//思考：while的结束条件是什么？
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

【数据结构】树、二叉树与堆（长期维护）（1）

一、初识树（了解即可）

1.树的概念

2.树的相关概念

3.树的表示方法

4.树的应用

二、二叉树

(一)、初识二叉树(了解即可)

1.二叉树的相关概念

2.二叉树的意义

3.二叉树的存储结构

4.二叉树的相关性质

(二)、堆

1.堆的概念

2.堆的初始化与销毁接口

3.堆的插入接口

4.堆的删除接口

测试（删除接口的意义之一）：删除的应用：用来找一列数中前k小/大的K个数字：

5.其他接口

6.堆排序的应用：TopK问题

7.堆排序

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】树、二叉树与堆（长期维护）（1）

一、初识树（了解即可）

1.树的概念

2.树的相关概念

3.树的表示方法

4.树的应用

二、二叉树

(一)、初识二叉树(了解即可)

1.二叉树的相关概念

2.二叉树的意义

3.二叉树的存储结构

4.二叉树的相关性质

(二)、堆

1.堆的概念

2.堆的初始化与销毁接口

3.堆的插入接口

4.堆的删除接口

测试（删除接口的意义之一）：删除的应用：用来找一列数中前k小/大的K个数字：

5.其他接口

6.堆排序的应用：TopK问题

7.堆排序

热门文章

最新文章

相关课程

相关电子书