【数据结构】长幼有序：树、二叉树、堆与TOP-K问题的层次解析（含源码）

为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有好坏之分，而评估数据结构的好坏要针对场景，就如我们已经学习的结构而言，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。 因此，不同的场景我们选择不同的数据结构

---

一、树

1.树的基本概念

       树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

       有一个特殊的结点，称为根结点，根结点没有前驱结点，如下图中A是根节点，前驱节点指的就是c的前面的节点A(前驱)。在树中有且仅有一个根节点

图1:

       除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义递归定义的。

        解释： 整棵树可以看成一个大集合，A就是根节点，而大集合可以分成一个个独立的小集合称为子树，如以B为根节点的小集合，C和D也可以看成集合，但要注意的是每个集合互不相交，如下图子树均相交则不是树而是图，在后续的博客会有介绍

图3：

       注意：因为是有限结点组成一个具有层次关系的集合，所以树在逻辑结构上就不是线性的。我们在生活中经常看到树是向上生长的，而在数据结构中的树是生活中的树抽象过来——根朝上，叶子朝下，如下图

图2：

结论： 1.子树是不相交
            2.除了根节点外，每个节点有且仅有一个父节点
            3.一棵N个节点的树有N-1条边（如图1中一共有12个节点，有11条边）

2.树相关术语

1 .叶结点或终端结： 度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点

2 .非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等结点为分支结点

3 .双亲结点或父结点： 若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

4 .孩子结点或子结点： 一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

5 .兄弟结点： 具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点

6 .结点的度： 一个结点含有的子树的个数称为该结点的度； 如上图：A的为6（B C D E F G）

7 .树的度： 一棵树中，最大的结点的度称为树的度； 如上图：树的度为6

8 . 结点的层次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推；

9 .树的高度或深度： 树中结点的最大层次； 如上图：树的高度为4

10 .堂兄弟结点： 双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

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

11 .结点的祖先： 从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

12 .子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

13 .森林： 由m（m>0）棵互不相交的树的集合称为森林；

3.树的表示

      树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

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

4.树形结构实际运用场景

      文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关联

二、二叉树

1. 概念与结构

      在树形结构中，我们最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该节点是由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者为空

   从上图可以看出二叉树具备以下特点：

     1 .二叉树不存在度大于2的节点（孩子不超过2个，可以是0个孩子，一个孩子，两个孩子）

     2 . 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

现实中的二叉树

特殊的二叉树

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

   2 . 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。（最后一层节点的个数不一定达到最大）

   证明：第一层节点有2 ^0 个节点，第二层是 2 ^1个节点，第三层是2 ^2个，以此内推，第n层是 2 ^(n-1)个节点，这符合高中等比数列求和公式，相加得到最终总结点事2 ^n-1个。

二叉树的性质

根据二叉树的特点可知;

1)若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点

2)若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1

3)若规定根节点的层数为1，具有n个节点的满二叉树的深度h=log2(n+1)(log以2为底，n+1为对数)

4）对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1

5）对于具有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否则无右孩子

这里对性质4进行证明：

• 假设二叉树有N个结点

• 从总结点数角度考虑：N = n0 + n1 + n2 ①

• 从边的角度考虑，N个结点的任意二叉树，总共有N-1条边

• 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边

• 因此N个结点的二叉树总共有N-1条边

• 因为度为0的结点没有孩子，故度为0的结点不产生边; 度为1的结点只有一个孩子，故每个度为1的结
  点* 产生一条边; 度为2的结点有2个孩子，故每个度为2的结点产生两条边，所以总边数为：
  n1+2*n2

• 故从边的角度考虑：N-1 = n1 + 2*n2 ②

• 结合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1

• 即：n0 = n2 + 1

二叉树存储结构

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

1. 顺序结构： 就是使用数组存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费，而在现实中使用中只有堆才会使用数组存储，需要注意的是这个里的堆和操作系统虚拟进程空间中的堆事两码事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

   二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树

   这里大家可能疑惑，为啥在非完全二叉树中必须空出位置来代表该节点为空，因为二叉树是有序的，否则会导致父亲变孩子，左孩子变右孩子

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

二叉链有两个指针指向左右孩子，不可以向上找父亲节点，但是三叉链多了个指针指向父亲节点。

三、手动模拟实现顺序二叉树——堆

   堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他特性，下面是其的概念和结构解释

定义：如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆（在左右子树中根节点也是对应的最小 / 最大）

小根堆：堆顶是堆中最小的节点 ，大根堆：堆顶是堆中最大的节点

注意：这里大家可能疑惑堆和二叉树具体是什么关系，可以认为堆除了具有二叉树的性质还具有堆顶是最大节点/最小节点的特性

1.堆的结构

这里堆的定义和顺序表的定义是类似的

typedef int HPDataType;//堆的结构
typedef struct Heap
{HPDataType* arr; int size;         //有效数据个数 int capacity;     //容量
}HP; 

2.初始化

和顺序表类似

void HPInit(HP* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}

3.销毁

void HPDestroy(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->capacity = php->size = 0;}

4.向上调整算法

是为了下一个插入数据方法做出铺垫，将插入的数据默认为孩子节点，根据二叉树的性质可知parent=(child-1)/2，如果我们要实现的是小堆，那么

1. 比较child和parent谁小，谁小谁往上放（交换）
2. 然后继续让child往上走（child=parent即可），结束条件是child>0,因为child走到根节点后没有其父节点

//交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上调整算法   前提;往有效的堆中调整
void AdjustUp(HPDataType *arr,int child)
{int parent = (child - 1) / 2;while (child>0){//  >:大堆//  <:小堆if (arr[child] <arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

5.插入数据

1. 初始情况下需要动态增容（这里和顺序表类似）
2. 插入数据：php->arr[php->size] = x
3. 判断插入的数据是否符合大堆/小堆，不符合则调用向上调整算法（这里是使用大堆）
4. 最后让size++

如下图：先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆

//插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;//空间满了，需要增容HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}

6.判空

这里和顺序表一样

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

7.求size

返回堆中有效的数据个数

int HPSize(HP* php)
{assert(php);return php->size;
}

8.向下调整算法

我们已知父亲节点来找孩子节点，假设我们要实现的是小堆，那么就需要让父亲节点和孩子节点比较，这里需要注意，我们需要让左右节点均要和父亲节点比，谁小谁和parent交换，然后让parent走到child位置，循环进行该操作直至child走到n结束

void AdjustDown(HPDataType* arr, int parent,int n)
{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;}}}

9.删除堆顶数据

1.首先保证堆不为空，调用堆判空接口

2.删除堆顶元素

如果直接删除堆顶元素，让孩子节点均往前移动会导致原来的孩子节点变成父亲节点，左右孩子顺序不对等情况，如下图中原本25是15的左孩子，现在变成56的兄弟节点，那么我们就需要重新一个个调整，代价太大了，那么有没有方法可以解决？

我们交换堆顶元素和最后一个数据，然后让size- -，走到a[5]位置，a[5]可以存储数据，但是不是有效的（即10不是堆中有序的数据），我们发现70变成了堆顶，但是15 56 25 等数据之间的关系并没有发生变化，因此我们只需要让堆顶70向下调整，直接调用向下调整方法即可

具体步骤如下：

1.将堆顶元素与堆中最后一个元素进行交换

2.删除堆中最后一个元素

3.将堆顶元素向下调整到满足堆特性为止

10.获取堆顶数据

判空后直接返回a[0]位置的数据即可

HPDataType HPTOP(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

注意：上述所说的向上调整算法和向下调整算法均有个前提是往有效的堆中调整

四、最全源码

1.堆中接口源码

五、堆排序

1.思考

这里我们需要思考：排升序和排降序时需要建大堆还是小堆。这里第一反应是通过循环取堆顶元素发现排升序是建立小堆，降序建立大堆。那么是对还是错？？？

具体操作：
1 .创建数组
2. 我们调用堆中的push接口将数组中的数据建堆
3 .通过频繁取堆顶元素放入到数组中（条件为堆不为空），并且要不断删除堆顶

注意：大家这里可能疑惑为什么不直接打印堆顶元素，而是将堆顶元素取出来放入数组中，首先我们明确需要的条件是将数组排序，打印堆顶元素并没有直接改变数组中原本的数据

//排升序----建大堆，因为调用AdjustDown函数，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序
//排降序----建小堆，因为调用AdjustDown函数，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序
//借助数据结果---堆
void test01()
{int arr[] = { 17,20,10,13,19,15 };int n = sizeof(arr) / sizeof(arr[0]);HP hp;HPInit(&hp);//调用push将数组中的数据建堆for (int i = 0; i < n; i++){HPPush(&hp, arr[i]);}int i = 0;while (!HPEmpty(&hp)){arr[i++]=HPTOP(&hp);HPPop(&hp);}for (int j = 0; j< n; j++){printf("%d ", arr[j]);}HPDestroy(&hp);}

我们这里来看下我们之前学习过的冒泡排序的代码是如何的，经过比较发现冒泡排序是通过思想来实现排序，而上述的堆排序是通过使用数据结构——堆来辅助实现的，因此要实现堆排序需要借助堆的排序思想

2.冒泡排序：

//冒泡排序，时间复杂度O（n^2）
void BubbleSort(int* arr, int n)
{for (int i= 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange = 0){break;}}}

3.建堆——算法复杂度的优与劣

       这里我们根据数组中存储的最后一个数据的有效下标（孩子节点）根据parent=（child-1)/2可得，依次递减parent直至根节点，结束循环

       大家可能疑惑在向下调整算法中可不可以从a[0]位置开始调整？答案是不可以，因为向上调整算法和向下调整算法成立的前提是该堆已经是有效的堆，从a[0]开始调整就相当于从有效的大/小堆中来调整大/小堆，所以不行，我们应该依次调整左右子树的大/小堆最后整体形成大/小堆

       注意：大家可能会把堆排序中的向上寻找parent节点认为是向上调整算法，但是如何确定是向上/向下调整算法的实质是调整方向，父亲节点——>子节点是向下调整，是通过比较两个孩子之间谁和父亲节点大/小来实现，可以保证堆的已有顺序不会被修改
代码如下：

void HeapSort(int*arr,int n)
{//根据给定的arr来进行建堆//child:n-1   parent;(n-1-1)/2for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(arr,i,n);}
}

时间复杂度： 我们发现如果要建的堆事满二叉树则一共有2^h-1个节点，最坏情况下就是从根节点到最后一个节点一次次往下移动（一层层移动），则h=log2(n+1),向下调整为logn，那么总时间复杂度为nlongn

那么可以使用向下调整算法建堆也是可以使用向上调整算法的，那么哪个时间复杂度更优捏？初次思考我们发现两个算法均是nlongn，那么是不是如此呢？

向下调整算法证明：
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

需要移动节点总的移动步数为：每层节点个数x向上调整次数


从第一层到最后一层节点个数逐渐增多，向下调整次数逐渐减少

向上调整算法时间复杂度证明：

这里和向下调整算法证明类似，最后可以得出F(n)=(n+1)(log2(n+1)-2)+2，则时间复杂度为O(n*logn)

结论：因此向下调整算法是堆排序中主流用法！

4.排序

假设我们需要排降序，

1.我们通过交换根节点a[0]和最后一个节点的数据

2.让end–

3.使用向下调整算法不断将小的数据放到根节点处

结论：根据上述步骤我们得到:

排升序----建大堆，因为不断交换堆顶数据和最后一个位置数据交换，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序

排降序----建小堆，因为不断交换堆顶数据和最后一个位置数据交换，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序

六、TOP-K问题

TOP-K问题:即求数据结合中前k个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名，世界500强，富豪榜，游戏中前100的活跃玩家等。
对于TOP-K问题，能想到的最简单直接的方法就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中），最佳的方法就是使用堆来解决，基本思路如下：

1.用数据集合中前k个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

2.用剩余的N-k个元素依次与堆顶元素进行比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比较完之后，堆中剩余的k个元素就是所求的前k个最小或者最大的元素

例子：假设·我们有N个数据， N是10亿个整数，需要申请多大的内存？

换算：
int = 4 byte
1G=1024MB=10241024KB=10241024*1024 byte

根据上述换算可得：1G约等于10亿个字节，因此存储10亿数据需要申请4G内存。

如果面试官问我们，如果我们只有1G内存——我们该如何解决？
这里我们可以分多次来存储，建立4个堆，每份都求取该堆中最大的几个数据，最后四个堆中数据个数相加为k即可

那么假设只有1KB内存该如何呢？
先取前k个数据进行建堆，遍历剩下的 N-K个数据跟堆顶数据进行比较

找最大的前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);
}

生成了data.txt文件，里面存放了十万个整型数据，如下

遍历剩余的N-K个数据，和堆顶比大小，符合条件则调用向下调整算法

void TopK()
{int k = 0;printf("请输入K：");scanf("%d", &k);//读取文件中前k个数据建堆const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K个数，建小堆int* minHeap = (int*)malloc(sizeof(int) * k);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);}//遍历剩下的n-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);
}

打印结果：

结论：找最大的前K个数据，建小堆，找最小的前K个数据，建大堆

总结

本文以“长幼有序”为核心思想，系统解析了树形结构及其衍生数据结构的层次化特性与应用：

1.树结构：作为非线性数据结构的基石，通过根节点与子树的层次关系，构建了自然的层级模型，体现了数据间的“长幼”逻辑。

2.二叉树：以简洁的左右子树划分，强化了顺序的重要性，满二叉树与完全二叉树的特性为高效算法（如堆）奠定了基础。

3.堆结构：作为二叉树的特殊形态，通过向上/向下调整算法，将层次化结构转化为排序利器，小根堆与大根堆的区分直接服务于TOP-K等实际问题。

4.TOP-K问题：利用堆的层次调整能力，在大数据场景下高效求解极值问题，体现了“长幼有序”思想在资源优化中的关键作用

全文贯穿“层次决定顺序，结构决定效率”的理念，展示了数据结构从理论到实践的完整链路