GESP C++ 六级：二叉树基础与遍历系统梳理

核心目标：理解二叉树的逻辑结构与存储方式，掌握链式存储与顺序存储的特点，熟练实现前序、中序、后序、层序四种遍历，能利用遍历序列解决还原二叉树、求深度/节点数等问题，能辨析遍历相关选择题与程序阅读题。
二叉树是每个节点最多两个孩子的树；遍历是“按某种顺序访问所有节点”——前序根左右、中序左根右、后序左右根、层序用队列逐层访问；已知前序+中序（或中序+后序）可唯一还原二叉树。

一、考纲定位

根据 CCF 官方考纲，GESP 六级数据结构部分明确要求掌握树与二叉树的基本概念、存储结构和遍历方法，以及它们在算法问题中的应用。

二叉树在六级考试中的考查分布：

考点	重要程度	典型考法
二叉树基本概念（根、叶子、深度、度）	★★★★★	选择题高频
满二叉树与完全二叉树
链式存储与顺序存储	★★★★☆	代码填空、选择题
前序、中序、后序遍历（递归）	★★★★★	程序阅读、代码填空
层序遍历（队列）		编程题高频
已知遍历序列还原二叉树	★★★★☆	编程题、选择题
二叉树的性质与计算		选择题
遍历的应用（求深度、节点数、叶子数）		编程题

二、二叉树基本概念

2.1 什么是二叉树

二叉树是每个节点最多有两个子节点的树形结构。两个子节点分别称为左孩子和右孩子，次序不能颠倒。

基本术语：

术语	含义
根节点	树的最顶层节点，没有父节点
叶子节点	没有孩子的节点
内部节点	至少有一个孩子的节点
节点的度	该节点拥有的孩子数量（0、1、2）
树的深度/高度	从根到最远叶子经过的节点数（或边数，题目会明确）
层	根为第1层（或第0层），依次向下
子树	以某个节点为根的子树

2.2 特殊二叉树

满二叉树：每一层的节点数都达到最大，即深度为 k 的满二叉树有 $2^k - 1$ 个节点。

完全二叉树：除了最后一层外，其他层都是满的，且最后一层的节点都集中在左侧。完全二叉树适合用数组顺序存储。

二叉搜索树（BST） ：左子树所有节点值 < 根值 < 右子树所有节点值（六级可能涉及，但重点在遍历）。

2.3 二叉树的重要性质

性质	说明
第 i 层最多有 $2^{i-1}$ 个节点（根为第1层）	每层最多翻倍
深度为 k 的二叉树最多有 $2^k - 1$ 个节点	满二叉树时达到最大
叶子数 = 度为2的节点数 + 1	$n_0 = n_2 + 1$
完全二叉树中，节点 i 的左孩子为 2i，右孩子为 2i+1（根从1开始）	顺序存储的基础

三、二叉树的存储方式

3.1 链式存储（最常用）

每个节点包含数据域和两个指针域，分别指向左孩子和右孩子。

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

创建节点：

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);

3.2 顺序存储（数组）

用数组存储完全二叉树，根节点放在下标 1（或 0）。下标关系：

关系	根从1开始	根从0开始
左孩子	2 * i	2 * i + 1
右孩子	2 * i + 1	2 * i + 2
父节点	i / 2	(i - 1) / 2

优点：访问方便，不需要指针。
缺点：非完全二叉树会浪费大量空间。

四、二叉树的遍历

遍历是指按照某种顺序访问二叉树中的所有节点，每个节点恰好访问一次。四种主要遍历方式：

遍历方式	访问顺序	典型应用
前序遍历	根 → 左 → 右	复制树、输出目录结构
中序遍历	左 → 根 → 右	二叉搜索树得到有序序列
后序遍历	左 → 右 → 根	释放树、计算表达式
层序遍历	逐层从左到右	BFS、求深度、按层输出

4.1 前序遍历（递归）

void preorder(Node* root) {
    if (root == nullptr) return;   // 终止条件
    cout << root->val << " ";      // 访问根
    preorder(root->left);          // 递归左子树
    preorder(root->right);         // 递归右子树
}

4.2 中序遍历（递归）

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);           // 递归左子树
    cout << root->val << " ";      // 访问根
    inorder(root->right);          // 递归右子树
}

4.3 后序遍历（递归）

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);         // 递归左子树
    postorder(root->right);        // 递归右子树
    cout << root->val << " ";      // 访问根
}

4.4 层序遍历（队列）

层序遍历使用队列实现：根节点入队，然后循环出队并访问，同时将左右孩子入队。

void levelorder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

按层输出（了解）：可以在每层结束时输出换行，需要记录当前层节点数。

void levelorderByLevel(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node* cur = q.front(); q.pop();
            cout << cur->val << " ";
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << endl;
    }
}

4.5 非递归遍历（了解）

前序非递归（用栈，先右后左入栈）：

void preorderIter(Node* root) {
    if (!root) return;
    stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* cur = st.top(); st.pop();
        cout << cur->val << " ";
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
    }
}

中序非递归：

void inorderIter(Node* root) {
    stack<Node*> st;
    Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        cout << cur->val << " ";
        cur = cur->right;
    }
}

后序非递归较复杂，六级一般以递归和层序为主。

五、已知遍历序列还原二叉树

5.1 前序 + 中序 → 唯一确定二叉树

方法：

1. 前序的第一个元素是根。
2. 在中序中找到根的位置，左边是左子树的中序，右边是右子树的中序。
3. 根据左子树节点数，在前序中划分出左子树和右子树的前序。
4. 递归构建。

Node* build(int preL, int preR, int inL, int inR) {
    if (preL > preR) return nullptr;
    int rootVal = pre[preL];
    Node* root = new Node(rootVal);
    int pos = inL;
    while (in[pos] != rootVal) pos++;   // 在中序中找根
    int leftLen = pos - inL;
    root->left = build(preL + 1, preL + leftLen, inL, pos - 1);
    root->right = build(preL + leftLen + 1, preR, pos + 1, inR);
    return root;
}

5.2 中序 + 后序 → 唯一确定二叉树

方法：后序的最后一个元素是根。在中序中找到根，划分左右子树，递归构建。

5.3 前序 + 后序 → 不能唯一确定

前序和后序无法确定左右子树的边界，因此不能唯一还原一棵二叉树。这是高频选择题考点。

六、遍历的典型应用

6.1 求二叉树的深度

int depth(Node* root) {
    if (root == nullptr) return 0;
    return 1 + max(depth(root->left), depth(root->right));
}

6.2 求节点总数

int countNodes(Node* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

6.3 求叶子节点数

int countLeaves(Node* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

6.4 复制二叉树

Node* copyTree(Node* root) {
    if (root == nullptr) return nullptr;
    Node* newNode = new Node(root->val);
    newNode->left = copyTree(root->left);
    newNode->right = copyTree(root->right);
    return newNode;
}

6.5 释放二叉树

void freeTree(Node* root) {
    if (root == nullptr) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

七、GESP 六级二叉树真题精讲

真题1：遍历序列判断（选择题）

已知二叉树的前序遍历为 ABDECF，中序遍历为 DBEAFC，则其后序遍历为（ ）。
A. DEBFCA B. DEBCFA C. DBEFCA D. DEFBCA
答案：A

解析：

• 前序第一个 A 是根。
• 中序中 A 左边是 DBE，右边是 FC。
• 左子树前序为 BDE，中序为 DBE，根为 B，左 D 右 E。
• 右子树前序为 CF，中序为 FC，根为 C，左 F。
• 后序：左子树后序 DEB，右子树后序 FC，根 A → DEBFCA。

真题2：层序遍历（编程题）

给定一棵二叉树，输出其层序遍历序列。

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void levelorder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

真题3：完全二叉树顺序存储（选择题）

一棵完全二叉树按顺序存储，根节点下标为 1，则下标为 5 的节点的左孩子下标是（ ）。
A. 10 B. 11 C. 9 D. 12
答案：A
解析：根从1开始，左孩子 = 2*i = 10。

真题4：二叉树性质（选择题）

一棵二叉树有 10 个度为 2 的节点，则叶子节点数为（ ）。
A. 9 B. 10 C. 11 D. 12
答案：C
解析：叶子数 = 度为2的节点数 + 1 = 11。

八、易错点汇总

1. 递归忘记终止条件：if (root == nullptr) return; 不能漏。
2. 前序、中序、后序顺序混淆：前序根左右，中序左根右，后序左右根。
3. 层序遍历忘记判空：队列为空时停止，根为空直接返回。
4. 已知前序+后序尝试还原：前序+后序不能唯一确定二叉树，这是高频错误。
5. 顺序存储下标关系记错：根从1开始，左孩子 2i，右孩子 2i+1；根从0开始，左孩子 2i+1，右孩子 2i+2。
6. 完全二叉树与满二叉树混淆：完全二叉树最后一层可以不满，但集中在左侧。
7. 遍历序列中节点值重复：如果节点值有重复，前序+中序也不能唯一还原（题目通常保证值唯一）。
8. 递归深度过大导致栈溢出：树退化为链表时，递归深度为 n，可能栈溢出。
9. 忘记释放内存：new 创建的节点需要 delete，虽然考试不强制，但好习惯。
10. 中序非递归遍历时忘记 cur = cur->right：会导致死循环。

九、速查表

需求	写法	关键注意
节点定义	struct Node { int val; Node *left, *right; };	左右指针初始为 nullptr
前序遍历	根 → 左 → 右	cout 在递归前
中序遍历	左 → 根 → 右	cout 在递归中间
后序遍历	左 → 右 → 根	cout 在递归后
层序遍历	队列，根入队，出队访问，左右入队	用 queue<Node*>
求深度	1 + max(depth(left), depth(right))	空返回 0
求节点数	1 + count(left) + count(right)
求叶子数	左右都空返回 1，否则递归求和	注意空节点
前序+中序还原	前序定根，中序分左右	递归构建
中序+后序还原	后序定根，中序分左右
前序+后序	不能唯一还原	选择题考点
顺序存储	根从1：左 2i，右 2i+1	根从0：左 2i+1，右 2i+2
完全二叉树	最后一层集中在左侧	叶子数 = 度2节点数 + 1

十、总结

二叉树基础与遍历是 GESP 六级数据结构模块的核心内容。

1. 二叉树每个节点最多两个孩子，左右次序不能颠倒。
2. 前序根左右，中序左根右，后序左右根，层序用队列逐层访问。
3. 递归遍历必须写终止条件 if (root == nullptr) return;。
4. 层序遍历用队列，根入队，出队访问，左右孩子入队。
5. 已知前序+中序，或中序+后序，可以唯一还原二叉树。
6. 前序+后序不能唯一还原二叉树，这是高频选择题考点。
7. 完全二叉树顺序存储：根从1开始，左孩子 2i，右孩子 2i+1。
8. 二叉树性质：叶子数 = 度为2的节点数 + 1。
9. 遍历可用于求深度、节点数、叶子数、复制树、释放树。
10. 多练“遍历序列推导”“层序遍历代码”“前序+中序还原”“完全二叉树性质”四类题。

复习建议：先把四种遍历的递归代码和层序遍历代码写熟；再重点练习“已知前序+中序求后序”类程序阅读题；然后掌握二叉树深度、节点数、叶子数的递归求法；最后复习完全二叉树和顺序存储的下标关系。考试中先判断题目考的是遍历顺序、遍历应用还是性质计算，再套用对应知识作答。