1. KMP字符串匹配算法#

考研核心考点：

• 核心思想：通过预处理模式串生成next（或nextval）数组，避免暴力匹配中主串指针的回溯，将时间复杂度从暴力的$O(nm)$优化至$O(n+m)$，其中$n$为主串长度，$m$为模式串长度。
• 关键概念：最长相等前后缀，即模式串前缀集合与后缀集合的交集元素中最长的那个，用于构建next数组，next[j]表示模式串前$j$个字符组成的子串的最长相等前后缀长度。
• 延伸考点：改进型nextval数组，用于消除next数组中重复的回溯操作；真题常考查手动推导next/nextval数组、算法代码实现、匹配过程推演。

2. 二叉树与树的核心性质公式#

考研高频考点：

• 通用二叉树性质：$n_0 = n_2 +1$（$n_0$为叶子结点数，$n_2$为度为2的结点数）；总结点数$N = n_0 +n_1 +n_2$。
• 满二叉树性质：深度为$k$的满二叉树总结点数为$2^k -1$，第$i$层结点数为$2^{i-1}$。
• 完全二叉树性质：按层序编号（从1开始）时，结点$i$的左孩子为$2i$、右孩子为$2i+1$，父结点为$\lfloor i/2 \rfloor$；叶子结点数为$\lceil N/2 \rceil$，度为1的结点数仅为0或1。

3. 二叉树的遍历#

考研必考考点：

• 遍历类型：前序、中序、后序（递归/非递归实现）、层序遍历（队列实现），其中非递归遍历是高频笔试考点，需熟练掌握栈实现逻辑。
• 核心应用：已知两种遍历序列（前序+中序、后序+中序、层序+中序）推导二叉树结构，进而求解第三种遍历序列。
• 衍生应用：通过遍历统计结点数、计算树深、筛选目标结点等。

4. 线索二叉树#

考研常考细节考点：

• 核心概念：利用二叉链表中空的左/右指针域，存储结点在指定遍历顺序下的前驱、后继线索，将遍历的空间复杂度从$O(n)$优化至$O(1)$。
• 分类：前序线索二叉树、中序线索二叉树、后序线索二叉树，其中中序线索二叉树的遍历实现是考查重点。
• 考点延伸：线索化的过程、线索二叉树的结点结构定义、遍历逻辑推演。

5. 树的存储结构#

各类存储结构的适用场景：

1. 双亲表示法（顺序存储）：每个结点存储数据域与双亲下标，优点是快速查找双亲结点，缺点是查找孩子结点效率低，适用于频繁查询父结点的场景。
2. 孩子表示法：采用“数组+链表”结构，每个结点挂载孩子链表，优点是快速查找孩子结点，缺点是查找双亲结点效率低。
3. 孩子兄弟表示法（二叉链表表示法）：每个结点存储数据、第一个孩子指针、右兄弟指针，是树与二叉树转换的核心依据。

6. 树、森林与二叉树的转换#

考研必考转换规则：

1. 树转二叉树：遵循“左孩子右兄弟”规则，将所有兄弟结点添加连线，仅保留每个结点的第一个孩子连线，最终旋转得到二叉树，转换后的二叉树根结点无右子树。
2. 森林转二叉树：先将每棵树独立转换为二叉树，再依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右兄弟进行链接。
3. 二叉树转森林：断开根结点的所有右子树链，将每个断开的右子树独立转换为树，最终得到森林。

• 遍历对应关系：树的先根遍历对应二叉树前序遍历，树的后根遍历对应二叉树中序遍历；森林的先序遍历对应二叉树前序遍历，森林的中序遍历对应二叉树中序遍历。

7. 哈夫曼树与编码#

考研数据压缩核心考点：

• 哈夫曼树（最优二叉树）：带权路径长度$WPL$最小的二叉树，构造规则为每次选取两个权值最小的结点合并为新结点，新结点权值为两者之和，重复至仅剩一个结点。
• 核心性质：哈夫曼树总结点数为$2n_0 -1$（$n_0$为叶子结点数）。
• 哈夫曼编码：基于哈夫曼树生成的前缀编码，任意编码均不为其他编码的前缀，可实现无损数据压缩，真题常考查$WPL$计算、编码生成、构造哈夫曼树。

8. 并查集#

考研图论配套高频考点：

• 核心操作：find（查找元素所在集合的根结点，搭配路径压缩优化）、union（合并两个集合，搭配按秩合并优化），时间复杂度近似$O(\alpha(n))$，$\alpha$为阿克曼函数反函数，可视为常数。
• 应用场景：Kruskal最小生成树算法、图的连通性判断、求解连通分量数量等。
• 考点延伸：并查集的数组/链式结构实现、优化逻辑的原理。