为了方便你为 OJ (Online Judge) 准备测试数据，我为你编写了一个基于 C++14 标准的数据生成器。

该生成器会生成 10 组测试点，涵盖了空树、单节点、完全二叉树、左斜树（链状）、右斜树（链状）以及复杂随机树。为了保证生成的 .out 文件绝对正确且不会爆栈，生成器内部使用了**迭代式（显式栈）**的前序遍历算法。

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

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

using namespace std;

// 节点结构体
struct Node {
    int val;
    int l, r;
};

// 使用迭代法生成标准答案，确保不爆栈
vector<int> getPreorder(int n, const vector<Node>& tree) {
    if (n <= 0) return {};
    vector<int> res;
    stack<int> s;
    s.push(1); // 根节点固定为 1
    
    while (!s.empty()) {
        int u = s.top();
        s.pop();
        res.push_back(tree[u].val);
        // 先压右再压左，弹出时即为先左后右
        if (tree[u].r != -1) s.push(tree[u].r);
        if (tree[u].l != -1) s.push(tree[u].l);
    }
    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;
        vector<Node> tree;
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";

        if (t == 1) n = 0; // 边界：空树
        else if (t == 2) n = 1; // 边界：单节点
        else if (t == 3) n = 3; // 基础树：1 是根，2 是左，3 是右
        else if (t == 4) n = 50; // 左斜树 (退化成链)
        else if (t == 5) n = 50; // 右斜树 (退化成链)
        else if (t == 6) n = 63; // 满二叉树 (深度为 6)
        else if (t == 7) n = 100; // 随机树 1
        else if (t == 8) n = 100; // 随机树 2
        else if (t == 9) n = 100; // 随机树 3
        else n = 100; // 最大规模随机树

        tree.assign(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) { // 左斜
            for (int i = 1; i < n; ++i) tree[i].l = i + 1;
        } else if (t == 5) { // 右斜
            for (int i = 1; i < n; ++i) tree[i].r = i + 1;
        } else if (t == 6) { // 满二叉树逻辑
            for (int i = 1; i <= n / 2; ++i) {
                tree[i].l = 2 * i;
                tree[i].r = 2 * i + 1;
            }
        } else if (t >= 7) { // 随机生成合法二叉树
            vector<int> available;
            available.push_back(1);
            vector<int> free_slots(n + 1, 2); 
            for (int i = 2; i <= n; ++i) {
                uniform_int_distribution<int> pick(0, (int)available.size() - 1);
                int p_idx = pick(rng);
                int p = available[p_idx];
                
                if (tree[p].l == -1 && tree[p].r == -1) {
                    if (rng() % 2) tree[p].l = i; else tree[p].r = i;
                } else if (tree[p].l == -1) tree[p].l = i;
                else tree[p].r = i;

                free_slots[p]--;
                if (free_slots[p] == 0) {
                    available.erase(available.begin() + p_idx);
                }
                available.push_back(i);
            }
        }

        writeIn(n, tree, in_name);
        writeOut(getPreorder(n, tree), out_name);
        cout << "Generated Case " << t << " (n=" << n << ")" << endl;
    }
    return 0;
}

测试点详细说明表

数据生成器设计规范说明

1. 非递归求精 (Safety)：
   • 在生成 .out 标准答案时，我使用了 stack<int> 模拟的迭代法。即使未来将 $n$ 调整到 $10^6$，这个生成器也不会因为系统栈溢出而崩溃，确保了数据的可靠性。
2. 文件大小优化 (Compactness)：
   • $n=100$ 的规模下，每个 .in 文件大约只有 1KB 到 2KB。10 组数据总大小不超过 30KB，极大地节省了 OJ 存储和下载带宽。
3. 随机性与合法性 (Correctness)：
   • 随机树算法：采用“节点逐一加入”法。新节点 $i$ 随机挂载到已有节点 $p$ 的空槽位上。这种方法保证了生成的结构一定是合法的二叉树，且不会出现环或多个根。
   • 种子设置：使用 chrono 纳秒时钟，保证每次运行生成的数据序列都是唯一的。
4. 防除零与异常 (Robustness)：
   • 代码逻辑中不涉及除法操作（除满二叉树索引外，已做安全判断），避免了 Floating Point Exception。
   • 使用了 vector 管理内存，避免了手动申请内存可能导致的 Memory Limit Exceeded。

使用方法

1. 将代码保存为 gen.cpp。
2. 在终端执行：g++ gen.cpp -o gen -std=c++14。
3. 运行 ./gen，当前目录即会出现 1.in/1.out 到 10.in/10.out。

同学你好！二叉树的前序遍历是树论算法的起点。在 NOI 竞赛中，掌握不同复杂度的实现方式能让你在面对不同内存限制（MLE）和时间限制（TLE）时游刃有余。

以下是三种版本的完整 C++14 代码实现。

版本一：递归法 (最简实现)

思路分析： 利用二叉树的递归特性：Preorder(root) = root + Preorder(root->left) + Preorder(root->right)。

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(h)$，$h$ 为树高。最坏情况下（链状树）为 $O(n)$。
• 关键点：递归边界判断 if (root == nullptr)。

#include <iostream>
#include <vector>

using namespace std;

// NOI 竞赛常使用静态数组模拟树结构
struct Node {
    int val;
    int l, r;
} tree[105];

// 结果存储
vector<int> res;

void preorder(int u) {
    if (u == -1) return; // 递归边界：遇到空节点返回
    
    // 1. 访问根节点
    res.push_back(tree[u].val);
    
    // 2. 递归左子树
    preorder(tree[u].l);
    
    // 3. 递归右子树
    preorder(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;
    }
    
    preorder(1); // 从编号 1 的根节点开始
    
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    cout << endl;
    
    return 0;
}

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

思路分析： 为了防止递归层数过深导致栈溢出，我们手动维护一个 std::stack。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(h)$。
• 易错点：由于栈是 LIFO (后进先出)，在前序遍历中，为了先访问左孩子，必须先将右孩子压栈，再将左孩子压栈。

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

void iterativePreorder(int rootIdx) {
    if (rootIdx == -1) return;
    
    stack<int> s;
    s.push(rootIdx);
    
    while (!s.empty()) {
        int u = s.top();
        s.pop();
        
        cout << tree[u].val << " "; // 访问当前根
        
        // 关键：先压右再压左，弹出时就是先左后右
        if (tree[u].r != -1) s.push(tree[u].r);
        if (tree[u].l != -1) s.push(tree[u].l);
    }
}

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;
    
    iterativePreorder(1);
    cout << endl;
    return 0;
}

版本三：Morris 遍历 (空间最优解)

思路分析： Morris 遍历的精髓在于利用叶子节点的空指针。它通过建立临时的“线索”回到父节点，从而实现 $O(1)$ 的额外空间。

• 时间复杂度：$O(n)$。虽然有嵌套循环，但每条边最多被访问 3 次。
• 空间复杂度：$O(1)$，不计存储答案的容器。
• 关键逻辑：
  1. 如果当前节点左子树为空，访问当前节点，去右边。
  2. 如果左子树不为空，找到左子树最右边的节点（前驱节点）。
  3. 如果前驱节点的右指针为空，说明第一次到这，访问当前节点，建立线索（右指针指向自己），去左边。
  4. 如果前驱节点的右指针指向自己，说明左边走完了，拆掉线索，去右边。

#include <iostream>
#include <vector>

using namespace std;

// 为实现 Morris 遍历，我们需要指针化的结构，或者在静态数组上操作
struct Node {
    int val;
    int l, r;
} tree[105];

void morrisPreorder(int rootIdx) {
    int curr = rootIdx;
    while (curr != -1) {
        if (tree[curr].l == -1) {
            // 情况 1: 没有左孩子，直接访问并去右边
            cout << tree[curr].val << " ";
            curr = tree[curr].r;
        } else {
            // 情况 2: 有左孩子，找前驱
            int pre = tree[curr].l;
            while (tree[pre].r != -1 && tree[pre].r != curr) {
                pre = tree[pre].r;
            }
            
            if (tree[pre].r == -1) {
                // 第一次访问：建立线索
                cout << tree[curr].val << " "; // 前序遍历在建立线索时访问
                tree[pre].r = curr;
                curr = tree[curr].l;
            } else {
                // 第二次访问：线索已存在，拆除线索回溯
                tree[pre].r = -1;
                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;
    
    morrisPreorder(1);
    cout << endl;
    return 0;
}

四、 复杂度分析思考过程

1. 时间复杂度分析：

   • 递归与迭代：很明显，每个节点进出栈一次或访问一次，均为 $O(n)$。
   • Morris：乍看 while 嵌套 while 像 $O(n^2)$，但实际上每条“建立线索”的边在建立和拆除时各走一次，总边数 $n-1$，故为 $O(n)$。

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

   • 在 NOI 比赛中，若 $n$ 较大且树退化为链（深度大），递归法会报 RE (栈溢出)。
   • 优化 1：优先使用迭代法。
   • 优化 2：如果内存限制极其严苛（如 4MB/8MB），Morris 遍历是唯一选择。
   • 优化 3：读入优化。若 $n > 10^5$，使用 scanf 或 getchar() 快读。

五、 读题关键词总结 (考场指南)

在处理树遍历题目时，注意这些隐含信息：

1. “前序/先序 (Preorder)”：核心是“早访问”。只要到了一个节点，还没去子树前就要处理它。
2. “$O(n)$ 节点”：如果 $n$ 特别大（如 $10^6$），注意递归深度，必要时手动开大系统栈或改迭代。
3. “节点值范围”：如果值很大，注意是否需要 long long（本题不需要）。
4. “左、右子树”：在迭代法中，注意入栈顺序与遍历顺序是相反的。

教练寄语： 同学，二叉树的前序遍历是进入高级算法的大门。递归法练的是逻辑拆解，迭代法练的是数据结构模拟，而 Morris 遍历练的是空间复用的极致思维。请一定要在草稿纸上把 Morris 建立和拆除线索的过程画出来，那是算法之美。加油！