二叉树和森林的转换

森林是若干棵树的集合。通过左孩子右兄弟表示法，任意森林都可以唯一地映射为一棵二叉树。
森林的前序遍历等于对应二叉树的前序遍历，森林的后序遍历等于对应二叉树的中序遍历。

所有依赖代码位于 Tree\Baseline\forest 目录下。数据结构定义在 forest.h。

森林的定义

树和森林

树（Tree）是一种非线性数据结构，由节点和边组成，每个节点可以有零个或多个子节点。一棵树有且仅有一个根节点。

森林（Forest）则是若干棵互不相交的树的集合。森林中的每棵树都是一个独立的树结构，树根之间没有边相连。为便于处理，通常将森林定义为一个以各树根为元素的线性表。

森林示意图

森林与树的区别：
- 一棵树只有一个 根结点，而森林可以有多个 根结点（每棵树一个）。
- 森林可以看作是多个树的并集，树是森林的一个特例（森林中只有一棵树）。
森林的深度：森林中所有树的最大高度（从根到最远叶结点的路径长度）。

二叉树

二叉树（Binary Tree）是每个节点最多有两个子节点（左孩子和右孩子）的树结构。由于二叉树的节点度数固定，它的存储和操作比一般树更为简单，因此在计算机科学中有着广泛的应用。

左孩子右兄弟表示法

左孩子右兄弟（Left-Child Right-Sibling, LCRS）表示法是一种将任意树（或森林）转换为二叉树的标准方法。其核心思想是：

对于树中的每个节点，将其第一个孩子作为它在二叉树中的左孩子。
将其其余孩子依次作为前一个兄弟节点的右孩子（即右兄弟链）。

树转化为二叉树示意图

对于森林，先转换第一棵树，其根作为二叉树的根；随后将森林中其余的树依次作为前一个树根的右孩子连接。

这种转换是一一对应的，也就是说，给定一棵二叉树，我们也可以唯一地还原出原始的森林。

森林转二叉树示意图

Baseline 任务: 二叉树与森林的转换

数据结构定义

本项目中使用以下数据结构来表示森林和二叉树（定义在 forest.h）：

一般树节点（ForestNode）

cpp

template <typename T>
struct ForestNode {
    T data;
    std::vector<std::unique_ptr<ForestNode>> children;

    ForestNode(const T &data);
    ForestNode(T &&data);
    static std::unique_ptr<ForestNode> get_new_node(const T &data);
    static std::unique_ptr<ForestNode> get_new_node(T &&data);
};

ForestNode 使用 std::vector 存储子节点，支持任意数量的孩子（可变度数）。所有权通过 std::unique_ptr 管理。

森林（Forest）

cpp

template <typename T>
using Forest = std::vector<std::unique_ptr<ForestNode<T>>>;

森林就是一棵棵树的根节点组成的向量。

二叉树节点（BinaryTreeNode）

cpp

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

    BinaryTreeNode(const T &data);
    BinaryTreeNode(T &&data);
    static std::unique_ptr<BinaryTreeNode> get_new_node(const T &data);
    static std::unique_ptr<BinaryTreeNode> get_new_node(T &&data);
};

BinaryTreeNode 固定有 left 和 right 两个子节点指针，与一般二叉树节点定义一致。

森林转二叉树

函数签名：

cpp

template <typename T>
std::unique_ptr<BinaryTreeNode<T>>
forest_to_binary_tree(const Forest<T> &forest);

算法步骤：

若森林为空，返回空指针。
对森林中的每棵树，递归转换每个子树：
- 创建一个新的 BinaryTreeNode，数据与原节点相同。
- 将原节点的第一个孩子递归转换为新节点的左孩子。
- 将原节点的后续孩子依次链接为左孩子的右兄弟链（即每个兄弟作为前一个的 right）。
森林中第一棵树的根成为结果二叉树的根。
后续树的根依次作为前一树根的右孩子。

二叉树转森林

函数签名：

cpp

template <typename T>
Forest<T>
binary_tree_to_forest(const std::unique_ptr<BinaryTreeNode<T>> &root);

算法步骤（forest_to_binary_tree 的逆过程）：

若二叉树根为空，返回空森林。
沿二叉树的右链向下遍历——右链上的每个节点都是森林中一棵树的根。
对每个根节点，递归还原一般树：
- 创建一个新的 ForestNode，数据与原节点相同。
- 沿该节点的 left->right 链向下遍历——链上的每个节点都是该 ForestNode 的一个孩子。

树的遍历

对于一个给定的树，通常有以下两种遍历方式：

先根遍历（类似于二叉树的前序遍历）：
- 访问树的根结点。
- 递归地 先根遍历 根的每一棵子树。
后根遍历（类似于二叉树的后序遍历）：
- 递归地 后根遍历 根的每一棵子树。
- 访问树的根结点。

注意树是没有 中根遍历 的，除非这棵树是二叉树。

观察可以得到如下结论：

树的 先根遍历 和其对应的二叉树的 先序遍历 相同
树的 后根遍历 和其对应的二叉树的 中序遍历 相同

森林的遍历

森林的遍历按顺序逐棵进行：

前序遍历：对于森林中的每一棵树，先访问根节点，再依次递归访问每个子树。
后序遍历：对于森林中的每一棵树，先依次递归访问每个子树，最后访问根节点。
中根遍历（普通的树构成的森林是不存在中序遍历的，这里的中序遍历指代的是二叉树森林）：依次 中根遍历 森林中的每一棵二叉树。

关键不变式：森林的前序遍历 = 二叉树的前序遍历，森林的后序遍历 = 二叉树的中序遍历。

Baseline 任务: 二叉树与森林的转换

任务概述

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

任务编号	任务名称	难度	必须完成
T1	森林转二叉树	⭐⭐ 进阶	✓
T2	二叉树转森林	⭐⭐ 进阶	✓
T3	森林前序遍历	⭐ 基础	✓
T4	森林后序遍历	⭐ 基础	✓
T5	验证遍历对应关系	⭐⭐ 进阶	✓
T6	往返转换一致性验证	⭐⭐ 进阶	○

⭐ 基础任务

T3: 森林前序遍历

任务描述：实现森林的前序遍历。

函数签名：

cpp

template <typename T>
void forest_preorder(const Forest<T> &forest, std::vector<T> &result);

遍历规则：

对于森林中的每一棵树，先访问根节点，再依次递归访问每个子树

示例：

cpp

// 输入森林（两棵树）:
// Tree 1:     Tree 2:
//     A            E
//    /|\          / \
//   B C D        F   G
// 输出: {A, B, C, D, E, F, G}

T4: 森林后序遍历

任务描述：实现森林的后序遍历。

函数签名：

cpp

template <typename T>
void forest_postorder(const Forest<T> &forest, std::vector<T> &result);

遍历规则：

对于森林中的每一棵树，先依次递归访问每个子树，最后访问根节点

示例：

cpp

// 输入森林（两棵树）:
// Tree 1:     Tree 2:
//     A            E
//    /|\          / \
//   B C D        F   G
// 输出: {B, C, D, A, F, G, E}

⭐⭐ 进阶任务

T1: 森林转二叉树

任务描述：将森林转换为二叉树（左孩子右兄弟表示法）。

函数签名：

cpp

template <typename T>
std::unique_ptr<BinaryTreeNode<T>> forest_to_binary_tree(const Forest<T> &forest);

转换规则：

若森林为空，返回空指针
森林中第一棵树的根成为结果二叉树的根
将原节点的第一个孩子递归转换为新节点的左孩子
将原节点的后续孩子依次链接为左孩子的右兄弟链
后续树的根依次作为前一树根的右孩子

T2: 二叉树转森林

任务描述：将二叉树还原为森林。

函数签名：

cpp

template <typename T>
Forest<T> binary_tree_to_forest(const std::unique_ptr<BinaryTreeNode<T>> &root);

转换规则（T1 的逆过程）：

若二叉树根为空，返回空森林
沿二叉树的右链向下遍历——右链上的每个节点都是森林中一棵树的根
对每个根节点，沿该节点的 left->right 链还原为一般树的孩子

T5: 验证遍历对应关系

任务描述：验证森林遍历与二叉树遍历的对应关系。

理论依据：

森林的前序遍历 = 二叉树的前序遍历
森林的后序遍历 = 二叉树的中序遍历

任务要求：

编写测试函数验证上述对应关系
解释为什么这种对应关系成立

提示：

左孩子右兄弟表示法中，原节点的第一个孩子成为左孩子，其余孩子形成右兄弟链
前序遍历先访问根，再访问第一个孩子（左），再访问兄弟（右链）
后序遍历先访问孩子，再访问根；对应二叉树中先访问左（第一个孩子），再访问右（兄弟链），最后访问根

T6: 往返转换一致性验证

任务描述：验证森林转二叉树、再转回森林的一致性（round-trip）。

任务要求：

设计测试用例验证 Forest → Binary Tree → Forest 转换后结果与原始一致
覆盖边界情况：空森林、单棵树、多棵树、不同深度等

提交要求

学生需要在 forest-impl.hpp 中实现所有任务，提交材料需包含：

四个核心函数的完整实现代码
对左孩子右兄弟表示法原理的解释
对森林与二叉树转换正确性的分析
自行设计测试用例，验证转换的正确性和往返转换的一致性

测试样例

点击展开：Baseline 测试样例与预期输出

以 forest-demo.cpp 中的示例森林为例（两棵树：A 有孩子 B、C、D；E 有孩子 F、G）：

text

Tree 1:     Tree 2:
    A            E
   /|\          / \
  B C D        F   G

预期输出

text

=== Original Forest ===
Forest preorder:  A B C D E F G
Forest postorder: B C D A F G E

=== Binary Tree (from forest) ===
Binary preorder:  A B C D E F G
Binary inorder:   B C D A F G E

=== Recovered Forest ===
Forest preorder:  A B C D E F G
Forest postorder: B C D A F G E

可以看到，森林的前序遍历 = 二叉树的前序遍历，森林的后序遍历 = 二叉树的中序遍历。往返转换后森林遍历结果与原始一致，验证了转换的正确性。

二叉树和森林的转换 ​

森林的定义 ​

树和森林 ​

二叉树 ​

左孩子右兄弟表示法 ​

Baseline 任务: 二叉树与森林的转换 ​

数据结构定义 ​

一般树节点（ForestNode） ​

森林（Forest） ​

二叉树节点（BinaryTreeNode） ​

森林转二叉树 ​

二叉树转森林 ​

树的遍历 ​

森林的遍历 ​

Baseline 任务: 二叉树与森林的转换 ​

任务概述 ​

⭐ 基础任务 ​

T3: 森林前序遍历 ​

T4: 森林后序遍历 ​

⭐⭐ 进阶任务 ​

T1: 森林转二叉树 ​

T2: 二叉树转森林 ​

T5: 验证遍历对应关系 ​

T6: 往返转换一致性验证 ​

提交要求 ​

测试样例 ​

预期输出 ​

二叉树和森林的转换

森林的定义

树和森林

二叉树

左孩子右兄弟表示法

Baseline 任务: 二叉树与森林的转换

数据结构定义

一般树节点（ForestNode）

森林（Forest）

二叉树节点（BinaryTreeNode）

森林转二叉树

二叉树转森林

树的遍历

森林的遍历

Baseline 任务: 二叉树与森林的转换

任务概述

⭐ 基础任务

T3: 森林前序遍历

T4: 森林后序遍历

⭐⭐ 进阶任务

T1: 森林转二叉树

T2: 二叉树转森林

T5: 验证遍历对应关系

T6: 往返转换一致性验证

提交要求

测试样例

预期输出