为了方便你快速创建 OJ (Online Judge) 评测数据，我为你编写了一个基于 C++14 标准的二叉树中序遍历数据生成器。

该生成器能够自动生成 10 组测试点，涵盖了从空树到最大规模随机树的各种情况。为了确保生成的 .out 文件绝对准确且在大规模数据下不爆栈，生成器内部使用了显式栈的迭代算法来产生标准答案。

数据生成器代码 (gen_inorder.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>
#include <numeric>

using namespace std;

// 节点结构体，符合题目输入格式
struct Node {
    int val;
    int l, r;
};

/**
 * 核心逻辑：迭代法（栈）生成中序遍历序列
 * 优点：非递归，不会因为树高过大（如链状树）导致生成器崩溃
 */
vector<int> getInorder(int n, const vector<Node>& tree) {
    if (n <= 0) return {};
    vector<int> res;
    stack<int> s;
    int curr = 1; // 根节点固定为 1
    
    while (curr != -1 || !s.empty()) {
        while (curr != -1) {
            s.push(curr);
            curr = tree[curr].l;
        }
        curr = s.top();
        s.pop();
        res.push_back(tree[curr].val);
        curr = tree[curr].r;
    }
    return res;
}

// 写入输入文件 (.in)
void writeIn(int n, const vector<Node>& tree, string filename) {
    ofstream fout(filename);
    fout << n << endl;
    for (int i = 1; i <= n; ++i) {
        fout << tree[i].val << " " << tree[i].l << " " << tree[i].r << endl;
    }
    fout.close();
}

// 写入输出文件 (.out)
void writeOut(const vector<int>& res, string filename) {
    ofstream fout(filename);
    for (int i = 0; i < (int)res.size(); ++i) {
        fout << res[i] << (i == (int)res.size() - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

int main() {
    // 随机数发生器初始化
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> valDist(-100, 100);

    for (int t = 1; t <= 10; ++t) {
        int n = 0;
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";

        // 确定节点数 n
        if (t == 1) n = 0;       // 边界：空树
        else if (t == 2) n = 1;  // 边界：单节点
        else if (t == 3) n = 3;  // 基础树
        else if (t == 4) n = 50; // 左斜树
        else if (t == 5) n = 50; // 右斜树
        else if (t == 6) n = 63; // 满二叉树
        else n = 100;            // 随机树

        vector<Node> tree(n + 1, {0, -1, -1});
        for (int i = 1; i <= n; ++i) tree[i].val = valDist(rng);

        // 构造树形态
        if (t == 3) {
            tree[1].l = 2; tree[1].r = 3;
        } else if (t == 4) { // 左斜：1->2->3...
            for (int i = 1; i < n; ++i) tree[i].l = i + 1;
        } else if (t == 5) { // 右斜：1->2->3...
            for (int i = 1; i < n; ++i) tree[i].r = i + 1;
        } else if (t == 6) { // 满二叉树：i 的孩子是 2i 和 2i+1
            for (int i = 1; i <= n / 2; ++i) {
                tree[i].l = (2 * i <= n) ? 2 * i : -1;
                tree[i].r = (2 * i + 1 <= n) ? 2 * i + 1 : -1;
            }
        } else if (t >= 7) { 
            // 随机合法二叉树生成逻辑
            // 每一个新节点 i 随机挂载到已有节点的一个空槽位上
            vector<int> slots; 
            slots.push_back(1); // 根节点
            vector<int> free_count(n + 1, 2); 

            for (int i = 2; i <= n; ++i) {
                uniform_int_distribution<int> pick(0, (int)slots.size() - 1);
                int idx = pick(rng);
                int parent = slots[idx];

                if (tree[parent].l == -1 && tree[parent].r == -1) {
                    if (rng() % 2) tree[parent].l = i; else tree[parent].r = i;
                } else if (tree[parent].l == -1) tree[parent].l = i;
                else tree[parent].r = i;

                free_count[parent]--;
                if (free_count[parent] == 0) {
                    slots.erase(slots.begin() + idx);
                }
                slots.push_back(i);
            }
        }

        writeIn(n, tree, in_name);
        writeOut(getInorder(n, tree), out_name);
        cout << "Generated Test Case " << t << " (n=" << n << ")" << endl;
    }

    return 0;
}

测试点规划说明 (Test Cases Specification)

生成器设计细节 (符合 NOI 规范)

1. 非递归求精 (Safety)：
   • 在生成标准答案（.out）时，生成器使用了显式栈模拟的迭代法。即使后期你将 $n$ 修改为 $10^5$，生成器本身也不会出现栈溢出错误，保证了评测数据的可靠性。
2. 文件大小极致优化 (Small Files)：
   • 在 $n=100$ 且节点值为整数的情况下，每个 .in 文件大约只有 1.5KB 左右。即使生成 10 个测试点，总数据量也不超过 20KB。这极大地降低了数据在本地及评测系统中的存储压力。
3. 合法性保证 (Correctness)：
   • 树生成逻辑：采用了“空槽位挂载法”。新节点只能连接到已有节点且出度小于 2 的位置。这保证了生成的结构一定是单根、连通、无环的合法二叉树。
4. 随机性与健壮性 (Robustness)：
   • 使用了 std::mt19937 高性能随机数生成器。
   • 不存在除法操作，消除了 Divide by Zero 风险。
   • 使用了 vector 动态内存，消除了硬编码数组可能导致的溢出。

使用提示

1. 将代码保存为 gen.cpp 并编译：g++ gen.cpp -o gen -std=c++14。
2. 运行 ./gen 即可在当前目录获得全套数据。
3. 如果你想为更高级的题目（如平衡树）生成数据，只需将 MAXN 调整至 $10^5$ 即可。

同学你好！二叉树的中序遍历是学习平衡树（BST, Splay, Treap）的基石。在 NOI 竞赛中，掌握多种实现方式不仅是为了应对题目，更是为了在不同的内存限制和树形态下选择最稳健的策略。

以下是三种版本的完整 C++14 代码实现，统一采用 NOI 常用的静态数组存储方式。

版本一：递归法 (考场最快实现)

思路分析： 基于分治思想。处理当前节点前，先递归处理左子树，处理完后再递归处理右子树。

• 时间复杂度：$O(n)$，每个节点被访问一次。
• 空间复杂度：$O(h)$，$h$ 为树的高度。在最坏情况下（链状树）为 $O(n)$。
• 考点：理解函数调用栈的“递去”与“归来”。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 105;

// NOI 风格：静态数组存储二叉树，避免频繁申请内存
struct Node {
    int val;
    int l, r;
} tree[MAXN];

vector<int> res;

void inorder(int u) {
    // 递归边界：遇到 -1 说明子树为空
    if (u == -1) return;
    
    // 1. 先走左边
    inorder(tree[u].l);
    
    // 2. 访问当前根节点
    res.push_back(tree[u].val);
    
    // 3. 再走右边
    inorder(tree[u].r);
}

int main() {
    int n;
    if (!(cin >> n) || n == 0) return 0;
    
    // 读入节点：v 为值，l r 为左右孩子编号
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }
    
    inorder(1); // 从编号 1 的根节点开始
    
    // 输出序列
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << (i == (int)res.size() - 1 ? "" : " ");
    }
    cout << endl;
    
    return 0;
}

版本二：迭代法 (显式栈模拟)

思路分析： 在 $n$ 较大（如 $10^5$）且树极度不平衡时，递归可能导致系统栈溢出。我们通过手动维护 std::stack 来模拟回溯过程。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(h)$，栈中最多保存从根到叶子的路径节点。
• 易错点：注意 curr 指针和栈的配合。只有当 curr 为空且栈也为空时，遍历才结束。

#include <iostream>
#include <vector>
#include <stack>   // 必须包含 stack 头文件

using namespace std;

// 1. 定义最大节点数。NOI中通常根据题目要求设定，如 100005
const int MAXN = 105; 

// 2. 定义节点结构体
struct Node {
    int val;
    int l, r;
} tree[MAXN]; // 定义全局数组存储树

/**
 * 核心逻辑：使用显式栈模拟递归
 * 关键点：
 * - 只要当前节点 curr 不为空，就一直向左压栈
 * - 当左边走到底，弹出栈顶并访问，然后转向该节点的右子树
 */
void iterativeInorder(int rootIdx) {
    if (rootIdx == -1) return;

    stack<int> s;
    int curr = rootIdx;
    
    // 只要当前指针不为空，或者栈内还有回溯路径，就继续循环
    while (curr != -1 || !s.empty()) {
        // 步骤 A：一路向左，把路径上的所有“根”都存进栈里
        while (curr != -1) {
            s.push(curr);
            curr = tree[curr].l;
        }
        
        // 步骤 B：触底反弹，取出最近的一个“根”
        curr = s.top();
        s.pop();
        
        // 步骤 C：访问节点值（中序遍历的访问时机）
        cout << tree[curr].val << " ";
        
        // 步骤 D：尝试转向右子树
        // 此时如果右子树为空，下一轮循环会直接进入步骤 B，继续弹出上级根节点
        curr = tree[curr].r;
    }
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    // 读入数据
    for (int i = 1; i <= n; i++) {
        // 读入节点权值、左孩子编号、右孩子编号
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }
    
    // 执行迭代遍历
    iterativeInorder(1);
    cout << endl;

    return 0;
}

版本三：Morris 遍历 (空间 $O(1)$ 极致优化)

思路分析： 这是中序遍历的高阶技巧。它利用了二叉树中大量存在的“空指针”。

• 前驱节点 (Predecessor)：中序遍历中，当前节点 u 的前一个节点。它一定是 u 的左子树中最右边的那个节点。

• 核心逻辑：

  1. 如果 u 没有左孩子，直接访问 u 去右边。
  2. 如果 u 有左孩子，找到它的前驱 pre。
  3. 如果 pre->r 为空，建立线索（pre->r = u），去左边。
  4. 如果 pre->r == u，说明左边已遍历完，拆掉线索，访问 u，去右边。

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$，不需要栈或递归。

#include <iostream>

using namespace std;

const int MAXN = 105; 

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

void morrisInorder(int root) {
    int curr = root;
    while (curr != -1) {
        if (tree[curr].l == -1) {
            // 没有左子树，直接访问并向右走
            cout << tree[curr].val << " ";
            curr = tree[curr].r;
        } else {
            // 有左子树，寻找前驱
            int pre = tree[curr].l;
            while (tree[pre].r != -1 && tree[pre].r != curr) {
                pre = tree[pre].r;
            }
            
            if (tree[pre].r == -1) {
                // 第一次到达：建立回溯线索
                tree[pre].r = curr;
                curr = tree[curr].l;
            } else {
                // 第二次到达：说明左子树已处理完
                tree[pre].r = -1; // 恢复树结构
                cout << tree[curr].val << " "; // 中序在此处访问
                curr = tree[curr].r;
            }
        }
    }
}

int main() {
    int n; cin >> n;
    if (n == 0) return 0;
    for (int i = 1; i <= n; i++) cin >> tree[i].val >> tree[i].l >> tree[i].r;
    
    morrisInorder(1);
    cout << endl;
    return 0;
}

七、 复杂度分析思考过程

1. 时间复杂度分析：

   • 递归与迭代：逻辑上每个节点只被压栈/出栈一次，显然是 $O(n)$。
   • Morris：虽然内层有 while 找前驱，但整棵树的每条边只会被遍历两次（一次建立线索，一次拆除线索），总时间依然是线性的 $O(n)$。

2. 空间复杂度优化建议：

   • 深度问题：NOI 比赛中如果遇到 $n=10^6$ 且树退化成链，递归法必爆栈（RE）。
   • 内存池（静态数组）：版本一至三都使用了 tree[MAXN]。在竞赛中，尽量避免使用 std::vector<int> res 存储结果再输出，而是边遍历边输出，可以节省 $O(n)$ 的内存。
   • Morris 的应用：当题目内存限制极低（如 4MB），且不准使用系统栈时，Morris 遍历是唯一的“保命”手段。

八、 读题关键词总结

在 NOI 处理二叉树中序遍历时，请盯住这些词：

1. “二叉搜索树 (BST)”：一旦看到 BST，默认就要进行中序遍历，因为它能给你一个有序序列。
2. “节点数 $n \le 10^5$”：这是一个信号，暗示递归可能会爆栈，建议写迭代。
3. “第 $k$ 小元素”：中序遍历的第 $k$ 个访问节点就是答案。
4. “原地修改 (In-place)”：意味着你应该考虑 Morris 遍历的思路。

教练寄语： 中序遍历的三种写法，分别代表了算法的三重境界：递归是形态美，迭代是严谨美，Morris 是空间美。请你在纸上通过追踪 pre 和 curr 指针的变化，手推一次 Morris 遍历，这能帮你深刻理解链式结构的本质。加油！