一、二叉树遍历的类型
二叉树的遍历通常分为两大类：深度优先遍历（Depth-First Traversal, DFS）和广度优先遍历（Breadth-First Traversal, BFS）。在深度优先遍历中，又可以进一步分为前序遍历、中序遍历和后序遍历。广度优先遍历通常就是指层序遍历。
遍历二叉树是指按照一定的顺序访问树中的每个节点。常见的二叉树遍历方式主要分为以下几类：
前序遍历（Pre-order Traversal）: 先访问根节点，然后遍历左子树，最后遍历右子树。中序遍历（In-order Traversal）: 先遍历左子树，然后访问根节点，最后遍历右子树。后序遍历（Post-order Traversal）: 先遍历左子树，然后遍历右子树，最后访问根节点。层次遍历（Level-order Traversal）: 按照从上到下、从左到右的顺序逐层遍历节点。
下面，我们将详细介绍每种遍历方式的原理、代码实现，并结合一个实例二叉树进行分析。
1. 前序遍历（Pre-order Traversal）
原理
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。这种遍历方式首先访问根节点，然后依次遍历左子树和右子树。
代码实现
递归实现：
void preOrder(TreeNode* root) {
if (root == nullptr) return;
std::cout << root->val << " "; // 访问根节点
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
迭代实现：
void preOrderIterative(TreeNode* root) {
if (root == nullptr) return;
std::stack
stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
std::cout << node->val << " "; // 访问根节点
if (node->right) stack.push(node->right); // 右子树入栈
if (node->left) stack.push(node->left); // 左子树入栈
}
}
实例分析
假设我们有一个二叉树如下：
1
/ \
2 3
/ \
4 5
前序遍历过程：
访问根节点 1，输出 1。递归遍历左子树，访问节点 2，输出 2。继续递归遍历节点 2 的左子树，访问节点 4，输出 4。节点 4 无子节点，返回到节点 2，遍历节点 2 的右子树，访问节点 5，输出 5。返回到根节点 1，递归遍历右子树，访问节点 3，输出 3。
最终的前序遍历结果为：1 2 4 5 3。
2. 中序遍历（In-order Traversal）
原理
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。这种遍历方式首先遍历左子树，然后访问根节点，最后遍历右子树。
代码实现
递归实现：
void inOrder(TreeNode* root) {
if (root == nullptr) return;
inOrder(root->left); // 递归遍历左子树
std::cout << root->val << " "; // 访问根节点
inOrder(root->right); // 递归遍历右子树
}
迭代实现：
void inOrderIterative(TreeNode* root) {
std::stack
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
while (current != nullptr) {
stack.push(current); // 左子树入栈
current = current->left;
}
current = stack.top();
stack.pop();
std::cout << current->val << " "; // 访问根节点
current = current->right; // 遍历右子树
}
}
实例分析
继续使用前面的二叉树实例：
1
/ \
2 3
/ \
4 5
中序遍历过程：
递归遍历左子树，访问节点 4，输出 4。返回到节点 2，访问节点 2，输出 2。继续遍历右子树，访问节点 5，输出 5。返回到根节点 1，访问节点 1，输出 1。递归遍历右子树，访问节点 3，输出 3。
最终的中序遍历结果为：4 2 5 1 3。
3. 后序遍历（Post-order Traversal）
原理
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。这种遍历方式首先遍历左子树，然后遍历右子树，最后访问根节点。
代码实现
递归实现：
void postOrder(TreeNode* root) {
if (root == nullptr) return;
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
std::cout << root->val << " "; // 访问根节点
}
迭代实现：
void postOrderIterative(TreeNode* root) {
if (root == nullptr) return;
std::stack
stack1.push(root);
while (!stack1.empty()) {
TreeNode* node = stack1.top();
stack1.pop();
stack2.push(node);
if (node->left) stack1.push(node->left); // 左子树入栈
if (node->right) stack1.push(node->right); // 右子树入栈
}
while (!stack2.empty()) {
std::cout << stack2.top()->val << " "; // 访问根节点
stack2.pop();
}
}
实例分析
仍然使用相同的二叉树实例：
1
/ \
2 3
/ \
4 5
后序遍历过程：
递归遍历左子树，访问节点 4，输出 4。返回到节点 2，遍历右子树，访问节点 5，输出 5。返回到节点 2，访问节点 2，输出 2。返回到根节点 1，遍历右子树，访问节点 3，输出 3。最后访问根节点 1，输出 1。
最终的后序遍历结果为：4 5 2 3 1。
4. 层次遍历（Level-order Traversal）
原理
层次遍历的顺序是：逐层从左到右遍历。这种遍历方式利用队列的先进先出特性，按层次从上到下、从左到右依次访问节点。
代码实现
void levelOrder(TreeNode* root) {
if (root == nullptr) return;
std::queue
queue.push(root);
while (!queue.empty()) {
TreeNode* node = queue.front();
queue.pop();
std::cout << node->val << " "; // 访问当前节点
if (node->left) queue.push(node->left); // 左子树入队
if (node->right) queue.push(node->right); // 右子树入队
}
}
实例分析
继续使用前面的二叉树实例：
1
/ \
2 3
/ \
4 5
层次遍历过程：
初始队列：[1]，访问节点 1，输出 1，并将其左右子节点 2 和 3 入队。队列更新为：[2, 3]，访问节点 2，输出 2，并将其左右子节点 4 和 5 入队。队列更新为：[3, 4, 5]，访问节点 3，输出 3，节点 3 无子节点。队列更新为：[4, 5]，访问节点 4，输出 4，节点 4 无子节点。队列更新为：[5]，访问节点 5，输出 5，节点 5 无子节点。
最终的层次遍历结果为：1 2 3 4 5。
二、 总结
遍历二叉树是掌握二叉树结构的基础。在实际应用中，不同的遍历方式有不同的适用场景：
前序遍历：适用于需要在访问节点时立即处理的情况，比如复制树结构。中序遍历：常用于需要按顺序访问节点的场景，比如在二叉搜索树中查找某个范围内的元素。后序遍历：通常用于需要在处理完所有子节点后才处理当前节点的情况，比如删除树。层次遍历：适合按层次处理树节点的问题，比如计算树的层数或查找某一层的所有节点。
不同的遍历方式本质上是通过不同的顺序来访问树中的节点，理解这些遍历方式有助于更深入地理解二叉树的结构和操作。