深入理解树的遍历：从基础到实战
树是计算机科学中最重要且应用最广泛的数据结构之一。本文将全面介绍树的遍历方法，包括递归与非递归实现，并结合实际应用场景，帮助读者彻底掌握这一核心概念。
一、树的基础概念
树是由n（n≥0）个节点组成的有限集合，当n=0时称为空树。非空树具有以下特性：
有且仅有一个根节点其余节点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树
树的常见类型
二叉树：每个节点最多有两个子节点二叉搜索树(BST)：左子树所有节点值小于根节点，右子树所有节点值大于根节点平衡二叉树(AVL)：任何节点的左右子树高度差不超过1红黑树：自平衡二叉搜索树的另一种实现B树/B+树：用于文件系统和数据库的多路搜索树
二、树的遍历方法
树的遍历是指按照某种规则访问树中所有节点的过程。主要有以下几种遍历方式：
1. 深度优先遍历(DFS)
前序遍历(Pre-order)
访问顺序：根节点 → 左子树 → 右子树
递归实现：
def preorder(root):
if root:
print(root.val) # 访问根节点
preorder(root.left) # 遍历左子树
preorder(root.right) # 遍历右子树
非递归实现（使用栈）：
def preorder(root):
stack = []
while root or stack:
while root:
print(root.val) # 访问节点
stack.append(root)
root = root.left
root = stack.pop()
root = root.right
中序遍历(In-order)
访问顺序：左子树 → 根节点 → 右子树
递归实现：
def inorder(root):
if root:
inorder(root.left) # 遍历左子树
print(root.val) # 访问根节点
inorder(root.right) # 遍历右子树
非递归实现：
def inorder(root):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
print(root.val) # 访问节点
root = root.right
后序遍历(Post-order)
访问顺序：左子树 → 右子树 → 根节点
递归实现：
def postorder(root):
if root:
postorder(root.left) # 遍历左子树
postorder(root.right) # 遍历右子树
print(root.val) # 访问根节点
非递归实现（使用两个栈）：
def postorder(root):
if not root:
return
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
print(stack2.pop().val)
前序遍历(Pre-order)
访问顺序：根节点 → 左子树 → 左子树
递归实现：
def postorder(root):
if root:
postorder(root.left) # 遍历左子树
postorder(root.right) # 遍历右子树
print(root.val) # 访问根节点
非递归实现（使用两个栈）：
def postorder(root):
if not root:
return
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
print(stack2.pop().val)
### 2. 广度优先遍历(BFS)/层次遍历
访问顺序：从上到下，从左到右逐层访问
**实现（使用队列）：**
```python
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
三、遍历的应用场景
1. 前序遍历应用
复制一棵树计算前缀表达式打印目录结构
2. 中序遍历应用
二叉搜索树的有序遍历表达式树的中缀表达式输出恢复二叉搜索树结构
3. 后序遍历应用
删除树计算后缀表达式计算目录大小
4. 层次遍历应用
寻找最短路径（无权图）序列化二叉树寻找每层最大值
四、特殊树的遍历
1. N叉树的遍历
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children or []
def nary_preorder(root):
if not root:
return []
result = [root.val]
for child in root.children:
result += nary_preorder(child)
return result
2. 线索二叉树的遍历
线索二叉树通过利用空指针存储前驱或后继信息，可以实现无需栈/递归的遍历。
五、遍历的复杂度分析
对于n个节点的树：
时间复杂度：O(n)，因为每个节点访问一次空间复杂度：
递归：O(h)，h为树的高度（递归栈空间）非递归：O(n)最坏情况（退化为链表）
六、实战题目推荐
理解了基础知识后我们来做两道题熟悉一下
pta:L2-006 树的遍历
这道题是道经典的树的遍历的题，我们只知道后序遍历是求不出树的，所以题目给了后序遍历和中序遍历，要求我们求出前序遍历。
#include
using namespace std;
const int N = 51; // 定义最大节点数
int n, hx[N], zx[N]; // hx存储后序遍历结果，zx存储中序遍历结果
// 二叉树节点结构体
struct node {
int val; // 节点值
node *left; // 左子节点指针
node *right; // 右子节点指针
node() : left(NULL), right(NULL) {} // 初始化左右指针为NULL
};
/*
* 根据后序和中序遍历结果重建二叉树
* 参数：
* hxl, hxr: 后序遍历数组的左右边界索引
* zxl, zxr: 中序遍历数组的左右边界索引
* 返回：
* 重建的二叉树根节点指针
*/
node* make(int hxl, int hxr, int zxl, int zxr) {
// 递归终止条件：当左边界超过右边界时返回NULL
if(hxl > hxr) return NULL;
// 创建新节点，值为后序遍历的最后一个元素（当前子树的根节点）
node *p = new node;
p->val = hx[hxr];
// 在中序遍历结果中查找根节点的位置
int root_val = hx[hxr];
int i; // 根节点在中序遍历中的索引
for(i = zxl; i <= zxr && zx[i] != root_val; i++);
// 计算左子树在后序遍历中的右边界：hxl + (左子树长度-1)
// 左子树长度 = i(根位置) - zxl(中序左边界)
int left_tree_right = hxl + (i - 1 - zxl);
// 递归构建左子树
p->left = make(hxl, left_tree_right, zxl, i-1);
// 递归构建右子树
p->right = make(left_tree_right + 1, hxr - 1, i + 1, zxr);
return p;
}
/*
* 层次遍历（BFS）打印二叉树
* 参数：
* p: 二叉树根节点指针
*/
void print(node *p) {
if(!p) return; // 空树处理
queue
int head = p->val; // 记录根节点值（用于控制输出格式）
q.push(*p); // 根节点入队
while(!q.empty()) {
node f = q.front(); // 取出队首节点
q.pop();
// 控制输出格式：根节点前不加空格，其他节点前加空格
if(f.val != head) cout << " ";
cout << f.val;
// 将左右子节点入队（如果存在）
if(f.left) q.push(*(f.left));
if(f.right) q.push(*(f.right));
}
}
int main() {
cin >> n; // 输入节点数量
// 输入后序遍历结果
for(int i = 0; i < n; i++) cin >> hx[i];
// 输入中序遍历结果
for(int j = 0; j < n; j++) cin >> zx[j];
// 重建二叉树
node* head = make(0, n-1, 0, n-1);
// 层次遍历输出
print(head);
return 0;
}
七、总结
树的遍历是算法学习的基础，掌握各种遍历方法及其应用场景对解决实际问题至关重要。建议读者：
理解每种遍历的特点和访问顺序掌握递归和非递归的实现方式通过实际题目加深理解尝试自己推导遍历序列
希望本文能帮助你系统性地理解树的遍历，在算法学习和面试中游刃有余！