题目：二叉树的遍历

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 4

5. 样例说明

根据输入数组[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，我们只需要关注三个核心动作的执行顺序：

1. 访问操作（根）：输出当前节点的值 (cout << tre[root])。

2. 递归左子树（左）：调用func(root * 2)。

3. 递归右子树（右）：调用func(root * 2 + 1)。

通过调整“访问根节点”这一步在其余两个递归步骤中的位置，我们就能实现三种不同的遍历。

第三部分：三种遍历的代码实现与解析

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 任务，都能快速设计出正确的递归函数。