第2章树的基本概念与遍历

🎯 本章学习目标

通过本章的学习，你将能够：

理解树的基本概念：掌握根、叶、度、深度、高度等核心术语
掌握二叉树定义：理解二叉树的特点，知道度最多为2、左右子树有序
熟悉特殊二叉树：掌握满二叉树、完全二叉树的定义和性质
掌握四种遍历：熟练掌握前序、中序、后序、层序遍历的顺序
实现递归遍历：能用递归实现前/中/后序遍历
实现层序遍历：能用队列实现层序遍历（BFS思想）
还原二叉树：给定前序+中序或后序+中序，能还原二叉树结构
应用完全二叉树性质：能用公式计算节点编号、深度、叶子数等
分析遍历序列：能快速分析遍历代码的输出结果
应对真题题型：能解决选择、判断、代码填空等各类树的题目

🗺️ 本章知识图谱

树的基本概念与遍历
├── 树的基础
│   ├── 定义（递归定义）
│   ├── 核心术语
│   │   ├── 根、叶、父/子节点
│   │   ├── 度（节点的度 / 树的度）
│   │   ├── 深度（从根往下数）
│   │   └── 高度（从叶往上数）
│   └── 性质：n个节点有n-1条边
├── 二叉树
│   ├── 定义：度≤2，左右有序
│   ├── 特殊二叉树
│   │   ├── 满二叉树（每层都满）
│   │   └── 完全二叉树（前k-1层满，最后一层左连续）
│   ├── 重要性质
│   │   ├── 第i层最多 2^(i-1) 个节点
│   │   ├── 深度k最多 2^k-1 个节点
│   │   ├── 叶子数 n0 = n2 + 1
│   │   └── 完全二叉树深度 = ⌊log₂n⌋ + 1
│   └── 存储结构
│       ├── 链式存储（二叉链表）
│       └── 数组存储（完全二叉树）
├── 四种遍历
│   ├── 前序遍历（根左右）
│   ├── 中序遍历（左根右）
│   ├── 后序遍历（左右根）
│   └── 层序遍历（队列实现）
├── 还原二叉树
│   ├── 前序 + 中序 → 唯一确定
│   ├── 后序 + 中序 → 唯一确定
│   ├── 前序 + 后序 → 不唯一
│   └── 方法：前/后找根，中序分左右
└── 非递归遍历（了解）
    ├── 栈实现前序
    ├── 栈实现中序
    └── 栈实现后序

一、树的基本概念

1.1 什么是树？

树（Tree）是 n（n≥0）个节点的有限集合。当 n=0 时称为空树。在任意一棵非空树中：

有且仅有一个特定的节点称为根（Root）
其余节点可分为若干互不相交的子集，每个子集本身又是一棵树，称为根的子树（Subtree）

易错点： 树是递归定义的结构，子树之间互不相交——这意味着每个节点有且仅有一个父节点（根节点除外）。

1.2 核心术语速查

术语	定义	图示记忆
节点（Node）	树中的每个元素	圆圈中的一个值
根（Root）	没有父节点的唯一顶层节点	最顶部的节点
叶节点（Leaf）	度为 0 的节点，没有子节点	最底层的节点
父节点（Parent）	某节点的上层直接连接节点	A→B，A是B的父
子节点（Child）	某节点的下层直接连接节点	A→B，B是A的子
兄弟（Sibling）	同一个父节点的子节点互称兄弟	B和C共父A
祖先（Ancestor）	从根到某节点路径上的所有节点	根→...→父→自身
度（Degree）	一个节点拥有的子树数量	有3个子节点则度为3
树的度	树中节点度的最大值	—
深度/高度	节点深度：根到该节点的层数（根深度为1）；树的高度 = 最大深度	根在第1层
层次（Level）	根为第1层，其子节点为第2层，以此类推	—

高频考点 ⚠️： "深度"和"高度"的区分。节点深度从根往下数（根=1），节点高度从叶往上数（叶=1）。考试中通常问的是节点的深度和树的高度（深度）。

易错点 ⚠️： 关于"度"——节点的度 = 子节点个数。一棵有 10 个节点的二叉树，其度最大为 2（因为二叉树每个节点最多 2 个子节点），但树的度指的是所有节点度的最大值。

二、二叉树

2.1 二叉树定义

二叉树（Binary Tree）是 n（n≥0）个节点的有限集合，满足：

每个节点最多有两棵子树（即度不超过 2）
子树有左右之分，次序不能颠倒（有序树）

关键区别： 普通树的子树无序，而二叉树严格区分左子树和右子树。即使某节点只有一棵子树，也要区分是左还是右。

2.2 两种特殊二叉树

满二叉树（Full Binary Tree）

一棵深度为 k 的二叉树，如果每一层的节点数都达到最大值（即第 i 层有 2^(i-1) 个节点），则称为满二叉树。

深度为 k 的满二叉树共有 2^k - 1 个节点
所有叶节点都在最底层
每个非叶节点的度都为 2

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

完全二叉树（Complete Binary Tree）

深度为 k、有 n 个节点的二叉树，当且仅当：

第 1 到 k-1 层都是满的
第 k 层的节点从左到右连续排列

高频考点 ⚠️： 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。考试中常考判断题！

2.3 二叉树的核心性质

性质 1： 第 i 层最多有 2^(i-1) 个节点（i≥1）

性质 2： 深度为 k 的二叉树最多有 2^k - 1 个节点

性质 3： 对任一二叉树，若叶节点数为 n₀，度为 2 的节点数为 n₂，则 n₀ = n₂ + 1

这个公式极其重要！推导思路：总节点数 n = n₀ + n₁ + n₂，总分支数 = n - 1 = n₁ + 2×n₂，联立得 n₀ = n₂ + 1。

性质 4： n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1

性质 5： 完全二叉树中，对编号为 i 的节点（从 1 开始编号）：

父节点编号：i / 2（i>1 时）
左孩子编号：2i（若 2i ≤ n）
右孩子编号：2i + 1（若 2i+1 ≤ n）

考试常见考法： 给定 n=500 个节点的完全二叉树，求深度？答：⌊log₂500⌋ + 1 = ⌊8.97⌋ + 1 = 8 + 1 = 9。

三、二叉树的存储结构

3.1 顺序存储（数组存储）

完全二叉树最适合用数组存储。对编号 i 的节点：

cpp

// 数组下标从1开始，tree[i]存储第i个节点的值
int tree[1005];
int n; // 节点总数

// 获取节点i的父节点
int parent(int i) {
    return i / 2;
}

// 获取节点i的左孩子
int leftChild(int i) {
    if (2 * i <= n) return 2 * i;
    return -1; // 无左孩子
}

// 获取节点i的右孩子
int rightChild(int i) {
    if (2 * i + 1 <= n) return 2 * i + 1;
    return -1; // 无右孩子
}

注意： 普通二叉树用数组存储会浪费大量空间，因此一般二叉树更常用链式存储。

3.2 链式存储（二叉链表）

cpp

struct TreeNode {
    int val;           // 节点值
    TreeNode* left;    // 左孩子指针
    TreeNode* right;   // 右孩子指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 手动构建一棵二叉树示例
//       1
//      / \
//     2   3
//    / \
//   4   5
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1);
    root->left  = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left  = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

3.3 左孩子右兄弟表示法（树 → 二叉树）

将普通树转为二叉树存储的经典方法：每个节点的第一个孩子作为左孩子，下一个兄弟作为右孩子。

cpp

struct TreeNode {
    int val;
    TreeNode* firstChild;   // 第一个孩子（左指针）
    TreeNode* nextSibling;  // 下一个兄弟（右指针）
    TreeNode(int x) : val(x), firstChild(nullptr), nextSibling(nullptr) {}
};

考试常见考法： 给你一棵普通树，画出对应的"左孩子右兄弟"二叉树表示。

四、二叉树的遍历

4.1 深度优先遍历（DFS）—— 递归实现

二叉树遍历是最核心的考点，必须烂熟于心！

以这棵树为例：

遍历方式	访问顺序	记忆口诀
前序遍历（先序）	1 2 4 5 3 6	根左右
中序遍历	4 2 5 1 3 6	左根右
后序遍历	4 5 2 6 3 1	左右根

完整代码模板

cpp

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历：根 -> 左 -> 右
void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";   // 访问根
    preorder(root->left);        // 遍历左子树
    preorder(root->right);       // 遍历右子树
}

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

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

int main() {
    // 构建示例树
    TreeNode* root = new TreeNode(1);
    root->left  = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left  = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    cout << "前序遍历: "; preorder(root);  cout << endl;
    cout << "中序遍历: "; inorder(root);   cout << endl;
    cout << "后序遍历: "; postorder(root); cout << endl;

    return 0;
}
// 输出：
// 前序遍历: 1 2 4 5 3 6
// 中序遍历: 4 2 5 1 3 6
// 后序遍历: 4 5 2 6 3 1

4.2 层次遍历（BFS）

使用队列实现，从根节点开始，逐层从左到右访问。

cpp

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

// 层次遍历（BFS）
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->val << " ";

        if (curr->left)  q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left  = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left  = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    cout << "层次遍历: ";
    levelOrder(root);
    cout << endl;
    // 输出: 层次遍历: 1 2 3 4 5 6
    return 0;
}

高频考点 ⚠️： BFS 使用队列（先进先出），DFS 使用栈或递归（后进先出）。考试中可能让你判断"某遍历序列是 BFS 还是 DFS 的结果"。

五、由遍历序列还原二叉树 ⭐⭐⭐

这是GESP六级的高频压轴考点！

5.1 核心原理

前序 + 中序 → 可唯一确定一棵二叉树 ✅
后序 + 中序 → 可唯一确定一棵二叉树 ✅
前序 + 后序 → 不能唯一确定 ❌

5.2 前序 + 中序 → 还原二叉树

思路：

前序序列的第一个元素是根节点
在中序序列中找到根节点，根左边是左子树的中序，右边是右子树的中序
递归处理左子树和右子树

示例： 前序 [1, 2, 4, 5, 3, 6]，中序 [4, 2, 5, 1, 3, 6]

第1步：前序首元素 1 是根
第2步：中序中 1 左边 [4,2,5] 是左子树（3个节点），右边 [3,6] 是右子树（2个节点）
第3步：左子树的前序 = [2,4,5]，中序 = [4,2,5] → 递归
第4步：右子树的前序 = [3,6]，中序 = [3,6] → 递归

完整代码模板

cpp

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 根据前序和中序还原二叉树
TreeNode* buildFromPreIn(vector<int>& preorder, vector<int>& inorder,
                          int preL, int preR, int inL, int inR) {
    if (preL > preR) return nullptr;

    // 前序第一个元素是根
    int rootVal = preorder[preL];
    TreeNode* root = new TreeNode(rootVal);

    // 在中序中找到根的位置
    int rootIdx = inL;
    while (inorder[rootIdx] != rootVal) rootIdx++;

    // 计算左子树节点数
    int leftSize = rootIdx - inL;

    // 递归构建左子树和右子树
    root->left  = buildFromPreIn(preorder, inorder,
                                  preL + 1, preL + leftSize,
                                  inL, rootIdx - 1);
    root->right = buildFromPreIn(preorder, inorder,
                                  preL + leftSize + 1, preR,
                                  rootIdx + 1, inR);
    return root;
}

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3, 6};
    vector<int> inorder  = {4, 2, 5, 1, 3, 6};
    int n = preorder.size();

    TreeNode* root = buildFromPreIn(preorder, inorder, 0, n-1, 0, n-1);
    cout << "后序遍历验证: ";
    // 后序输出: 4 5 2 6 3 1
    // （调用postorder即可）
    return 0;
}

5.3 后序 + 中序 → 还原二叉树

思路类似，只是后序的最后一个元素是根节点。

cpp

TreeNode* buildFromPostIn(vector<int>& postorder, vector<int>& inorder,
                           int postL, int postR, int inL, int inR) {
    if (postL > postR) return nullptr;

    int rootVal = postorder[postR]; // 后序最后一个是根
    TreeNode* root = new TreeNode(rootVal);

    int rootIdx = inL;
    while (inorder[rootIdx] != rootVal) rootIdx++;

    int leftSize = rootIdx - inL;

    root->left  = buildFromPostIn(postorder, inorder,
                                   postL, postL + leftSize - 1,
                                   inL, rootIdx - 1);
    root->right = buildFromPostIn(postorder, inorder,
                                   postL + leftSize, postR - 1,
                                   rootIdx + 1, inR);
    return root;
}

易错点 ⚠️： 考试中最常见的陷阱——给你前序和后序让你还原树，注意这是不能唯一确定的！一定要包含中序序列。

考试常见考法： 给一棵树的前序和中序序列，要求你画出二叉树或写出后序序列。手算即可，不需要写代码。关键是熟练运用"前序定根、中序分左右"的方法。

六、完全二叉树的性质总结

性质	公式	备注
第 i 层最多节点数	2^(i-1)	i≥1
深度为 k 最多节点数	2^k - 1	即满二叉树
n 个节点的完全二叉树深度	⌊log₂n⌋ + 1	也写作 ⌈log₂(n+1)⌉
叶节点数 n₀ 与度为2节点数 n₂	n₀ = n₂ + 1	适用于所有二叉树
节点 i 的父节点	⌊i/2⌋	i>1
节点 i 的左孩子	2i	若 2i≤n
节点 i 的右孩子	2i+1	若 2i+1≤n

必记公式 ⚠️： n 个节点的完全二叉树，叶节点数 = ⌈n/2⌉，度为1的节点数 = 0 或 1（n为奇数时0，n为偶数时1）。

七、📝 实战练习

练习题 1（单选题）

题目： 一棵二叉树的前序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，则该二叉树的后序遍历序列为（）

A. CEFDBHGA B. CEFDHGAB C. CEFDBGAH D. CFEDBHGA

🔑 点击查看答案与解析

答案： A 解析： 第1步：前序首元素 A 是根。中序中 A 在第5位，左子树中序 CBEDF（5节点），右子树中序 GH（2节点）。

第2步：左子树前序 BCDEF，中序 CBEDF。B 是左子树根。中序中 B 左边 C（1节点），右边 EDF（3节点）。

第3步：B 的右子树前序 DEF，中序 EDF。D 是根，左为 E，右为 F。

第4步：右子树前序 GH，中序 GH。G 是根，右为 H。

还原的二叉树：

          A
        /   \
       B     G
      / \     \
     C   D     H
        / \
       E   F

后序遍历：左→右→根 → CEFDBHGA，选 A。

---

练习题 2（单选题）

题目： 一棵完全二叉树有 500 个节点，则该树的深度为（），其中叶节点有（）个。

🔑 点击查看答案与解析

答案： 深度为 9，叶节点有 250 个。

解析：

深度 = ⌊log₂500⌋ + 1 计算：2⁸ = 256，2⁹ = 512，所以 ⌊log₂500⌋ = 8，深度 = 8 + 1 = 9 验证：前 8 层共 2⁸ - 1 = 255 个节点，第 9 层有 500 - 255 = 245 个节点（≤ 2⁸ = 256 ✓）
500 是偶数，所以度为 1 的节点有 1 个。
n₀ = n₂ + 1，n₀ + n₁ + n₂ = 500，n₁ = 1
所以 n₀ + n₂ = 499，n₀ = n₂ + 1
解得 n₀ = 250，n₂ = 249

叶节点数 = 250 个。

---

练习题 3（单选题）

题目： 以下关于二叉树的说法，正确的有（）

① 满二叉树一定是完全二叉树 ② 完全二叉树一定是满二叉树 ③ 已知前序和后序遍历序列，可以唯一确定一棵二叉树 ④ 已知前序和中序遍历序列，可以唯一确定一棵二叉树 ⑤ 一棵有 124 个节点的二叉树，度为 0 的节点最多有 63 个

A. ①③ B. ①④ C. ②④ D. ①④⑤

🔑 点击查看答案与解析

答案： B

解析：

① 正确 ✅ 满二叉树每层都满，自然满足完全二叉树条件。
② 错误 ❌ 反例：最后一层缺右边节点的二叉树是完全二叉树但不是满二叉树。
③ 错误 ❌ 前序+后序无法唯一确定（必须有中序参与）。
④ 正确 ✅ 前序定根，中序分左右，递归可唯一确定。
⑤ 错误 ❌ n₀ = n₂ + 1，n₀ + n₁ + n₂ = 124。要使 n₀ 最大，需 n₁ 最小=0，则 2n₂ + 1 = 124，n₂ = 61.5（非整数）。所以 n₁ 至少为 1，n₀ = (124-1+1)/2 = 62，最多 62 个叶节点，不是 63。

选 B（①④）。

---

练习题 4（单选题）

题目： 一棵有 100 个节点的树，总共有多少条边？（）

A. 99
B. 100
C. 101
D. 200

🔑 点击查看答案与解析

答案： A

解析： 树的基本性质：n 个节点的树有 n-1 条边。

为什么？因为除了根节点外，每个节点都有且仅有一条边连接到它的父节点，所以边数 = 节点数 - 1。

100 个节点 → 99 条边，选 A。

💡 记忆技巧：树 = 节点 - 1 条边。这是树的标志性性质，也是判断一个图是不是树的重要依据。

---

练习题 5（单选题）

题目： 在一棵二叉树中，度为 2 的节点有 5 个，则叶子节点（度为 0 的节点）有多少个？（）

A. 4
B. 5
C. 6
D. 7

🔑 点击查看答案与解析

答案： C

解析： 二叉树重要性质：n₀ = n₂ + 1（叶子数 = 度为2的节点数 + 1）

已知 n₂ = 5，所以 n₀ = 5 + 1 = 6

选 C。

🔥 高频考点：这个公式非常重要！推导思路：总边数 = n₁ + 2n₂（度为1的贡献1条边，度为2的贡献2条），同时总边数 = n - 1 = n₀ + n₁ + n₂ - 1，两式相等化简即可。

---

练习题 6（判断题）

题目： 完全二叉树一定是满二叉树。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 正好说反了！

满二叉树：每一层都填满了节点，深度为 k 时有 2^k - 1 个节点
完全二叉树：前 k-1 层是满的，最后一层的节点从左到右连续排列

所以：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

🍎 生活比喻：满二叉树像一个完整的三角形蛋糕，每一层都铺满了；完全二叉树像有人从右边咬了一口——最后一层右边缺了几块，但左边还是连续的。

---

练习题 7（单选题）

题目： 二叉树的层序遍历（层次遍历）通常用什么数据结构实现？（）

A. 栈
B. 队列
C. 数组
D. 链表

🔑 点击查看答案与解析

答案： B

解析： 层序遍历就是按层次从上到下、每层从左到右访问节点。这是典型的广度优先搜索（BFS），用队列实现。

基本思路：

根节点入队
出队一个节点，访问它
如果有左孩子，左孩子入队
如果有右孩子，右孩子入队
重复 2-4 直到队列为空

选 B。

💡 对比记忆：
前/中/后序遍历 → 深度优先 DFS → 栈/递归
层序遍历 → 广度优先 BFS → 队列

---

练习题 8（编程题）

题目： 给定一棵二叉树的前序遍历和中序遍历，请编写程序输出后序遍历。

输入：两行，第一行前序遍历字符串，第二行中序遍历字符串（节点用大写字母表示）
输出：后序遍历字符串

样例输入：

ABCDE
BADCE

样例输出：

BDECA

🔑 点击查看答案与解析

答案：

cpp

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

// 根据前序和中序求后序
void postOrder(string pre, string in) {
    if (pre.empty()) return;
    
    char root = pre[0];  // 前序第一个是根
    int pos = in.find(root);  // 在中序中找到根的位置
    
    // 递归左子树
    postOrder(pre.substr(1, pos), in.substr(0, pos));
    // 递归右子树
    postOrder(pre.substr(pos + 1), in.substr(pos + 1));
    // 后序：左右根，最后输出根
    cout << root;
}

int main() {
    string pre, in;
    cin >> pre >> in;
    postOrder(pre, in);
    cout << endl;
    return 0;
}

解析： 递归思路：

前序第一个字符就是根节点
在中序中找到根节点，左边是左子树，右边是右子树
递归处理左子树
递归处理右子树
最后输出根节点（后序 = 左 → 右 → 根）

🔥 这是树的经典编程题，核心就是"前/后找根，中序分左右"。

---

八、📊 考点总结表

考点	重要程度	出题形式	易错点
树的基本术语（根、叶、度、深度）	⭐⭐⭐	选择/填空	深度和高度搞混
树的性质：n节点n-1条边	⭐⭐⭐	选择/判断	公式记错
二叉树定义（度≤2，左右有序）	⭐⭐⭐⭐	选择/判断	左右子树有顺序
满二叉树 vs 完全二叉树	⭐⭐⭐⭐	选择/判断	谁是谁的子集搞反
二叉树性质：n₀ = n₂ + 1	⭐⭐⭐⭐⭐	选择/计算	高频考点，公式记牢
第i层最多 2^(i-1) 个节点	⭐⭐⭐⭐	选择/计算	注意是第i层不是深度k
深度k最多 2^k - 1 个节点	⭐⭐⭐⭐	选择/计算	和上面的区分开
三种递归遍历（前/中/后序）	⭐⭐⭐⭐⭐	选择/程序阅读/代码填空	遍历顺序记混
层序遍历（队列实现）	⭐⭐⭐⭐	选择/程序阅读	用队列不是栈
前序+中序还原二叉树	⭐⭐⭐⭐⭐	选择/程序填空（压轴）	找根、分左右的过程
后序+中序还原二叉树	⭐⭐⭐⭐⭐	选择/程序填空	后序最后一个是根
完全二叉树深度公式	⭐⭐⭐⭐	选择/计算	⌊log₂n⌋ + 1

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       树的基本概念与遍历 · 必背速记卡       │
├─────────────────────────────────────────────┤
│  1. 树：n个节点，n-1条边                   │
│  2. 二叉树：度≤2，左右子树有序             │
│  3. 叶子数 n0 = n2 + 1（度2节点数+1）      │
│  4. 第i层最多有 2^(i-1) 个节点             │
│  5. 深度k的二叉树最多 2^k - 1 个节点       │
│  6. 前序遍历：根 → 左 → 右                 │
│  7. 中序遍历：左 → 根 → 右                 │
│  8. 后序遍历：左 → 右 → 根                 │
│  9. 层序遍历：从上到下，每层从左到右       │
│ 10. 层序遍历用队列，DFS遍历用栈/递归       │
│ 11. 还原二叉树：前/后找根，中序分左右      │
│ 12. 前序第一个是根，后序最后一个是根       │
│ 13. 只有前序+后序不能唯一确定二叉树        │
│ 14. 满二叉树一定是完全二叉树，反之不成立    │
│ 15. 完全二叉树深度 = floor(log2 n) + 1     │
└─────────────────────────────────────────────┘

第2章 树的基本概念与遍历 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、树的基本概念 ​

1.1 什么是树？ ​

1.2 核心术语速查 ​

二、二叉树 ​

2.1 二叉树定义 ​

2.2 两种特殊二叉树 ​

满二叉树（Full Binary Tree） ​

完全二叉树（Complete Binary Tree） ​

2.3 二叉树的核心性质 ​

三、二叉树的存储结构 ​

3.1 顺序存储（数组存储） ​

3.2 链式存储（二叉链表） ​

3.3 左孩子右兄弟表示法（树 → 二叉树） ​

四、二叉树的遍历 ​

4.1 深度优先遍历（DFS）—— 递归实现 ​

完整代码模板 ​

4.2 层次遍历（BFS） ​

五、由遍历序列还原二叉树 ⭐⭐⭐ ​

5.1 核心原理 ​

5.2 前序 + 中序 → 还原二叉树 ​

完整代码模板 ​

5.3 后序 + 中序 → 还原二叉树 ​

六、完全二叉树的性质总结 ​

七、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（单选题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（判断题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

八、📊 考点总结表 ​

⭐ 必背速记卡 ​

第2章树的基本概念与遍历

🎯 本章学习目标

🗺️ 本章知识图谱

一、树的基本概念

1.1 什么是树？

1.2 核心术语速查

二、二叉树

2.1 二叉树定义

2.2 两种特殊二叉树

满二叉树（Full Binary Tree）

完全二叉树（Complete Binary Tree）

2.3 二叉树的核心性质

三、二叉树的存储结构

3.1 顺序存储（数组存储）

3.2 链式存储（二叉链表）

3.3 左孩子右兄弟表示法（树 → 二叉树）

四、二叉树的遍历

4.1 深度优先遍历（DFS）—— 递归实现

完整代码模板

4.2 层次遍历（BFS）

五、由遍历序列还原二叉树 ⭐⭐⭐

5.1 核心原理

5.2 前序 + 中序 → 还原二叉树

完整代码模板

5.3 后序 + 中序 → 还原二叉树

六、完全二叉树的性质总结

七、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（单选题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（判断题）

练习题 7（单选题）

练习题 8（编程题）

八、📊 考点总结表

⭐ 必背速记卡