欢迎阅读本篇学习笔记。本篇作为个人计算机专业的学习记录这里将系统梳理二叉树的相关知识点从基础概念到代码实现逐步展开便于后续的复习巩固。如有不足欢迎大家在评论区交流指正感谢大家的阅读与支持1.树概念及结构1.1树的概念在学习二叉树之前我们先来了解一下树的概念。树是一种非线性的数据结构它是由 nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。有一个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成 M (M0) 个互不相交的集合 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 的子孙。森林由 mm0棵互不相交的树的集合称为森林。森林可以看作是多棵树的集合在实际应用中森林与树的转换是常见的操作。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的结点产生两条边所以总边数为: * n12*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.B2. 二叉树的存储结构二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。1. 顺序存储顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们下一部分会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。对应下面配图左侧为完全二叉树的数组存储右侧为一般二叉树的数组存储对比2. 链式存储二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面随着我们学习的深入会学到红黑树等等会用到三叉链。3. 堆的概念及结构在上一部分我们了解了二叉树的两种存储结构其中顺序存储数组最适合表示完全二叉树而现实中最典型的应用就是「堆」。这一部分内容我们将会讲解堆的概念、实现与应用。我们先来了解一下堆和二叉树的区别。3.1 堆的定义与性质若存在一个关键码的集合 K {k0, k1, k2, ..., k (n-1)}将其所有元素按照完全二叉树的顺序存储方式存放于一维数组中并且满足下述关系则称该集合为堆若满足 Ki ≤ K (2i1) 且 Ki ≤ K (2i2)则称为小根堆小顶堆此时根结点为全局最小值若满足 Ki ≥ K (2i1) 且 Ki ≥ K (2i2)则称为大根堆大顶堆此时根结点为全局最大值。堆的核心性质堆中任意结点的值总是不大于小根堆或不小于大根堆其父结点的值堆在逻辑上一定是一棵完全二叉树物理上用一维数组存储。小根堆与大根堆示例小根堆父结点 ≤ 左右孩子逻辑结构根为 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.C3. 堆的实现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 33.3 建堆的时间复杂度因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的 就是近似值多几个结点不影响最终结果)因此建堆的时间复杂度为 ON3.4 堆的插入这里展示的是小堆的插入大堆也是类似的堆的插入操作分为两步将新元素插入到数组的尾部也就是完全二叉树的最后一个叶子位置对新插入的结点执行向上调整算法从该结点开始不断与父结点比较若不满足堆性质则交换直到满足堆性质或到达根结点。3.5 堆的删除堆的删除默认删除堆顶元素即当前堆的最值操作步骤将堆顶元素与数组最后一个元素交换删除数组的最后一个元素原堆顶元素对新的堆顶元素执行向下调整算法恢复整个堆的性质。这种删除方式可以保证删除后结构仍然是合法的堆单次删除的时间复杂度为 OlogN。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-gt;_left node2; node1-gt;_right node4; node2-gt;_left node3; node4-gt;_left node5; node4-gt;_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好啦那这篇内容就先整理到这里这次把二叉树的相关知识整理了一下为了方便自己日后复习回顾也希望能给正在学习的小伙伴一些参考。如果文中有理解不到位或是书写有误的地方欢迎大家在评论区指出一起交流共同进步。谢谢大家