YatDS

Appearance

二叉树的遍历 ​

二叉树的遍历是指按照某种顺序访问树中的每个节点，使每个节点被访问且仅被访问一次。遍历是二叉树各种操作的基础。

遍历的基本概念 ​

遍历的意义 ​

二叉树的遍历是树结构中最基本、最重要的操作之一。通过遍历，我们可以：

  • 获取树中所有节点的信息
  • 查找特定节点
  • 对树进行各种统计和计算
  • 为其他操作（如插入、删除）提供基础

遍历的分类 ​

二叉树的遍历方式主要分为两类：

类别遍历方式特点
深度优先遍历前序、中序、后序遍历按深度方向访问节点
广度优先遍历层序遍历按层次方向访问节点

深度优先遍历（DFS） ​

深度优先遍历（Depth-First Search, DFS）是一种沿着树的深度方向遍历的方式，先访问根节点，再递归访问子树。

深度优先遍历

前序遍历（Preorder Traversal） ​

前序遍历的访问顺序：根节点 → 左子树 → 右子树

算法步骤：

  1. 访问根节点
  2. 前序遍历左子树
  3. 前序遍历右子树

前序遍历

递归实现：

cpp
void preorder_traversal(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    result.push_back(root->data);         // 访问根节点
    preorder_traversal(root->left.get(), result);   // 遍历左子树
    preorder_traversal(root->right.get(), result);  // 遍历右子树
}

非递归实现（使用栈）：

cpp
void preorder_traversal_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    std::stack<const BinaryTreeNode<int>*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        auto node = stk.top();
        stk.pop();
        result.push_back(node->data);
        
        if (node->right) stk.push(node->right.get());
        if (node->left) stk.push(node->left.get());
    }
}

应用场景：

  • 复制一棵二叉树
  • 计算表达式树的值
  • 查找特定节点

中序遍历（Inorder Traversal） ​

中序遍历的访问顺序：左子树 → 根节点 → 右子树

算法步骤：

  1. 中序遍历左子树
  2. 访问根节点
  3. 中序遍历右子树

中序遍历

递归实现：

cpp
void inorder_traversal(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    inorder_traversal(root->left.get(), result);    // 遍历左子树
    result.push_back(root->data);         // 访问根节点
    inorder_traversal(root->right.get(), result);   // 遍历右子树
}

非递归实现（使用栈）：

cpp
void inorder_traversal_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    std::stack<const BinaryTreeNode<int>*> stk;
    auto current = root;
    
    while (current || !stk.empty()) {
        while (current) {
            stk.push(current);
            current = current->left.get();
        }
        
        current = stk.top();
        stk.pop();
        result.push_back(current->data);
        
        current = current->right.get();
    }
}

应用场景：

  • 二叉搜索树的中序遍历结果是有序序列
  • 表达式树的中序遍历可以得到表达式的 infix 形式

后序遍历（Postorder Traversal） ​

后序遍历的访问顺序：左子树 → 右子树 → 根节点

算法步骤：

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根节点

后序遍历

递归实现：

cpp
void postorder_traversal(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    postorder_traversal(root->left.get(), result);   // 遍历左子树
    postorder_traversal(root->right.get(), result);  // 遍历右子树
    result.push_back(root->data);          // 访问根节点
}

非递归实现（使用栈）：

cpp
void postorder_traversal_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    std::stack<const BinaryTreeNode<int>*> stk;
    std::stack<const BinaryTreeNode<int>*> output;
    stk.push(root);
    
    while (!stk.empty()) {
        auto node = stk.top();
        stk.pop();
        output.push(node);
        
        if (node->left) stk.push(node->left.get());
        if (node->right) stk.push(node->right.get());
    }
    
    while (!output.empty()) {
        result.push_back(output.top()->data);
        output.pop();
    }
}

应用场景：

  • 计算树的深度
  • 删除二叉树（先删除子节点再删除根节点）
  • 计算表达式树的值

广度优先遍历（BFS） ​

广度优先遍历（Breadth-First Search, BFS），也称层序遍历，按照树的层次从上到下、从左到右依次访问节点。

广度优先遍历

层序遍历（Level Order Traversal） ​

算法步骤：

  1. 将根节点入队
  2. 循环执行：出队一个节点并访问，将其左右子节点入队
  3. 直到队列为空

实现代码：

cpp
void level_order_traversal(const BinaryTreeNode<int> *root, std::vector<int> &result) {
    if (root == nullptr) return;
    
    std::queue<const BinaryTreeNode<int>*> q;
    q.push(root);
    
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        result.push_back(node->data);
        
        if (node->left) q.push(node->left.get());
        if (node->right) q.push(node->right.get());
    }
}

应用场景：

  • 查找某一层的所有节点
  • 计算树的高度
  • 判断是否为完全二叉树

遍历序列的性质 ​

唯一确定一棵二叉树 ​

给定序列能否唯一确定二叉树
前序 + 中序✓ 可以唯一确定
后序 + 中序✓ 可以唯一确定
前序 + 后序✗ 不能唯一确定（缺少中序信息）

示例：给定前序序列 [A, B, D, E, C, F, G] 和中序序列 [D, B, E, A, F, C, G]，可以唯一重建二叉树：

  1. 前序第一个元素 A 是根节点
  2. 中序中 A 左边的 [D, B, E] 是左子树，右边的 [F, C, G] 是右子树
  3. 递归处理左右子树

森林与二叉树遍历的关系 ​

对于森林和对应二叉树的遍历序列：

森林遍历对应二叉树遍历
前序遍历前序遍历
后序遍历中序遍历

Baseline 任务: 二叉树的遍历 ​

任务概述 ​

本模块包含以下任务，学生需要按照难度逐步完成：

任务编号任务名称难度必须完成
T1前序遍历（递归）⭐ 基础✓
T2中序遍历（递归）⭐ 基础✓
T3后序遍历（递归）⭐ 基础✓
T4层序遍历⭐ 基础✓
T5前序遍历（非递归）⭐⭐ 进阶○
T6中序遍历（非递归）⭐⭐ 进阶○
T7后序遍历（非递归）⭐⭐ 进阶○
T8重建二叉树⭐⭐ 进阶✓
T9判断对称二叉树⭐⭐ 进阶○
T10遍历输出某一层⭐⭐ 进阶○
T11计算树的最大宽度⭐⭐⭐ 挑战○
T12Morris 遍历⭐⭐⭐ 挑战○

⭐ 基础任务 ​

T1: 前序遍历（递归） ​

任务描述：使用递归方式实现二叉树的前序遍历。

函数签名：

cpp
void preorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

遍历顺序：根节点 → 左子树 → 右子树

输入要求：

  • root：二叉树的根节点指针
  • result：用于存储遍历结果的向量（输出参数）

输出要求：

  • 将遍历结果按顺序存入 result 向量

示例：

cpp
// 输入二叉树:
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: {1, 2, 4, 5, 3, 6, 7}

提示：

  • 先访问当前节点，再递归访问左子树，最后递归访问右子树
  • 注意处理空指针情况

T2: 中序遍历（递归） ​

任务描述：使用递归方式实现二叉树的中序遍历。

函数签名：

cpp
void inorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

遍历顺序：左子树 → 根节点 → 右子树

示例：

cpp
// 输入二叉树:
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: {4, 2, 5, 1, 6, 3, 7}

应用场景：对于二叉搜索树，中序遍历结果为有序序列。

T3: 后序遍历（递归） ​

任务描述：使用递归方式实现二叉树的后序遍历。

函数签名：

cpp
void postorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

遍历顺序：左子树 → 右子树 → 根节点

示例：

cpp
// 输入二叉树:
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: {4, 5, 2, 6, 7, 3, 1}

应用场景：用于删除二叉树（先删除子节点再删除根节点）。

T4: 层序遍历 ​

任务描述：实现二叉树的层序遍历（广度优先遍历）。

函数签名：

cpp
void level_order(const BinaryTreeNode<int> *root, std::vector<int> &result);

遍历顺序：按层次从上到下、从左到右依次访问节点。

示例：

cpp
// 输入二叉树:
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: {1, 2, 3, 4, 5, 6, 7}

提示：

  • 使用队列（std::queue）辅助实现
  • 根节点入队，循环处理：出队访问，左右子节点入队

⭐⭐ 进阶任务 ​

T5: 前序遍历（非递归） ​

任务描述：使用栈实现前序遍历的迭代版本。

函数签名：

cpp
void preorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

提示：

  • 使用 std::stack 存储待访问节点
  • 入栈顺序：右孩子先入栈，左孩子后入栈

T6: 中序遍历（非递归） ​

任务描述：使用栈实现中序遍历的迭代版本。

函数签名：

cpp
void inorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

提示：

  • 先将所有左孩子入栈
  • 出栈访问后，转向右孩子

T7: 后序遍历（非递归） ​

任务描述：使用栈实现后序遍历的迭代版本。

函数签名：

cpp
void postorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

提示：

  • 可以使用双栈方法
  • 或使用单栈+前驱节点标记法

T8: 重建二叉树 ​

任务描述：根据前序遍历和中序遍历序列重建二叉树。

函数签名：

cpp
std::unique_ptr<BinaryTreeNode<char>> build_tree_from_pre_in(
    const std::vector<char> &preorder,
    const std::vector<char> &inorder);

输入要求：

  • preorder：前序遍历序列
  • inorder：中序遍历序列

输出要求：

  • 返回重建后的二叉树根节点

示例：

cpp
// 输入: preorder = {A, B, D, E, C, F, G}
//       inorder  = {D, B, E, A, F, C, G}
// 输出: 重建如下二叉树
//        A
//       / \\
//      B   C
//     / \ / \\
//    D  E F  G

算法步骤：

  1. 前序序列第一个元素为根节点
  2. 在中序序列中找到根节点位置，左边为左子树，右边为右子树
  3. 递归处理左右子树

T9: 判断对称二叉树 ​

任务描述：判断一棵二叉树是否对称（左右镜像相同）。

函数签名：

cpp
bool is_symmetric(const BinaryTreeNode<int> *root);

示例： 对称二叉树

cpp
// 输入: 对称二叉树
//       1
//      / \\
//     2   2
//    / \ / \\
//   3  4 4  3
// 输出: true

提示：

  • 比较左子树的左孩子与右子树的右孩子
  • 比较左子树的右孩子与右子树的左孩子

T10: 遍历输出某一层 ​

任务描述：输出二叉树第 k 层的所有节点。

函数签名：

cpp
void print_level(const BinaryTreeNode<int> *root, int k, std::vector<int> &result);

输入要求：

  • root：二叉树的根节点
  • k：层数（第 1 层为根节点层）

示例：

cpp
// 输入: k=3
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: {4, 5, 6, 7}

⭐⭐⭐ 挑战任务 ​

T11: 计算树的最大宽度 ​

任务描述：计算二叉树的最大宽度（节点数最多的一层的节点数）。

函数签名：

cpp
int max_width(const BinaryTreeNode<int> *root);

提示：

  • 使用层序遍历记录每层节点数
  • 或使用带编号的层序遍历

T12: Morris 遍历 ​

任务描述：实现空间复杂度为 O(1) 的 Morris 中序遍历。

函数签名：

cpp
void morris_inorder(BinaryTreeNode<int> *root, std::vector<int> &result);

提示：

  • 利用空闲指针临时建立线索
  • 不使用栈，只使用常量空间

数据结构定义 ​

本项目中使用以下数据结构（定义在 traversal.h）：

cpp
template <typename T>
struct BinaryTreeNode {
    T data;
    std::unique_ptr<BinaryTreeNode> left;
    std::unique_ptr<BinaryTreeNode> right;
};

实现要求 ​

必须实现的遍历函数 ​

cpp
// 前序遍历（递归）
void preorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

// 中序遍历（递归）
void inorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

// 后序遍历（递归）
void postorder_recursive(const BinaryTreeNode<int> *root, std::vector<int> &result);

// 层序遍历
void level_order(const BinaryTreeNode<int> *root, std::vector<int> &result);

可选实现的遍历函数 ​

cpp
// 前序遍历（非递归）
void preorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

// 中序遍历（非递归）
void inorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

// 后序遍历（非递归）
void postorder_iterative(const BinaryTreeNode<int> *root, std::vector<int> &result);

示例代码 ​

cpp
#include "traversal.h"

int main() {
    // 创建一棵二叉树
    auto root = BinaryTreeNode<int>::get_new_node(1);
    root->left = BinaryTreeNode<int>::get_new_node(2);
    root->right = BinaryTreeNode<int>::get_new_node(3);
    root->left->left = BinaryTreeNode<int>::get_new_node(4);
    root->left->right = BinaryTreeNode<int>::get_new_node(5);
    root->right->left = BinaryTreeNode<int>::get_new_node(6);
    root->right->right = BinaryTreeNode<int>::get_new_node(7);

    std::vector<int> result;

    // 前序遍历: 1 2 4 5 3 6 7
    preorder_recursive(root.get(), result);
    std::cout << "前序遍历: ";
    for (int val : result) std::cout << val << " ";
    std::cout << std::endl;

    result.clear();
    // 中序遍历: 4 2 5 1 6 3 7
    inorder_recursive(root.get(), result);
    std::cout << "中序遍历: ";
    for (int val : result) std::cout << val << " ";
    std::cout << std::endl;

    result.clear();
    // 后序遍历: 4 5 2 6 7 3 1
    postorder_recursive(root.get(), result);
    std::cout << "后序遍历: ";
    for (int val : result) std::cout << val << " ";
    std::cout << std::endl;

    result.clear();
    // 层序遍历: 1 2 3 4 5 6 7
    level_order(root.get(), result);
    std::cout << "层序遍历: ";
    for (int val : result) std::cout << val << " ";
    std::cout << std::endl;

    return 0;
}

提交要求 ​

  1. 所有任务代码需放在 Tree/Baseline/traversal 目录下
  2. 每个任务需编写对应的测试文件
  3. 基础任务（T1-T4）必须全部完成
  4. 任务 T8（重建二叉树）必须完成
  5. 进阶任务（T5-T7, T9-T10）至少完成 2 个
  6. 挑战任务（T11-T12）可选完成

测试验证 ​

建议编写以下测试用例验证代码正确性：

cpp
// 创建标准测试二叉树
auto create_test_tree() {
    auto root = BinaryTreeNode<int>::get_new_node(1);
    root->left = BinaryTreeNode<int>::get_new_node(2);
    root->right = BinaryTreeNode<int>::get_new_node(3);
    root->left->left = BinaryTreeNode<int>::get_new_node(4);
    root->left->right = BinaryTreeNode<int>::get_new_node(5);
    root->right->left = BinaryTreeNode<int>::get_new_node(6);
    root->right->right = BinaryTreeNode<int>::get_new_node(7);
    return root;
}

// 测试函数
void test_traversal() {
    auto root = create_test_tree();
    std::vector<int> result;

    preorder_recursive(root.get(), result);
    assert(result == std::vector<int>{1, 2, 4, 5, 3, 6, 7});

    result.clear();
    inorder_recursive(root.get(), result);
    assert(result == std::vector<int>{4, 2, 5, 1, 6, 3, 7});

    result.clear();
    postorder_recursive(root.get(), result);
    assert(result == std::vector<int>{4, 5, 2, 6, 7, 3, 1});

    result.clear();
    level_order(root.get(), result);
    assert(result == std::vector<int>{1, 2, 3, 4, 5, 6, 7});
}

参考资源 ​