这是一个完整的 C++ 数据生成器。它整合了随机树生成算法和标准答案逻辑。程序运行后会自动生成 1.in/out 到 10.in/out 共 10 组测试数据。

数据生成器设计思路

1. 覆盖边界：包含空树 ($N=0$)、单节点 ($N=1$)、完全二叉树、左斜链、右斜链、随机深树。
2. 树结构生成算法：
   • 随机树：为了确保生成的是合法的树且不形成环，我们让节点 $i$ 的父节点必须在 $[0, i-1]$ 范围内随机选择。
   • 链状树：节点 $i$ 的左/右孩子固定为 $i+1$。
   • 完全二叉树：利用数组下标性质 $2i+1$ 和 $2i+2$ 建立连接。
3. 性能与安全性：
   • 使用 std::queue 的迭代写法（BFS）生成答案，防止递归过深导致生成器崩溃。
   • 使用 std::ofstream 输出文件，确保文件读写效率。
   • $N=2000$ 的数据规模，单文件大小约 30KB，总数据量远小于 2MB。

C++ 完整生成器代码 (C++14 标准)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>
#include <string>
#include <ctime>
#include <random>

using namespace std;

// 定义树节点结构
struct Node {
    int val;
    int left, right;
    Node() : val(0), left(-1), right(-1) {}
};

// --- 标准答案逻辑 (用于生成 .out 文件) ---
void solve(int n, const vector<Node>& tree, const string& out_file) {
    ofstream fout(out_file);
    if (n <= 0) return;

    vector<vector<int>> res;
    queue<int> q;
    q.push(0); // 假设 0 始终是根

    while (!q.empty()) {
        int sz = q.size();
        vector<int> current_level;
        for (int i = 0; i < sz; ++i) {
            int curr = q.front();
            q.pop();
            current_level.push_back(tree[curr].val);
            if (tree[curr].left != -1) q.push(tree[curr].left);
            if (tree[curr].right != -1) q.push(tree[curr].right);
        }
        res.push_back(current_level);
    }

    reverse(res.begin(), res.end());

    for (const auto& row : res) {
        for (int i = 0; i < row.size(); ++i) {
            fout << row[i] << (i == (int)row.size() - 1 ? "" : " ");
        }
        fout << "\n";
    }
}

// --- 数据生成逻辑 ---
void generate_test_case(int case_num, int n, string type) {
    string in_name = to_string(case_num) + ".in";
    string out_name = to_string(case_num) + ".out";
    ofstream fin(in_name);

    vector<Node> tree(n);
    mt19937 rng(time(0) + case_num);
    uniform_int_distribution<int> val_dist(-1000, 1000);

    // 1. 生成节点值
    for (int i = 0; i < n; ++i) tree[i].val = val_dist(rng);

    // 2. 根据类型生成树结构
    if (type == "left_chain" && n > 1) {
        for (int i = 0; i < n - 1; ++i) tree[i].left = i + 1;
    } 
    else if (type == "right_chain" && n > 1) {
        for (int i = 0; i < n - 1; ++i) tree[i].right = i + 1;
    }
    else if (type == "full" && n > 1) {
        for (int i = 0; i < n; ++i) {
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            if (l < n) tree[i].left = l;
            if (r < n) tree[i].right = r;
        }
    }
    else if (type == "random" && n > 1) {
        // 保证是树：每个节点 i (i>0) 随机挂载到 [0, i-1] 某个有空位的节点上
        vector<int> free_slots;
        free_slots.push_back(0); // 根节点初始有空位
        for (int i = 1; i < n; ++i) {
            uniform_int_distribution<int> p_dist(0, (int)free_slots.size() - 1);
            int p_idx = p_dist(rng);
            int parent = free_slots[p_idx];
            
            if (tree[parent].left == -1) {
                tree[parent].left = i;
            } else {
                tree[parent].right = i;
                // 父节点已满，从空位列表中移除
                free_slots.erase(free_slots.begin() + p_idx);
            }
            free_slots.push_back(i); // 新加入的节点有空位
        }
    }

    // 3. 写入输入文件
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << tree[i].val << " " << tree[i].left << " " << tree[i].right << "\n";
    }

    // 4. 调用解题代码生成输出文件
    solve(n, tree, out_name);
    
    cout << "Test Case " << case_num << " [" << type << "] generated. N=" << n << endl;
}

int main() {
    // 覆盖不同规模和形态
    generate_test_case(1, 0, "empty");       // 边界：空树
    generate_test_case(2, 1, "single");      // 边界：单节点
    generate_test_case(3, 10, "full");       // 小规模：完全树
    generate_test_case(4, 100, "left_chain");// 中规模：左斜链（最大深度）
    generate_test_case(5, 100, "right_chain");// 中规模：右斜链
    generate_test_case(6, 500, "random");    // 中大规模：随机树
    generate_test_case(7, 1000, "full");     // 大规模：平衡树
    generate_test_case(8, 2000, "random");   // 最大规模：随机
    generate_test_case(9, 2000, "left_chain");// 最大规模：极端深度
    generate_test_case(10, 2000, "random");  // 最大规模：随机

    return 0;
}

数据点说明表 (用于 OJ 配置)

复杂度分析与建议

1. 时间复杂度：
   • 生成器：随机树生成使用 vector::erase 略慢（$O(N^2)$），但由于 $N=2000$ 且树结构随机，实际运行瞬间完成。
   • 解题器：标准 BFS 复杂度为 $O(N)$。
2. 空间复杂度：
   • 存储整棵树需要 $O(N)$。$2000$ 个节点消耗内存极小。
3. 优化建议：
   • 在 OJ 评测时，如果 $N$ 增加到 $10^5$ 以上，建议将生成随机树中的 vector::erase 改为交换末尾元素后 pop_back，可将生成时间降至 $O(N)$。
   • 对于此题规模，当前的生成逻辑已足够高效且安全。

你好，同学。在 NOI 竞赛中，处理树形结构的代码不仅要求逻辑正确，更要求对内存开销和执行效率有深刻理解。

下面我将为你展示这道题（自底向上层序遍历）从初学者写法到竞赛优化写法的演进过程。为了符合 NOI 竞赛习惯，我将题目背景设定为：给定 $N$ 个节点及每个节点的左右孩子编号，输出结果。

版本一：基础 BFS + 插入头部（简单但低效）

这个版本最符合直觉：每次得到一层的结果，就把它插到动态数组的开头。

易错点： v.insert(v.begin(), ...) 在 std::vector 中是 $O(N)$ 操作。如果树很深，会导致频繁的内存搬移。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// NOI 竞赛中常用数组模拟树，此处为了通用性使用结构体
struct Node {
    int val;
    int left, right; // 存储左右孩子的编号，-1表示空
} tree[2005];

int main() {
    int n, root_idx;
    if (!(cin >> n)) return 0; // 处理空树或输入结束

    // 假设输入：n 个节点的值，以及每个节点的左右孩子编号
    for (int i = 0; i < n; i++) {
        cin >> tree[i].val >> tree[i].left >> tree[i].right;
    }

    // 假设根节点编号为 0
    root_idx = 0;
    if (n == 0) return 0;

    vector<vector<int>> result;
    queue<int> q;
    q.push(root_idx);

    while (!q.empty()) {
        int size = q.size();
        vector<int> current_level;
        for (int i = 0; i < size; i++) {
            int curr = q.front();
            q.pop();
            current_level.push_back(tree[curr].val);

            if (tree[curr].left != -1) q.push(tree[curr].left);
            if (tree[curr].right != -1) q.push(tree[curr].right);
        }
        // 关键点：每次插入到 vector 头部，导致后面所有元素移动
        result.insert(result.begin(), current_level); 
    }

    // 输出结果
    for (const auto& level : result) {
        for (int j = 0; j < level.size(); j++) {
            cout << level[j] << (j == level.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

• 时间复杂度：$O(N + H \cdot N)$，$H$ 为树高。因为 insert(begin) 需要移动已有的 $O(N)$ 个元素。
• 空间复杂度：$O(N)$。

版本二：标准 BFS + 全局反转（竞赛推荐版）

这是竞赛中最常用的写法。先按正常顺序存储，最后通过 std::reverse 一次性翻转。std::reverse 对 vector<vector<int>> 的操作本质上是交换内部指针，效率极高。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node {
    int val;
    int left, right;
} tree[2005];

int main() {
    ios::sync_with_stdio(false); // 优化 1: 竞赛中常用，加速 cin/cout
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 0; i < n; i++) {
        cin >> tree[i].val >> tree[i].left >> tree[i].right;
    }

    if (n == 0) return 0;

    vector<vector<int>> res;
    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int level_size = q.size();
        vector<int> curr_level;
        // 预分配空间防止多次扩容
        curr_level.reserve(level_size); 

        for (int i = 0; i < level_size; i++) {
            int t = q.front();
            q.pop();
            curr_level.push_back(tree[t].val);
            if (tree[t].left != -1) q.push(tree[t].left);
            if (tree[t].right != -1) q.push(tree[t].right);
        }
        res.push_back(curr_level);
    }

    // 优化 2: 翻转二维向量。在 C++14 中，这是 O(H) 的指针交换操作
    reverse(res.begin(), res.end());

    for (const auto& row : res) {
        for (int i = 0; i < row.size(); i++) {
            cout << row[i] << (i == row.size() - 1 ? "" : " ");
        }
        cout << "\n"; // 优化 3: 用 \n 代替 endl，避免频繁刷新缓冲区
    }

    return 0;
}

• 时间复杂度：$O(N)$。每个节点遍历一次，reverse 操作复杂度远小于 $N$。
• 空间复杂度：$O(N)$。

版本三：DFS + 深度索引（最优复杂度，省去队列开销）

在某些极限内存限制的题目中，可以用递归 DFS 代替 BFS。我们通过记录当前深度 dep，直接将节点放入对应的 res[dep] 中。

注意： 因为结果是自底向上的，但 DFS 是自顶向下的，我们依然需要最后翻转。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 2005;
struct Node {
    int val, l, r;
} tree[MAXN];

vector<vector<int>> res;

// 启发式思考：DFS 顺序虽然不是层序，但如果我知道当前深度，就能归类
void dfs(int u, int dep) {
    if (u == -1) return;

    // 如果当前深度超过了 res 的大小，说明第一次进入这一层
    if (dep >= res.size()) {
        res.push_back(vector<int>());
    }

    res[dep].push_back(tree[u].val);
    dfs(tree[u].l, dep + 1);
    dfs(tree[u].r, dep + 1);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> tree[i].val >> tree[i].l >> tree[i].r;

    if (n > 0) {
        dfs(0, 0);
        reverse(res.begin(), res.end());
    }

    for (auto &v : res) {
        for (int i = 0; i < v.size(); i++)
            cout << v[i] << (i == v.size() - 1 ? "" : " ");
        cout << endl;
    }
    return 0;
}

复杂度分析与优化建议

1. 时间复杂度思考过程

• 遍历过程：无论是 BFS 还是 DFS，每个节点必须访问且仅访问一次。复杂度底线是 $\Omega(N)$。
• 层级处理：
  • insert(0)：导致 $O(N^2)$ 隐患（最坏情况退化为链表）。
  • push_back + reverse：$O(N) + O(H) = O(N)$。
  • 结论：在 NOI 中，永远优先选择后处理（翻转）而不是前处理（插入）。

2. 空间复杂度分析

• 队列空间：最宽的一层。对于完全二叉树，最后一层节点数为 $N/2$，即 $O(N)$。
• 递归栈空间：DFS 的递归深度等于树高 $H$。最坏情况（链表）为 $O(N)$。
• 存储空间：存储所有节点值，必然是 $O(N)$。

3. 竞赛向优化建议

• 内存池：如果题目给定 $N$ 很大且频繁创建 TreeNode 指针，建议改用 struct tree[MAXN] 静态数组，避免 new 带来的时间消耗和内存碎片。
• IO 优化：使用 scanf/printf 或 cin.tie(0)。在处理多行大量数据输出时，endl 会强制刷新缓冲区，速度比 \n 慢很多。
• 预分配：如果你已经通过一次 DFS 知道了树的最大深度 $H$，可以先 res.resize(H)，这样在填充数据时效率更高。

总结：在 NOI 读题时，看到“层序”想到 BFS，看到“逆序输出”想到 Stack 或 std::reverse。这就是本题的解题秘籍。