知识块①：树与二叉树——“最重要的非线性数据结构”
1.1 树的基本概念——“从根出发，分层生长”
树是由n（n≥0）个节点组成的有限集合。当n=0时称为空树。树有一个根节点，其他节点分属若干互不相交的子树。
基本术语：
· 根：最顶层的节点，一棵树只有一个根
· 叶子：没有子节点的节点
· 父节点 / 子节点：上下直接相连的节点
· 兄弟节点：同一个父节点的多个子节点
· 深度：从根到该节点的路径上的边数（根深度为0）
· 高度：从该节点到最远叶子的边数（叶子高度为0）
1.2 二叉树——“每个节点最多两个孩子”
二叉树是每个节点最多有两个子树的树结构，分左子树和右子树。非常重要：二叉树不是树的特例，而是一种独立的树结构。
（2025年12月第6题） 练习题： 一棵二叉树中，每个节点最多有几个孩子？
答案：2个。
1.3 二叉树的三种遍历方式——必考！几乎每套题都有
遍历就是按照某种顺序访问树中的每个节点。三种最基本的遍历方式：
前序遍历（先序遍历）
访问顺序：根 → 左 → 右
口诀：“根左右”
记忆法：先访问根
中序遍历
访问顺序：左 → 根 → 右
口诀：“左根右”
记忆法：根在中间
后序遍历
访问顺序：左 → 右 → 根
口诀：“左右根”
记忆法：最后访问根
（2024年3月第12题、2024年9月第8题、2025年6月第8题、2025年9月第7题、2026年3月第7题、2026年6月第8题）
经典题型一：由前序+中序还原二叉树，求后序遍历
这是六级考试中的最经典题型，几乎每套题都会出现。我们用一个例子来逐步讲解：
例题：前序遍历为 ABCDEF，中序遍历为 CBAEDF，求后序遍历。
解题步骤： （这是一道“分治”问题）
第一步： 前序的第一个元素是根。
第二步： 在中序中找到根A的位置，左边的都是左子树，右边的都是右子树。
· 中序：C B A E D F
· 左子树（中序）：C B（在A左边）
· 右子树（中序）：E D F（在A右边）
第三步： 左子树的前序是 B C，中序是 C B → B是左子树的根，C是B的左孩子
第四步： 右子树的前序是 D E F，中序是 E D F → D是右子树的根，E是D的左孩子，F是D的右孩子
最终树结构：
后序遍历（左右根）： C → B → E → F → D → A
（2026年3月第7题） 练习题： 前序为ABDCEGFHI，中序为DBAEGCHFI，求后序？
· 根A，左子树（前序B D，中序D B），右子树（前序C E G F H I，中序E G C H F I）
· 左子树：B是根，D是B的左孩子
· 右子树：C是根，左子树（前序E G，中序E G）→ G是E的右孩子，右子树（前序F H I，中序H F I）→ F是根，H是F的左孩子，I是F的右孩子
· 后序：BDGEHIFCA
经典题型二：由一种遍历推树结构
（2026年3月第8题） 练习题： 已知中序遍历为D B E A F C G，以下哪种遍历序列组合可以唯一确定二叉树？
· A. 前序+后序 B. 后序+中序 C. 前序+中序 D. 以上都可以
· 答案：B、C。前序+中序或后序+中序都可以唯一确定二叉树。但仅有前序+后序不能唯一确定。
1.4 完全二叉树——“除最后一层外全满，且最后一层节点靠左”
定义： 一棵二叉树中，只有最下面两层的节点可以小于2，且最下一层的节点全部集中在左侧。（2025年6月第6题）
（2025年12月第6题、2026年6月第6题） 练习题： 如何判断一棵树是完全二叉树？
答案：层序遍历，遇到空节点后不应再出现非空节点。
重要性质：
1. 节点数n与高度h的关系： h = ⌊log₂n⌋ + 1（2025年12月判断第10题）
2. 数组存储： 下标为i的节点，左孩子下标为2i，右孩子下标为2i+1（2024年9月第9题、2025年9月第8题）
3. 完全二叉树可以用数组完美存储，空间利用率高（2024年6月判断第7题）
（2024年3月第10题） 练习题：完全二叉树有5个叶子节点，最多有多少个节点？
完全二叉树中，叶子节点数 = 内部节点数 + 1（当度为2的节点数=内部节点数-1时）。最多情况下，最后一层除了叶子还可以有度1的节点。5个叶子，最多可以有 5 + 4 + 1 = 10个节点。.. 实际上需要更精确的计算：完全二叉树中，如果叶子节点数为n，总结点数最多为2n。
1.5 二叉排序树（BST，也称二叉搜索树）——“左小右大”
定义： 左子树所有节点的值 < 根节点的值 < 右子树所有节点的值。左右子树也分别是二叉排序树。（2023年12月判断第8题）
（2025年6月判断第4题） 练习题：二叉排序树的中序遍历结果是什么？
答案：递增有序序列。这是BST最重要的性质之一。
三大操作的时间复杂度：
· 查找： 平均O(log n)，最坏O(n)（退化为链表时，2025年12月第13题）
· 插入： 从根开始，比根小往左，比根大往右，直到空位置插入（2025年6月第13题）
· 删除： 删除有两个孩子的节点时，需要找右子树的最小值（或左子树的最大值）替换（2025年9月第14题）
（2025年6月判断第5题） 练习题： 如果二叉搜索树退化为链表，则查找的时间复杂度为？
答案： O(n)。因为树退化为一条链，查找需要逐个比较。
1.6 满二叉树——“每个节点都有两个孩子”
定义： 所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。
性质： 深度为k的满二叉树共有 2^k - 1 个节点。（2024年6月第10题）
（2024年6月第10题） 练习题： 5层满二叉树有多少个节点？
答案： 2^5 - 1 = 31个节点。
1.7 二叉树深度计算
递归实现——（2023年12月第9题）：
int Depth(TreeNode* root) {
if (root == nullptr) return 0;
return max(Depth(root->left), Depth(root->right)) + 1;
}
1.8 树的存储方式
二叉树可以用数组（完全二叉树用数组存储，下标从1开始，左孩子2i，右孩子2i+1）或链表（结构体+左右指针）存储。（2023年12月第10题）
（2025年6月第7题） 练习题： 用数组表示完全二叉树，下标为i的节点，左孩子下标为多少？
答案： 2i。
知识块②：哈夫曼树与哈夫曼编码——“最优二叉树”
2.1 什么是哈夫曼树？
哈夫曼树（Huffman Tree） 也称最优二叉树，是带权路径长度（WPL）最小的二叉树。（2024年3月第1题）
带权路径长度（WPL）：所有叶子节点的权值 × 路径长度（从根到该叶子的边数）之和。（2026年3月第9题）
2.2 哈夫曼树的构造过程——“贪心算法”
构造步骤（每一步都是贪心选择）：
（2024年6月判断第1题） 练习题：哈夫曼编码的构造使用了什么策略？
答案： 贪心策略。
2.3 哈夫曼树的重要性质
1. 哈夫曼树是二叉树（2024年3月判断第1题） ✓
2. 哈夫曼树中没有度为1的节点（2026年3月第10题）
3. 叶子节点数n与总节点数m的关系： m = 2n - 1（2026年3月第10题、2026年6月第10题）
4. 哈夫曼编码不具有唯一性——同一组频率可能有多种不同的哈夫曼树（2025年9月判断第2题）
2.4 哈夫曼编码——“前缀编码”
定义： 用哈夫曼树构造的编码，任意一个字符的编码都不是另一个字符编码的前缀，因此称为“前缀编码”。（2025年6月判断第2题）
性质：
· 变长编码：频率高的字符编码短，频率低的编码长（2025年3月第2题）
· 无损压缩：可以完全还原原始数据（2023年9月判断第7题）
· 解码无需分隔符：因为前缀编码特性，编码可以连续拼接，解码时不会混淆（2026年3月判断第5题）
（2023年12月第7题） 练习题： 对“hello world”进行哈夫曼编码，最少需要多少比特？
统计字符频率→构造哈夫曼树→计算每个字符的编码长度→频率×编码长度之和。
2.5 哈夫曼编码的计算步骤
（2024年6月第8题） 例题： 对字符串“classmycls”进行哈夫曼编码，最少需要多少比特？
解题步骤：
1. 统计字符频率：c:2, l:1, a:1, s:2, m:1, y:1
知识块③：搜索算法（DFS与BFS）
3.1 深度优先搜索（DFS）——“一条路走到黑，再回头”
核心思想： 从根节点出发，沿着每个分支路径尽可能深入，直到不能再深入为止，然后回溯到上一个分支点继续探索。（2023年12月判断第4题）
形象理解： 就像走迷宫，选一条路一直走到底，走不通就退回到上一个岔路口，换一条路继续走。
实现方式：
· 递归方式：函数调用自身（最简单）
· 非递归方式：用栈模拟（2025年6月判断第9题、2024年6月判断第9题）
时间复杂度： O(V + E)，V为顶点数，E为边数（2023年9月判断第9题）
DFS的应用： 二叉树遍历（前序/中序/后序都是DFS）、图的遍历、树的深度计算、路径查找、连通性判断。
（2025年12月第11题） 非递归前序遍历（用栈）：
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* node = st.top(); st.pop();
cout << node->val; // 访问根
if (node->right) st.push(node->right); // 先右后左（因为栈是后进先出）
if (node->left) st.push(node->left);
}
3.2 广度优先搜索（BFS）——“逐层推进，不抢跑”
核心思想： 从根节点出发，逐层遍历，先访问距离根最近的节点，再访问次近的，依次向外扩展。（2024年3月第8题）
形象理解： 就像投石入水，水波一圈一圈向外扩散——先近后远，逐层推进。
实现方式：队列（先进先出）（2024年12月第12题、2024年6月判断第6题）
时间复杂度： O(n)（2025年9月第12题）
BFS的应用：层序遍历、最短路径、树的右视图（每层最右侧节点，2026年3月第12题）
（2025年3月第11题） BFS实现代码（用队列）：
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front(); q.pop();
// 处理节点
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
3.3 DFS vs BFS 对比表
核心思想
深度优先搜索（DFS）： 沿着分支深入到底再回溯
广度优先搜索（BFS）： 逐层向外扩展
辅助数据结构
深度优先搜索（DFS）： 栈（递归/非递归）
广度优先搜索（BFS）： 队列
遍历顺序
深度优先搜索（DFS）： 按深度优先，一条分支走完才换分支
广度优先搜索（BFS）： 按层，同一层节点全部访问完才到下一层
时间复杂度
深度优先搜索（DFS）： O(V+E)
广度优先搜索（BFS）： O(V+E)
空间复杂度
深度优先搜索（DFS）： 最坏O(V)（递归栈深度）
广度优先搜索（BFS）： 最坏O(V)（队列长度）
适用场景
深度优先搜索（DFS）： 路径搜索、树的遍历、连通性判断
广度优先搜索（BFS）： 最短路径、层序遍历、拓扑排序
知识块④：动态规划——“最优子结构 + 重叠子问题”
4.1 动态规划的核心思想——“大事化小，小事化了”
定义： 将复杂问题分解为若干重叠子问题，通过求解子问题的最优解，逐步构建出原问题的最优解。
两个基本性质——必考！
1. 最优子结构： 问题的最优解包含子问题的最优解（2024年3月第11题、2024年6月第11题）
2. 重叠子问题： 子问题被重复计算，可以通过存储中间结果（如数组）避免重复计算
（2024年6月判断第10题） 练习题：0-1背包问题使用贪心算法可以保证获得最优解吗？
答案： 不能。贪心不一定得到最优解，动态规划才能保证最优解。
4.2 一维线性动态规划——“最简单的DP”
经典例题——不相邻元素最大和（打家劫舍问题）：
（2024年3月第7题、2025年9月第10题、2026年6月第14题）
问题描述： 一排房屋，每个房屋有若干现金，不能偷相邻的房屋，求最多能偷多少钱。
逐步推导：
1. 定义状态： dp[i] 表示前i个房屋能偷到的最大金额
· 不偷：dp[i] = dp[i-1]
· 偷：dp[i] = dp[i-2] + nums[i]（因为不能偷相邻的，所以前i-2个的最大值+当前）
· 取最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
1. 初始化： dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
4.3 0/1背包问题——必考！几乎每套题都有
问题描述： 有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，每个物品最多选1个，求最大价值。
（2025年6月第15题、2025年9月第15题、2025年12月第14题、2026年6月第15题）
二维状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
· dp[i][j]：前i个物品放入容量为j的背包的最大价值
· dp[i-1][j]：不放第i个物品
· dp[i-1][j-w[i]] + v[i]：放第i个物品
一维滚动数组优化（空间从O(nC)降到O(C)）：
// 注意：内层循环必须从大到小（逆序）！
// 因为如果从小到大，物品会被重复使用（变成完全背包）
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = C; j >= w[i]; j--) // 逆序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
（2026年3月判断第9题） 练习题：0-1背包一维动态规划中，内层循环为什么必须逆序？
答案： 为了保证每个物品只被选择一次。如果正序，dp[j-w[i]]可能已经包含了当前物品，导致物品被重复使用。
4.4 完全背包——“每个物品可以选无限次”
与0/1背包的唯一区别： 每个物品可以选无限次。
一维滚动数组（内层循环从小到大）：
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= C; j++) // 正序！允许重复使用
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
（2025年6月编程题1、2026年6月编程题1）
4.5 动态规划 vs 贪心算法
决策方式
动态规划： 考虑所有可能的子问题，取最优
贪心算法： 每一步选当前最优，不做“回头看”
子问题重叠
动态规划： 有重叠子问题，需要存储中间结果
贪心算法： 无重叠子问题
最优性保证
动态规划： 保证全局最优
贪心算法： 不一定保证全局最优
适用场景
动态规划：最优子结构+重叠子问题
贪心算法： 局部最优可推出全局最优
知识块⑤：面向对象编程（C++类与对象）
5.1 面向对象三大特性——必考！
1. 封装（Encapsulation）： 将数据和操作数据的方法绑定在一起，对外隐藏内部实现细节，通过访问权限控制外部访问。（2025年3月判断第8题）
2. 继承（Inheritance）： 从已有类派生出新类，子类继承父类的属性和方法。（2024年3月判断第3题）
3. 多态（Polymorphism）： 同一操作作用于不同对象产生不同的执行结果。C++中通过虚函数（virtual）实现运行时多态。（2025年6月第3题）
（2024年6月第1题） 练习题：面向对象编程的三大原则是什么？
答案： 封装、继承、多态。
5.2 类的定义与使用
class Student {
private: // 私有成员，外部不可直接访问
string name;
int age;
public: // 公有成员，外部可访问
// 构造函数（与类名相同，无返回值）
Student(string n, int a) : name(n), age(a) {}
// 成员函数
void display() { cout << name << " " << age; }
};
5.3 构造函数与析构函数——高频考点
构造函数（Constructor）：
· 与类名相同，无返回值，创建对象时自动调用
· 可以有多个构造函数（函数重载）（2025年3月判断第5题）
· 构造函数不能声明为虚函数（2025年6月判断第1题、2026年6月第1题）
· 如果没有定义构造函数，编译器会生成默认构造函数（2023年12月判断第2题）
· 默认构造函数可以被声明为private（2025年3月第6题）
析构函数（Destructor）：
· 名称=~类名，无参数无返回值
· 对象销毁时自动调用
· 基类析构函数通常声明为虚函数，以便通过基类指针正确释放派生类对象（2026年6月第1题）
· 析构函数可以被声明为private（2025年3月第6题）
5.4 访问权限控制
私有
关键字：private
本类内部：✓
派生类（子类）：✗
外部：✗
保护
关键字：protected
本类内部：✓
派生类（子类）：✓
外部：✗
公有
关键字：public
本类内部：✓
派生类（子类）：✓
外部：✓
（2023年12月第1题、2024年9月第2题） 练习题： 派生类能否访问父类的private成员？
答案： 不能。private成员只有本类内部可以访问，派生类也不能访问。
5.5 静态成员
· 静态成员变量： 被所有对象共享，类外初始化（2023年9月第15题）
· 静态成员函数： 只能访问静态成员，不能访问非静态成员（2024年12月判断第2题）
（2023年9月第4题） 练习题： static修饰的静态成员有什么特性？
答案： 被所有对象共享，所有对象访问的是同一个变量。
5.6 虚函数与多态——高频考点
虚函数： 用virtual关键字修饰的成员函数，允许在派生类中重写（override）。
动态绑定： 通过基类指针或引用调用虚函数时，在运行时根据对象的实际类型决定调用哪个版本的函数。（2026年6月第2题）
class Base {
public:
virtual void show() { cout << "Base"; } // 虚函数
virtual ~Base() {} // 虚析构函数
};
class Derived : public Base {
public:
void show() override { cout << "Derived"; } // 重写
};
int main() {
Base* p = new Derived();
p->show(); // 输出 "Derived"（动态绑定，运行时决定）
delete p; // 正确调用Derived的析构函数
}
5.7 类与结构体的区别
在C++中，class和struct的区别仅在于默认访问权限：class默认private，struct默认public。（2026年3月第1题）
知识块⑥：栈与队列
6.1 栈（Stack）——“先进后出，后进先出”
定义： 只允许在一端（栈顶）进行插入（push）和删除（pop）操作。（2024年6月第5题）
（2024年6月第5题） 练习题： 栈的基本特性是什么？
答案：先进后出（FILO），后进先出（LIFO）。
应用场景：
· 函数调用管理（递归调用栈，2025年12月判断第5题）
· 括号匹配（2025年3月第14题）
· 文本编辑器撤销操作（2025年12月第4题、2026年6月第4题）
· DFS非递归实现（2024年6月第14题）
· 十进制转二进制（2024年6月第6题）
栈的合法性判断（2024年9月第3题）： 给定入栈序列，判断出栈序列是否合法。这是一道经典题，需要模拟入栈出栈过程来验证。
C++ STL栈：std::stack，push()入栈，pop()出栈（不返回栈顶元素，2025年9月判断第4题），top()取栈顶元素。
6.2 队列（Queue）——“先进先出，排队办事”
定义： 只允许在一端（队尾）插入（enqueue），在另一端（队头）删除（dequeue）。（2024年3月第3题）
（2024年3月第3题） 练习题： 队列的基本特性是什么？
答案：先进先出（FIFO）。
应用场景：
· BFS（广度优先搜索）实现（2024年6月第13题）
· 任务调度、打印机队列
· 缓冲区管理
C++ STL队列：std::queue，push()入队，pop()出队（不返回队头），front()取队头元素。
6.3 循环队列——“数组模拟队列，空间复用”
定义： 用数组实现队列，通过取模运算实现队头队尾指针循环移动，避免“假溢出”。（2024年6月第7题）
关键操作：
· 入队：rear = (rear + 1) % maxSize
· 出队：front = (front + 1) % maxSize
· 判空：front == rear
· 判满：(rear + 1) % maxSize == front（空一格判满，2025年6月第5题）
（2025年3月第9题、2026年3月第4题） 练习题：循环队列的判满条件是什么？
答案： (rear + 1) % maxSize == front。循环队列通常空出一个位置来区分队空和队满。
应用场景： 生产者和消费者问题中的共享缓冲区（2026年3月第5题）
知识块⑦：格雷编码
7.1 什么是格雷码？
格雷码（Gray Code）： 一种二进制编码方式，相邻两个编码之间只有一位不同。（2024年3月第6题、2025年3月第2题）
性质： 首尾两个编码之间也只有一位不同（循环码）。
7.2 格雷码的生成
（2025年9月第10题） 递归生成方式： n位格雷码由n-1位格雷码先按顺序生成，再按逆序生成，并在前半部分前面加0，后半部分前面加1。
举例： 2位格雷码 → 3位格雷码
· 2位：00, 01, 11, 10
· 3位：
· 前半部分（加0）：000, 001, 011, 010
· 后半部分（加1，逆序）：110, 111, 101, 100
· 结果：000, 001, 011, 010, 110, 111, 101, 100
迭代生成公式：gray(i) = i ^ (i >> 1)
7.3 格雷码的应用
· 数字通信中的错误检测
· 模数转换器（ADC）
· 卡诺图化简
