GESP 6级《树与二叉树》的考纲要求是什么？

GESP 6级《树与二叉树》是 CCF 编程能力等级认证（C++）的官方考点，考频★★★、难度★★★。本页严格对照官方考纲逐条拆解要求，配有通俗讲解、必背重点、易错陷阱与考场真题，帮助中小学生零基础系统掌握。

GESP 6级《树与二叉树》怎么学？有哪些易错点？

学习《树与二叉树》建议四步：①读「通俗讲解」理解概念；②记「核心必背重点」；③避开「高频易错陷阱」；④用「真题演练」检验。本站为该考点提供 ASCII 图解、例题与历年真题，循序渐进即可通关 GESP 6级。

📌 树与二叉树

所属等级：GESP 6级｜难度：★★★ ｜关键词：二叉树、前中后序遍历、建树、性质

📝 考纲要求

理解“树”与“二叉树”的概念、区别与基本术语（根、叶子、深度、度）；
掌握二叉树的三种遍历：前序、中序、后序，能手动模拟与写递归；
了解二叉树的性质（满二叉树、完全二叉树、结点数量关系）；
能用数组或指针结构建立简单的二叉树并完成遍历。

📖 通俗讲解

💡 一句话理解二叉树就像一棵倒着长的树：最上面是根结点，每个结点最多分两个“叉”（左孩子、右孩子）。遍历就是按固定顺序“逛”遍所有结点。

三种遍历的区别只在“根”什么时候被访问：

前序（根左右）：先访问根，再左子树，再右子树；
中序（左根右）：先左子树，再根，再右子树；
后序（左右根）：先左子树，再右子树，最后根。

下面用递归实现三种遍历。每个结点存一个值 val，以及左、右孩子指针。

🖼️ 图解

二叉树结构：最上是根，每个结点最多两个孩子（左、右）
            [1]  ← 根
           /   \
         [2]   [3]
         / \     \
       [4] [5]   [6]
   前序(根左右): 1 2 4 5 3 6
   中序(左根右): 4 2 5 1 3 6
   后序(左右根): 4 5 2 6 3 1

C++

#include <iostream>
using namespace std;

// 二叉树结点结构：值 + 左右孩子指针
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 前序遍历：根 -> 左 -> 右
void preorder(Node* root) {
    if (root == nullptr) return;   // 空树直接返回
    cout << root->val << " ";        // 先访问根
    preorder(root->left);          // 再走左子树
    preorder(root->right);         // 最后走右子树
}

// 中序遍历：左 -> 根 -> 右
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);           // 先走左子树
    cout << root->val << " ";        // 再访问根
    inorder(root->right);          // 最后走右子树
}

// 后序遍历：左 -> 右 -> 根
void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);         // 先走左子树
    postorder(root->right);        // 再走右子树
    cout << root->val << " ";        // 最后访问根
}

int main() {
    // 手动建一棵简单的树：   1
    //                       / \
    //                      2   3
    //                     /
    //                    4
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);

    cout << "前序: "; preorder(root); cout << endl;
    cout << "中序: "; inorder(root);  cout << endl;
    cout << "后序: "; postorder(root);cout << endl;
    return 0;
}

输出前序: 1 2 4 3 中序: 4 2 1 3 后序: 4 2 3 1

📌 重要性质（送分题）

💡 性质速记

第 i 层（根算第 1 层）最多有 2^(i-1) 个结点；
深度为 h 的二叉树最多有 2^h - 1 个结点（满二叉树）；
在任意二叉树中，叶子结点数 = 度为 2 的结点数 + 1；
有 n 个结点的完全二叉树，最后一个非叶子结点下标为 n/2（从 1 开始编号）。

🔵 核心必背重点

✅ 必背

三种遍历的顺序：前序“根左右”、中序“左根右”、后序“左右根”；
递归模板固定：先写“空则返回”，再按顺序排根与左右递归；
性质公式：第 i 层 ≤ 2^(i-1)；满二叉树总节点 ≤ 2^h-1；叶子 = 度为2节点 + 1；
完全二叉树用数组存：下标 1 起，左孩子 2i、右孩子 2i+1，父结点 i/2。

🔑

记忆口诀：“根在头是前序，根在中是中序，根在尾是后序；左永远比右先走。”

🔴 考试拉分难点

⚠️ 难点

由遍历还原树：已知“前序 + 中序”或“后序 + 中序”可唯一确定一棵二叉树（前序/后序定根，中序分左右）；单给前序和后序不能确定。
“用数组建完全二叉树再遍历”：输入按层序给，下标映射要仔细，避免越界。
递归边界：忘记 if (root == nullptr) return; 会导致访问空指针崩溃。

🟡 高频易错陷阱

🚫 扣分坑点

把三种遍历顺序背混，尤其“中序”把根放中间；
数组从 0 编号却用 2i、2i+1（应 +1 偏移或使用 1 起编号）；
建树时 new Node(0) 后忘了连左右指针，遍历只输出根；
用 bits/stdc++.h 或非标准库（考试禁用），只用 iostream。

🧪 例题演练

例题 1（基础题）：数组存完全二叉树并中序遍历

题目：输入一个完全二叉树的层序结点值（n 个），下标从 1 开始存放在数组 a 中，输出中序遍历结果。

C++

#include <iostream>
using namespace std;

const int MAXN = 105;
int a[MAXN];      // 1 起编号的数组，存放结点值
int n;            // 结点总数

// 中序遍历：当前结点下标为 idx
void inorder(int idx) {
    if (idx > n) return;        // 下标越界说明没有该结点
    inorder(idx * 2);          // 先访问左孩子（下标 2*idx）
    cout << a[idx] << " ";        // 再访问根
    inorder(idx * 2 + 1);      // 最后访问右孩子（下标 2*idx+1）
}

int main() {
    cin >> n;                   // 输入结点个数
    for (int i = 1; i <= n; i++) {
        cin >> a[i];            // 按层序读入结点值
    }
    inorder(1);                 // 从根结点（下标1）开始
    cout << endl;
    return 0;
}

输入 / 输出7 1 2 3 4 5 6 7 4 2 5 1 6 3 7

例题 2（模拟真题）：已知前序+中序重建并后序输出

题目：给定一棵二叉树的前序遍历与中序遍历，输出它的后序遍历结果。

C++

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

string pre, in;   // 前序串、中序串

// 在 in[l2..r2] 区间内找字符 c 的位置
int findPos(char c, int l2, int r2) {
    for (int i = l2; i <= r2; i++) {
        if (in[i] == c) return i;
    }
    return -1;
}

// 重建并直接输出后序：pl/pr 为前序区间，il/ir 为中序区间
void build(int pl, int pr, int il, int ir) {
    if (pl > pr) return;                 // 区间为空返回
    char root = pre[pl];                 // 前序第一个字符就是根
    int pos = findPos(root, il, ir);     // 根在中序中的位置
    int leftSize = pos - il;             // 左子树的大小
    // 先递归左子树（后序：左在前）
    build(pl + 1, pl + leftSize, il, pos - 1);
    // 再递归右子树
    build(pl + leftSize + 1, pr, pos + 1, ir);
    cout << root;                        // 最后输出根（后序）
}

int main() {
    cin >> pre >> in;                    // 读入前序、中序
    int len = pre.size();
    build(0, len - 1, 0, len - 1);       // 从完整区间开始
    cout << endl;
    return 0;
}

输入 / 输出ABDCE DBAEC DBECA

🚫 错误示范 cout << root; build(...); —— 把输出根放在递归前，就变成“前序”而非“后序”。后序必须等左右子树都递归完再输出根。