【数据结构】二叉树初阶详解（一）：树与二叉树基础 + 堆结构全解析

📝前言

在计算机科学的知识体系里，数据结构是构建高效程序与系统的基石，而树结构，更是其中极具代表性与实用价值的存在。它以独特的分层组织形式，能高效解决诸如数据检索、分层管理等各类问题，像文件系统的目录架构、数据库的索引设计，都有树结构的身影 。
掌握树结构，尤其是二叉树的概念、不同存储结构（顺序与链式 ）及实现，不仅能帮我们理解复杂数据关系的组织逻辑，更能在算法设计、系统优化等实践中，找到高效解题的钥匙。接下来，就让我们深入探索树结构的奥秘，从基础概念到具体实现，一步步搭建起对树结构的清晰认知，为编程能力与问题解决思维的提升，筑牢根基。

🌠树的概念和结构

🌉树的概念

树是一种非线性的数据结构，有n（n>=0）个有限结点组成的一个有层的集合，他的形状类似将现实中的树倒过的模样，也就是树根朝上，树叶朝下。
性质：
1.树有一个特殊结点，叫根结点，是开端，也就是说根结点前面没有别的结点了（无前驱结点）。
2.根结点下的接下来的结点又是一颗类似于树的子树，它们有且只有一个前驱结点，但可以有0或者多个后继结点（它不能横向发展，可以向下发展，要是向上发展有且只有一个结点），因此树也算是一种递归。
3.树形结构中，子树之间不能有交集，否则就不是树形结构。
4.一颗N个结点的树有N-1条边。

（这里的树其实可以理解为我们家族的人际关系，这样就好看待树相关的性质了。图片上的都是非树）

🌉树的相关概念

结点的度：一个结点含有的子树的个数称为该结点的度； 如上图：A的为6

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

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

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

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

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

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

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

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

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

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

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

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

（这里的名称其实可以理解为我们家族的人际关系，这样就好看待树一些的名称了）用前面的思想理解后 ，我们还要在这里了解：度，层次，高度或深度。

度：其实就是一个结点下连着几个结点（而这连着的结点下还连着的结点不算）

层次：可以理解为辈分的层次。从最先开始的最高辈（根结点）叫做第一层。

高度或深度：你可以从根结点连接到终端结点，每次连一个，看这条线上有几个结点，就有多大的高度或深度。

🌉树的表示

树的表示有很多种：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这些方法都是为了要满足树既要保存值域，又要保存结点和结点则之间的关系。
孩子兄弟表示法（代码）：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点（靠左边的孩子结点）
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的值域
};

树的实际应用是在我们的文件系统的目录结构里面使用。

🌠二叉树概念及结构

🌉二叉树的概念

二叉树是树的一种特殊情况，就像，在我国的二胎政策下每一家只能生两个小孩，我们的每一个父结点下最多自能有两个孩子结点，且最好是将先来为左结点，后至为右结点。因此二叉树也是一个有序树。

🌉特殊的二叉树

1. 满二叉树：若二叉树每一层的结点数都达到该层能容纳的最大值，则为满二叉树。
   设层数为 K，满二叉树的结点总数满足公式 (2^K - 1)（推导：第 1 层 1 个，第 2 层 2 个…… 第 K 层 (2^{K-1}) 个，总数为等比数列求和 (2^K - 1) ）。当二叉树结点总数符合此公式时，即为满二叉树。
2. 完全二叉树：完全二叉树是基于满二叉树衍生的高效结构，核心规则为：对深度为 K、含 n 个结点的二叉树，若其所有结点能与 “深度 K 的满二叉树” 中编号 1 到 n 的结点一一对应（可理解为按层序 “填充满” 满二叉树的前 n 个位置 ），则称为完全二叉树。
   
   完全二叉树得 “从左到右挤着排，不能跳位。

🌉二叉树的性质

一、层与结点数量关系（根层数为 1 ）
1.第 i 层最多结点数：
非空二叉树第 i 层，最多有 2^(i - 1)个结点（每一层结点数呈 2 的幂次增长 ）。
2.深度 h 的最大结点数（满二叉树场景 ）：
深度为 h 的二叉树，结点总数最多是 2^h - 1（满二叉树时达到此最大值，每层结点数都 “拉满” ）。

二、叶结点与分支结点的数量关系
对任意二叉树，记：
No：度为 0 的叶结点个数（无分支的 “末端” 结点 ）
N2：度为 2 的分支结点个数（有两个子结点的结点 ）
则恒有 No = N2 + 1（叶结点比度 2 结点多 1 ，可通过 “边数 = 结点数 - 1” 推导 ）。

三、满二叉树的深度计算（根层数为 1 ）
若满二叉树有 n 个结点，其深度 h 满足：h = log_2(n + 1)（因满二叉树结点数 n = 2^h - 1，变形可得深度公式）。

四、完全二叉树的编号与亲属结点关系（编号从 0 开始 ）
对有 n 个结点的完全二叉树，按层序（从上到下、从左到右 ） 编号（根为 0 ），
序号为 i 的结点：
1.双亲结点：若 i>0，双亲序号为 (i-1)/2（整数除法，向下取整 ）；i = 0 是根，无双亲。
2.左孩子：若 2i + 1 < n，左孩子序号为 2i + 1；否则无左孩子。
3.右孩子：若 2i + 2 < n，右孩子序号为 2i + 2；否则无右孩子。

🌠二叉树顺序结构及实现

🌉二叉树的顺序结构

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

按照图上的情况，非完全二叉树会有空间浪费和操作复杂度高以及结构表达不直观的劣势。所以顺序结构还是用完全二叉树的好。

🌉堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

一 堆的定义
给定关键码集合 K = {k0, k1, k2, …, k（n-1）}，按完全二叉树的顺序存储方式（即层序存储到一维数组 ）存放，且满足以下关系之一：
小根堆（小堆）：对任意下标 i，有 Ki <= K(2i+1) 且 Ki <= K(2i+2)（父结点值 ≤ 左右子结点值 ）。
大根堆（大堆）：对任意下标 i，有 Ki <= K(2i+1) 且 Ki >= K(2i+2)（父结点值 ≥ 左右子结点值 ）。

若根结点是堆中最小元素 → 小根堆；若根结点是堆中最大元素 → 大根堆。

二、堆的性质
1.结点值的层级关系：堆中任意结点的值，总是不大于（小根堆）或不小于（大根堆）其父结点的值，保证根结点是堆的 “极值”（最小 / 最大 ）。
2.结构特征：堆一定是完全二叉树（存储方式和规则决定，结点按层序填充，无 “跳位” ）。

第一个是小根堆，第二个是大根堆。

🌉堆的实现

堆的声明：

typedef int HPDataType;
typedef struct Heap
{
 HPDataType* _a;
 int _size;
 int _capacity; 
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

接下来我们要逐步学习堆的知识。

🍁堆向下调整算法

先定义一个数组，这个数组从逻辑上看是一颗完全二叉树。我们从根结点开始向下调整算法，将其调整一个小堆。但有一个条件：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

以27为根的左右子树，都满足小堆的性质，只有根节点不满足，因此只需将根节点往下调整到合适的位置即可形成堆。

🍁堆的创建

构建堆时，从最后一个非叶子节点的子树开始，向上调整到根，把完全二叉树数组改成堆 。

定义一个数组：

int a[] = {1,5,3,8,7,6};

第3步：此时调换 1 和 8 的位置的时候，8 的其左子树构成的归结结构被破坏。如第3步8下面的左子树。因此，每一次调换元素的时候，有可能破坏其子堆的结构。

因此，每一次发生元素交换的时候，都需要递归调用重新构造堆的结构。此时就要重新对这一部分进行重新构造堆。

🍁建堆的时间复杂度

前提：因堆是完全二叉树，为便于分析，用满二叉树（属完全二叉树）推导，少量节点不影响最终近似结果。

分层分析：设树高为 h，按层统计节点数与移动步数：第 i 层（从 0 开始）有 2^i 个节点，需向下移动 h - i - 1 层（如第 1 层节点移动 h - 2 步 ）。

第 1 层，2^0个节点，需要向下移动h - 1层
第 2 层，2^1个节点，需要向下移动h - 2层
第3 层 ，2^2个节点，需要向下移动h - 3层
第 4 层，2^3个节点，需要向下移动h - 4层
……
第h - 1层，2^{h - 2}个节点，需要向下移动 1 层

公式构建：总移动步数 T(n)按层累加，得到含等比数列的表达式 ①；通过构造 2*T(n) 并与 ① 错位相减，化简后结合满二叉树节点数 n = 2^h - 1（即 h = log_2(n + 1)，最终推导出 T(n)约等于n 。

结论：建堆时间复杂度为 O(N) ，体现建堆操作随数据规模增长，时间成本线性递增的特性。

🍁堆的插入

1.先将元素插入到堆的末尾，即最后一个叶子之后
2.插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可
3.简而言之：就是进行向上调整算法，直到满足堆

🍁堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根与最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

🌉堆的应用

🍁堆排序

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

2. 利用堆删除思想来进行排序

3. 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

建堆是针对无序二叉树（通常基于数组模拟完全二叉树结构 ）的调整过程，目的是构建大顶堆或小顶堆：
从最后一个非叶子节点开始，
1.若构建大顶堆，比较父节点与子节点值，若父节点小于子节点，选子节点中值最大的与父节点交换；
2.若构建小顶堆，则选子节点中值最小的交换。按此规则，逐层向上对每个子树递归 / 循环调整，使整棵树满足堆的有序性（大顶堆父节点≥子节点，小顶堆父节点≤子节点 ）。

堆删除排序（堆排序核心步骤 ）

基于堆 “根节点为最值（大顶堆最大、小顶堆最小 ）” 的性质：
1.若根节点不满足最值，先通过向下调整让根节点成为最值 。

2.将根节点（最值 ）与堆最后一个数据交换，把最值 “固定” 到堆末尾 。

3.对剩余未固定的堆结构（除末尾已交换元素 ），再次执行向下调整，恢复堆性质。重复此过程，最终完成排序，使数据按升序（大顶堆场景 ）或降序（小顶堆场景 ）排列 。

🍁TOP-K问题

TOP - K 问题是从大规模数据里找前 K 个最大或最小元素，因数据量大排序法受限，用堆解决更优，步骤为：
1.建堆：找最大元素建小堆，找最小元素建大堆，用前 K 个元素初始化堆。

2.筛选：剩余 N - K 个元素逐个与堆顶比，不满足条件（如找最大时堆顶小则替换 ）就替换堆顶，调整堆结构。

3.结果：处理完后，堆里 K 个元素就是前 K 个最大或最小元素，利用堆的特性高效筛选，适配大数据场景 。

举个🌰（找前 3 大的元素）：

数据是 [5, 3, 8, 1, 9, 2, 7]，K=3。
目标：找最大的 3 个（8、9、7）。

1. 第一步：先拿前 3 个 [5, 3, 8] 建 小顶堆，堆顶是 3（小顶堆特性：堆顶最小）。

2. 第二步：“筛选 → 用筛子过滤数据”
   剩下的数据（除了前 K 个），逐个和 堆顶 比较：
   如果比堆顶 “更优”（找最大时，比堆顶大；找最小时，比堆顶小）→ 替换堆顶，再调整堆结构（保持堆的规则）；如果不如堆顶 → 直接淘汰，不管它。

接着上面的🌰：
剩余数据是 [1, 9, 2, 7]，堆顶是 3（小顶堆）。
拿 1 和堆顶 3 比：1 < 3 → 淘汰；

拿 9 和堆顶 3 比：9 > 3 → 替换堆顶，堆变成 [5, 8, 9]（调整后小顶堆堆顶回到最小，比如变成 5 ）；

拿 2 和堆顶 5 比：2 < 5 → 淘汰；

拿 7 和堆顶 5 比：7 > 5 → 替换堆顶，堆变成 [7, 8, 9]（调整后堆顶是 7 ）。

3. 第三步：“结果 → 筛子里剩下的就是答案”
   过滤完所有数据后，堆里剩下的 K 个元素，就是 “前 K 大 / 前 K 小” 的结果！
   上面的🌰最后堆里是 [7, 8, 9] → 刚好是最大的 3 个元素

// 向下调整函数，构建小堆
#include<stdio.h>
void AdjustDown(int* a, int n, int parent) {
    int child = 2 * parent + 1;
    while (child < n) {
        // 找较小的子节点
        if (child + 1 < n && a[child + 1] < a[child]) {
            child++;
        }
        // 子节点小于父节点，交换并继续调整
        if (a[child] < a[parent]) {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}
void PrintTopK(int* a, int n, int k)
{
 // 1. 建堆--用a中前k个元素建堆
  for (int i = (k / 2) - 1; i >= 0; i--) {
        AdjustDown(a, k, i);
    }
 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
  for (int i = k; i < n; i++) {
        if (a[i] > a[0]) {
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            AdjustDown(a, k, 0);
        }
    }
    // 这里可按需输出堆中前 K 个元素，示例简单打印堆内数据
    for (int i = 0; i < k; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}
void TestTopk()
{
 int n = 10000;
 int* a = (int*)malloc(sizeof(int)*n);
 srand(time(0));
 for (size_t i = 0; i < n; ++i)
 {
 a[i] = rand() % 1000000;
 }
 a[5] = 1000000 + 1;
 a[1231] = 1000000 + 2;
 a[531] = 1000000 + 3;
 a[5121] = 1000000 + 4;
 a[115] = 1000000 + 5;
 a[2335] = 1000000 + 6;
 a[9999] = 1000000 + 7;
 a[76] = 1000000 + 8;
 a[423] = 1000000 + 9;
 a[3144] = 1000000 + 10;
 PrintTopK(int* a, n, 10);
}

🚩总结

感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以点一个小小的赞😘