1. 六级新增知识框架

• 树的定义、构造与遍历。
• 哈夫曼树、完全二叉树、二叉排序树。
• 哈夫曼编码、格雷编码。
• DFS、BFS、二叉树搜索。
• 一维动态规划、简单背包。
• 面向对象思想，类的创建与初始化，封装/继承/多态概念。
• 栈、队列、循环队列。

2. 树的基本术语

术语	含义
根节点	没有父节点的节点
父/子节点	直接上下层关系
兄弟节点	父节点相同
叶子节点	没有子节点
节点的度	子树/直接子节点数量
深度	根到该节点的层次距离（具体从 0/1 计需看定义）
高度	该节点到最深叶子的距离/层数（需看题目定义）
子树	某节点及其后代形成的树

做题第一件事：确认题目对“深度/高度/层数”从 0 还是 1 开始计。

3. 二叉树基本性质

在“根为第 1 层”的常见定义下：

• 第 $i$ 层最多 $2^{i-1}$ 个节点。
• 深度为 $k$ 的二叉树最多 $2^k-1$ 个节点。
• 对任意非空二叉树，若 $n_0$ 是叶子数、$n_2$ 是度为 2 的节点数，则 $n_0=n_2+1$。

完全二叉树：除最后一层外都满，最后一层节点从左到右连续排列。

4. 二叉树遍历

遍历	顺序	口诀
前序	根 → 左 → 右	根在前
中序	左 → 根 → 右	根在中
后序	左 → 右 → 根	根在后
层序	一层一层从上到下	用队列

void preorder(Node* root) {
    if (!root) return;
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

5. 完全二叉树数组下标关系

若采用 1-based 数组：

• 父节点：i / 2
• 左孩子：2 * i
• 右孩子：2 * i + 1

若采用 0-based 数组【辅助补充】：

• 父节点：(i - 1) / 2
• 左孩子：2 * i + 1
• 右孩子：2 * i + 2

6. 二叉搜索树 BST

对每个节点：

• 左子树关键字通常小于节点关键字。
• 右子树关键字通常大于节点关键字。
• 中序遍历得到有序序列（具体重复值规则由实现定义）。

平均查找/插入/删除可接近 $O(\log n)$，但树退化成链时最坏可到 $O(n)$。

7. 哈夫曼树与哈夫曼编码

哈夫曼树

目标：使带权路径长度最小。

构造核心：不断选择权值最小的两个节点合并，新节点权值为二者之和。

若叶子权值为 $w_i$、深度为 $d_i$，带权路径长度可表示为：$WPL=\sum w_i d_i$。

哈夫曼编码

• 基于哈夫曼树得到前缀编码。
• 任意一个字符编码都不是另一个字符编码的前缀，因此可无歧义解码。
• 高频字符通常分配更短编码。

8. 格雷编码

格雷码特点：相邻两个编码仅有 1 位不同。

常见二进制转格雷码公式【辅助补充，与六级原理一致】：

$g=n\oplus(n>>1)$。

9. DFS 深度优先搜索

核心：沿一条路径尽可能深入，不能继续时回溯。

void dfs(State u) {
    标记 u;
    for (每个可达状态 v) {
        if (v 合法且未访问) dfs(v);
    }
}

适用：

• 连通性。
• 枚举所有方案/路径。
• 树遍历。
• 回溯搜索。

在图采用邻接表时，一次完整遍历通常为 $O(V+E)$。

10. BFS 广度优先搜索

核心：按“距离起点的层数”逐层扩展，使用队列。

queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : next[u]) {
        if (!vis[v]) {
            vis[v] = true;
            q.push(v);
        }
    }
}

在无权图/每条边代价相同时，BFS 第一次到达某点即可得到最少边数意义下的最短距离。

11. DFS 与 BFS 对比

项目	DFS	BFS
核心结构	递归/栈	队列
扩展方式	先深后回	按层扩展
无权最短路	不保证	保证
找所有方案	常用	可用但通常不是首选
连通块	可

12. 动态规划 DP 基本思想

DP 适合具有：

• 重叠子问题。
• 最优子结构。

五步法：

1. 定义状态 dp[...] 的准确含义。
2. 写出初始状态。
3. 推导状态转移方程。
4. 确定计算顺序。
5. 找最终答案位置。

13. 一维 DP

例：最大不相邻和（示意）：

$dp[i]=\max(dp[i-1],dp[i-2]+a_i)$。

重点不是背公式，而是背“dp[i] 表示什么”。

14. 0/1 背包

每件物品最多选一次。

若物品体积 $w_i$、价值 $v_i$、容量 $W$：

一维优化转移：

$dp[j]=\max(dp[j],dp[j-w_i]+v_i)$。

容量 j 必须从大到小遍历，防止同一件物品被重复使用。

for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

15. 栈、队列、循环队列

结构	原则	常见操作	典型应用
栈	LIFO 后进先出	push/pop/top	括号匹配、递归、表达式
队列	FIFO 先进先出	push/pop/front/back	BFS、任务排队
循环队列	数组首尾相接	head/tail 配合取模	固定容量队列

循环队列下标推进常写：next = (index + 1) % capacity。

16. 面向对象与类

class Student {
private:
    int score;
public:
    Student(int s = 0) : score(s) {}
    int getScore() const { return score; }
};

三大特性概念

特性	核心含义
封装	将数据与操作绑定，并控制访问权限
继承	新类复用/扩展已有类
多态	同一接口在不同对象上表现不同

访问权限：public、private、protected。

17. 六级必背易错点

1. 前/中/后序的区别只看“根节点何时访问”。
2. BST 平均 $O(\log n)$，退化时可到 $O(n)$。
3. BFS 只对无权/等权边保证“层数最短”。
4. DFS 递归要考虑访问标记和回溯恢复。
5. 0/1 背包一维优化容量从大到小。
6. 队列的 pop() 不返回队首值，要先 front()。
7. 格雷码相邻编码只差 1 位。

18. 六级背诵清单

• [ ] 树术语和二叉树性质。
• [ ] 前/中/后/层序遍历。
• [ ] 完全二叉树数组下标公式。
• [ ] BST、哈夫曼树、哈夫曼编码、格雷码。
• [ ] DFS/BFS 对比。
• [ ] DP 五步法与 0/1 背包倒序容量。
• [ ] 栈、队列、循环队列。
• [ ] 类、封装、继承、多态。