1. 题目描述
给定一个非负二叉树，其节点以数组（顺序存储/层序）的形式给出。请分别求出该二叉树的前序遍历、中序遍历和后序遍历序列。
2. 输入格式
第一行：一个整数 N，表示节点的个数 (N < 100)。
第二行：N 个整数，以空格分隔，代表二叉树节点的数值（按层序/数组顺序排列）。
3. 输出格式
共三行，每行输出一个遍历序列，数字之间用空格分隔：
第一行：前序遍历 (Pre-order)
第二行：中序遍历 (In-order)
第三行：后序遍历 (Post-order)
4. 样例
输入：
7 4 2 6 1 3 5 7输出：
4 2 1 3 6 5 7 1 2 3 4 5 6 7 1 3 2 5 7 6 45. 样例说明
根据输入数组[4, 2, 6, 1, 3, 5, 7]构建的二叉树结构如下：
4 / \ 2 6 / \ / \ 1 3 5 7前序 (根-左-右):4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7
中序 (左-根-右):1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
后序 (左-右-根):1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4
6. 提示与约束
节点数约束：N < 100。
坑点提示：在使用递归或循环判断节点是否有孩子时，请务必注意不要访问超出数组边界的下标（即计算出的孩子下标必须小于 N）。
摘要
二叉树的遍历是数据结构的基础，也是算法面试中必考的核心知识点。本文将详细讲解如何利用 C++ 数组存储结构，通过递归（深度优先搜索，DFS）实现前序、中序、后序三种基本遍历。本文的核心在于揭示递归的设计原理：即如何通过调整三个核心操作的顺序来完成不同的遍历任务。
第一部分：数组存储与 DFS 基础
1. 二叉树的数组表示法
对于完全二叉树，数组是最简洁高效的存储方式。我们采用从索引 1 开始计数的约定：
根节点位于索引 i=1。
如果一个父节点位于索引 i，则：
它的左子节点位于索引2i。
它的右子节点位于索引2i + 1。
我们使用一个整型数组tre[300]来存储树的节点值，并约定值为0表示该位置没有节点（即空子树）。
2. 深度优先搜索 (DFS) 与递归
所有二叉树遍历本质上都是深度优先搜索。递归是实现 DFS 的最佳工具。
在树的遍历中，每一个递归函数调用，如first(root)，都代表着一个子任务：以root为根节点的子树，完成特定的遍历。
第二部分：递归设计的核心 —— “定序”原理
设计递归遍历函数的关键在于，针对当前节点root，我们只需要关注三个核心动作的执行顺序：
访问操作（根）：输出当前节点的值 (
cout << tre[root])。递归左子树（左）：调用
func(root * 2)。递归右子树（右）：调用
func(root * 2 + 1)。
通过调整“访问根节点”这一步在其余两个递归步骤中的位置，我们就能实现三种不同的遍历。
| 遍历名称 | 动作定义顺序 | 访问根节点操作 的位置 |
| 前序 | 根左 右 | 第 1 位(最先执行) |
| 中序 | 左根右 | 第 2 位(夹在中间) |
| 后序 | 左 右根 | 第 3 位(最后执行) |
第三部分：三种遍历的代码实现与解析
1. 前序遍历 (first)：根 左 右
前序遍历是最直观的，因为它遵循“先处理自身”的原则。
void first(int root){ // 根：立即访问当前节点 cout<<tre[root]<<" "; if(tre[root*2]!=0) // 左：递归处理左子树 first(root*2); if(tre[root*2+1]!=0) // 右：递归处理右子树 first(root*2+1); }逻辑总结：在进入子树之前，父节点就已经被输出了。
2. 中序遍历 (mid)：左 根 右
中序遍历要求我们必须先穷尽左侧的分支，才能访问当前节点。
void mid(int root){ if(tre[root*2]!=0) // 左：递归处理左子树 (第一步) mid(root*2); // 根：在左右递归之间访问当前节点 (第二步) cout<<tre[root]<<" "; if(tre[root*2+1]!=0) // 右：递归处理右子树 (第三步) mid(root*2+1); }逻辑总结：左子树的递归返回后，才执行cout语句，保证了左子节点总是排在父节点之前。
3. 后序遍历 (late)：左 右 根
后序遍历用于处理需要先依赖子节点结果的场景（如释放内存、计算表达式）。它要求左右子树都处理完毕后，父节点才能进行最终操作。
void late(int root){ if(tre[root*2]!=0) // 左：递归处理左子树 late(root*2); if(tre[root*2+1]!=0) // 右：递归处理右子树 late(root*2+1); // 根：最后访问当前节点 cout<<tre[root]<<" "; }逻辑总结：cout语句被放在函数的最后一行，确保了只有在左右两个递归调用彻底返回后，该节点的数值才会被输出。
完整代码
#include <iostream> using namespace std; int tre[300]; void first(int root){ cout<<tre[root]<<" ";//输出根 if(tre[root*2]!=0)//如果左节点存在，输出左节点，并以此为根节点继续递归下去。执行完最后一层的左叶子节点后就回到它根节点，去输出右叶子节点 first(root*2); if(tre[root*2+1]!=0)//执行完最后一层的左叶子节点后就回到它根节点，去输出右叶子节点 first(root*2+1); } void mid(int root){ if(tre[root*2]!=0)//如果左儿子节点存在，就继续递归 mid(root*2); cout<<tre[root]<<" ";//递归到最后一层的不存在左儿子节点，然后输出 if(tre[root*2+1]!=0)//如果右儿子节点存在，就输出 mid(root*2+1); } //后序遍历 void late(int root){ if(tre[root*2]!=0) late(root*2); if(tre[root*2+1]!=0) late(root*2+1); cout<<tre[root]<<" "; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>tre[i]; //输出先序遍历 根左右 first(1); //输出中序遍历 左根右 cout<<endl; mid(1); //输出后序遍历 根左右 cout<<endl; late(1); }总结与延伸
通过本文的分析，我们理解了二叉树三种递归遍历的本质区别仅在于：“访问根节点”的操作相对于“递归左右子树”的操作，被放置在了函数体的哪个位置。
这种“定序”的思维模式是掌握所有树结构递归算法的基础。掌握了这一点，无论是链表存储的二叉树还是其他变种的 DFS 任务，都能快速设计出正确的递归函数。
