欢迎阅读本篇学习笔记。
本篇作为个人计算机专业的学习记录，这里将系统梳理二叉树的相关知识点，从基础概念到代码实现逐步展开，便于后续的复习巩固。如有不足，欢迎大家在评论区交流指正，感谢大家的阅读与支持！
1.树概念及结构
1.1树的概念
在学习二叉树之前我们先来了解一下树的概念。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根结点没有前驱结点
- 除根结点外，其余结点被分成 M (M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti (1<= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继
- 因此，树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
1.2树的相关概念
- 结点的度：一个结点含有的子树的个数称为该结点的度。度是衡量一个结点“分支能力”的重要指标，它直接反映了该结点向下延伸的规模。如上图：A 的度为 6，说明 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）棵互不相交的树的集合称为森林。森林可以看作是多棵树的集合，在实际应用中，森林与树的转换是常见的操作。
1.3树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType; struct Node { struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域 };好啦，看完上面的文字相信大家已经对树有了一定了解。树作为一种基础的非线性数据结构，其核心在于通过结点之间的层次关系来组织数据，这与我们熟悉的线性表有着本质区别。理解树的概念和相关术语，是后续学习二叉树、堆、并查集等更复杂结构的重要前提。接下来，我们将进入二叉树的学习。
2.二叉树的概念及结构
2.1二叉树的概念
二叉树是由结点构成的有限集合，它有且仅有两种情况：
- 集合中没有任何结点，称为空二叉树；
- 集合由一个根结点，加上两棵互不相交、分别称作左子树和右子树的二叉树共同组成。
从上图可以看出：
- 二叉树不存在度大于 2 的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的： 空树、只有根节点、只有左子树、只有右子树、左右子树均存在
2.2特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是 2的k次方-1，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。通俗一点来讲就是：除了最底下一层，上面所有层的结点都全部填满（前 k-1 层是标准的满二叉树）最底层的结点全部靠左连续排列，中间没有空缺。
2.3二叉树的性质
/* * 假设二叉树有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.B 2.A 3.A 4.B 5.B
2. 二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1. 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们下一部分会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
（对应下面配图：左侧为完全二叉树的数组存储，右侧为一般二叉树的数组存储对比）
2. 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面随着我们学习的深入会学到红黑树等等会用到三叉链。
3. 堆的概念及结构
在上一部分我们了解了二叉树的两种存储结构，其中顺序存储（数组）最适合表示完全二叉树，而现实中最典型的应用就是「堆」。这一部分内容我们将会讲解堆的概念、实现与应用。我们先来了解一下堆和二叉树的区别。
3.1 堆的定义与性质
若存在一个关键码的集合 K = {k0, k1, k2, ..., k (n-1)}，将其所有元素按照完全二叉树的顺序存储方式存放于一维数组中，并且满足下述关系，则称该集合为堆：
- 若满足 Ki ≤ K (2i+1) 且 Ki ≤ K (2i+2)，则称为小根堆（小顶堆），此时根结点为全局最小值；
- 若满足 Ki ≥ K (2i+1) 且 Ki ≥ K (2i+2)，则称为大根堆（大顶堆），此时根结点为全局最大值。
堆的核心性质
- 堆中任意结点的值，总是不大于（小根堆）或不小于（大根堆）其父结点的值；
- 堆在逻辑上一定是一棵完全二叉树，物理上用一维数组存储。
小根堆与大根堆示例
小根堆：父结点 ≤ 左右孩子
- 逻辑结构：根为 10，子结点 15、56，底层结点 25、30、70
- 对应存储数组：
{10, 15, 56, 25, 30, 70}
大根堆：父结点 ≥ 左右孩子
- 逻辑结构：根为 70，子结点 56、30，底层结点 25、15、10
- 对应存储数组：
{70, 56, 30, 25, 15, 10}
✏️ 概念巩固选择题
参考答案：1.A 2.C 3.C 4.C
3. 堆的实现
3.1 堆向下调整算法
向下调整是堆所有操作的核心算法，它有一个严格的前提条件：
待调整结点的左、右子树必须已经是堆，才能对该结点执行向下调整。
算法思路（以小根堆为例）
- 从目标结点开始，比较当前结点与其左、右孩子的值；
- 找到左右孩子中值更小的结点，与当前结点比较；
- 如果孩子结点更小，则交换当前结点与孩子结点；
- 继续向下重复上述过程，直到当前结点满足堆性质，或到达叶子结点。
示例：数组{27,15,19,18,28,34,65,49,25,37}其左右子树本身已经是小根堆，仅根结点 27 不满足堆性质，只需将 27 逐层向下交换到合适位置，即可形成完整的小根堆。
3.2 堆的创建（建堆）
对于一个任意数组，它逻辑上对应一棵完全二叉树，但不一定满足堆的性质。我们可以通过从下往上、对每个非叶子结点依次执行向下调整，将整棵树构建成一个堆。
建堆步骤
- 找到倒数第一个非叶子结点（即数组最后一个结点的父结点）；
- 从该结点开始，倒序向前遍历所有非叶子结点；
- 对每一个非叶子结点执行向下调整算法；
- 一直调整到根结点，整棵树就成为一个合法的堆。
注意：每次元素交换后，被影响的子树结构可能被破坏，因此需要对交换后的子树重新向下调整，保证子树仍然满足堆性质。
示例：数组{1,5,3,8,7,6}构建大根堆，最终得到大根堆序列：8 7 6 1 5 3
3.3 建堆的时间复杂度
因此：建堆的时间复杂度为 O（N）
3.4 堆的插入
这里展示的是小堆的插入（大堆也是类似的）
堆的插入操作分为两步：
- 将新元素插入到数组的尾部，也就是完全二叉树的最后一个叶子位置；
- 对新插入的结点执行向上调整算法：从该结点开始，不断与父结点比较，若不满足堆性质则交换，直到满足堆性质或到达根结点。
3.5 堆的删除
堆的删除默认删除堆顶元素（即当前堆的最值），操作步骤：
- 将堆顶元素与数组最后一个元素交换；
- 删除数组的最后一个元素（原堆顶元素）；
- 对新的堆顶元素执行向下调整算法，恢复整个堆的性质。
这种删除方式可以保证删除后结构仍然是合法的堆，单次删除的时间复杂度为 O（logN）。
3.6 堆的代码实现（C 语言）
堆的结构体定义
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);4. 堆的应用：堆排序
堆排序（Heap Sort）就是利用堆的思想对数组进行排序，总共分为两大核心步骤：
4.1 步骤一：建堆
- 排升序：建立大根堆
- 排降序：建立小根堆
4.2 步骤二：利用堆删除思想排序
建堆完成后，堆顶元素就是整个数组的最值。我们不断执行「堆顶与末尾元素交换 → 缩小堆的范围 → 堆顶向下调整」的循环，每次都能将当前堆的最值放到数组的末尾位置，最终整个数组变为有序序列。
由于建堆和堆删除的核心都是向下调整算法，因此只要掌握了向下调整，就可以完整实现堆排序。
4.3 TOP-K 问题
4.3.1 问题场景
TOP-K 问题的核心需求是：在海量数据中，找出前 K 个最大的元素或者前 K 个最小的元素。常见的应用场景比如专业成绩前 10 名、世界 500 强企业、游戏全服活跃榜前 100 名等。
这类问题的典型特点是数据量极大，如果直接对全部数据做全排序，不仅时间成本很高，甚至可能无法将全部数据一次性加载到内存中。而堆结构正是解决海量数据 TOP-K 问题的最优方案。
4.3.2 解题思路
- 用前 K 个元素建初始堆
- 求前 K 个最大的元素 → 建小根堆（堆顶是当前 K 个元素里的最小值，遇到更大的元素就替换堆顶）
- 求前 K 个最小的元素 → 建大根堆（堆顶是当前 K 个元素里的最大值，遇到更小的元素就替换堆顶）
- 遍历剩余的 N-K 个元素，依次与堆顶元素比较：
- 如果当前元素比堆顶更符合要求（求最大时比堆顶大，求最小时比堆顶小），则用该元素替换堆顶
- 替换后对堆顶执行向下调整算法，恢复堆的性质
- 全部元素遍历完成后，堆中剩余的 K 个元素就是所求的前 K 个最值元素
4.3.3 代码框架
void PrintTopK(int* a, int n, int k) { // 1. 用数组前k个元素建堆 // 2. 剩余n-k个元素依次与堆顶比较，不满足则替换并向下调整 }4.3.4 测试示例
下面的代码模拟了在 10000 个随机数中，找出数值最大的前 10 个元素：
#include <stdio.h> #include <stdlib.h> #include <time.h> // 小顶堆向下调整 void sift_down(int* heap, int size, int index) { while (1) { int left = 2 * index + 1; int right = 2 * index + 2; int min_idx = index; if (left < size && heap[left] < heap[min_idx]) { min_idx = left; } if (right < size && heap[right] < heap[min_idx]) { min_idx = right; } if (min_idx == index) break; int temp = heap[index]; heap[index] = heap[min_idx]; heap[min_idx] = temp; index = min_idx; } } // 小顶堆实现 Top-K：输出数组中最大的前k个元素 void PrintTopK(int* a, int n, int k) { int* heap = (int*)malloc(sizeof(int) * k); int heap_size = 0; for (int i = 0; i < n; i++) { if (heap_size < k) { // 堆未满，插入尾部并向上调整 heap[heap_size++] = a[i]; int idx = heap_size - 1; while (idx > 0) { int parent = (idx - 1) / 2; if (heap[idx] < heap[parent]) { int temp = heap[idx]; heap[idx] = heap[parent]; heap[parent] = temp; idx = parent; } else break; } } else if (a[i] > heap[0]) { // 堆已满，比堆顶大则替换并向下调整 heap[0] = a[i]; sift_down(heap, heap_size, 0); } } printf("最大的前%d个元素：", k); for (int i = 0; i < heap_size; i++) { printf("%d ", heap[i]); } printf("\n"); free(heap); } void TestTopK() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand((unsigned int)time(NULL)); // 生成10000个0~99999的随机整数 for (int i = 0; i < n; ++i) { a[i] = rand() % 100000; } // 手动植入10个更大的数，用于验证算法结果 a[5] = 100000 + 1; a[1231] = 100000 + 2; a[531] = 100000 + 3; a[5121] = 100000 + 4; a[115] = 100000 + 5; a[2335] = 100000 + 6; a[9999] = 100000 + 7; a[76] = 100000 + 8; a[423] = 100000 + 9; a[3144] = 100000 + 10; PrintTopK(a, n, 10); free(a); }该算法核心仅维护大小为 K 的小顶堆，空间复杂度为 O (K)；实际海量数据场景下可流式逐个读取数据，无需将全部数据加载到内存，非常适合处理大规模数据下的 TOP-K 筛选场景。
5. 二叉树链式结构的实现
前置说明
在学习二叉树的增删改查、遍历等基本操作之前，我们首先需要构造出一棵二叉树作为测试基础。 考虑到初学者对二叉树结构还不够熟悉，为了降低学习门槛，我们先通过手动快速创建的方式得到一棵结构简单的二叉树，先把重心放在遍历等核心操作的学习上。等对二叉树的操作逻辑完全熟悉之后，再深入讲解二叉树通用的、正式的创建方式。
链式二叉树结点定义
链式存储的二叉树采用二叉链表结构，每个结点由三部分组成：数据域、左孩子指针、右孩子指针：
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; // 数据域，存储结点的值 struct BinaryTreeNode* _left; // 左指针，指向左孩子结点 struct BinaryTreeNode* _right; // 右指针，指向右孩子结点 }BTNode;手动构建测试二叉树
下面的代码通过逐个申请结点、手动连接指针的方式，构建一棵固定结构的二叉树，用于后续操作的测试：
BTNode* CreatBinaryTree() { // 申请6个结点 BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); // 按照树形结构连接各结点的左右指针 node1->_left = node2; node1->_right = node4; node2->_left = node3; node4->_left = node5; node4->_right = node6; return node1; // 返回整棵树的根结点指针 }注意：上述代码只是快速构造测试树的权宜写法，并不是二叉树通用的创建方式。
二叉树的递归定义
二叉树的定义本身具有递归性，这也是二叉树绝大多数操作都采用递归实现的根本原因：
- 空树：不包含任何结点的二叉树
- 非空树：由根结点、根结点的左子树、根结点的右子树三部分组成
换句话说，二叉树的任意一棵子树，本身也都是一棵完整的二叉树。这个概念是理解二叉树递归遍历、递归操作的核心基础。
5.2 二叉树的遍历
5.2.1前序、中序以及后序遍历
遍历是二叉树最基础也最重要的操作。所谓二叉树遍历 (Traversal)，是指按照某种特定的规则，依次访问二叉树中的每一个结点，且每个结点仅被访问一次。遍历是二叉树上所有其它运算的基础。
根据访问根结点的时机不同，二叉树有三种经典的深度优先遍历方式：
- 前序遍历（先根遍历，Preorder Traversal）访问根结点的操作，发生在遍历其左右子树之前。 访问顺序：根结点 → 左子树 → 右子树，简称NLR
- 中序遍历（中根遍历，Inorder Traversal）访问根结点的操作，发生在遍历其左右子树中间。 访问顺序：左子树 → 根结点 → 右子树，简称LNR
- 后序遍历（后根遍历，Postorder Traversal）访问根结点的操作，发生在遍历其左右子树之后。 访问顺序：左子树 → 右子树 → 根结点，简称LRN
其中 N 代表根结点 (Node)，L 代表左子树 (Left subtree)，R 代表右子树 (Right subtree)。由于被访问的结点一定是某棵子树的根，因此 NLR、LNR、LRN 也分别称为先根遍历、中根遍历和后根遍历。
5.2.2 递归遍历的函数接口
三种深度优先遍历都可以基于二叉树的递归定义，用递归函数简洁实现。三个遍历函数的接口声明如下：
// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);5.2.3 前序遍历递归执行过程详解
二叉树的递归定义天然适配递归遍历逻辑，下面我们以前序遍历为例，完整拆解递归调用与返回的完整执行过程。中序与后序遍历仅调整访问根结点的时机，递归调用的整体路径完全一致，大家可以对照逻辑自行推导。
核心递归逻辑
前序遍历遵循「根 → 左 → 右」的规则，递归函数的执行逻辑为：
- 如果当前结点为空（NULL），直接返回，这是递归的终止条件；
- 先访问当前根结点；
- 递归遍历当前结点的左子树；
- 递归遍历当前结点的右子树。
逐步骤递归调用过程
我们以下图中的二叉树为例（根结点 1，左孩子 2、右孩子 4；结点 2 的左孩子为 3；结点 4 的左孩子为 5、右孩子为 6；所有叶子结点的左右子树均为空），逐步拆解前序遍历的执行流程：
- 调用
PreOrder(结点1)：访问结点 1，随后递归进入左子树，调用PreOrder(结点2) - 调用
PreOrder(结点2)：访问结点 2，随后递归进入左子树，调用PreOrder(结点3) - 调用
PreOrder(结点3)：访问结点 3，随后递归进入左子树，调用PreOrder(NULL) - 调用
PreOrder(NULL)：触发递归终止条件，直接返回到结点 3 - 结点 3 继续递归进入右子树，调用
PreOrder(NULL)，再次触发终止条件返回；结点 3 遍历完成，返回到结点 2 - 结点 2 递归进入右子树，调用
PreOrder(NULL)，触发终止条件返回；结点 2 遍历完成，返回到结点 1 - 结点 1 递归进入右子树，调用
PreOrder(结点4) - 调用
PreOrder(结点4)：访问结点 4，随后递归进入左子树，调用PreOrder(结点5) - 调用
PreOrder(结点5)：访问结点 5，左、右子树依次递归调用均为 NULL，逐层返回；结点 5 遍历完成，返回到结点 4 - 结点 4 递归进入右子树，调用
PreOrder(结点6) - 调用
PreOrder(结点6)：访问结点 6，左、右子树依次递归调用均为 NULL，逐层返回；结点 6 遍历完成，返回到结点 4 - 结点 4 遍历完成，返回到结点 1，整棵二叉树的前序遍历结束
最终得到前序遍历序列：1 2 3 4 5 6
图解说明
图中红色箭头代表递归深入调用的方向，绿色箭头代表递归结束后的返回方向，每一个虚线框都对应一次函数调用的完整生命周期。可以看到，递归遍历本质上是沿着二叉树的结构深度优先深入，遇到空结点就回溯，最终覆盖所有结点。
补充：中序遍历和后序遍历的递归调用路径与前序完全一致，区别仅在于访问根结点的时机：
- 中序：左子树递归返回后、右子树递归前，访问根结点
- 后序：左、右子树都递归返回后，再访问根结点
✏️ 概念巩固选择题
参考答案：1.A 2.A 3.D 4.A
