在C++里实现二叉树遍历，最直观的方式是使用递归。我们通常会先定义树的节点结构，然后针对前序、中序、后序三种顺序分别编写递归函数。这三种遍历的区别仅在于访问根节点的时机不同。
二叉树节点定义
首先给出最简单的二叉树节点结构，每个节点保存一个整型值，以及左右子节点指针：
#include <iostream>
// 二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
前序遍历递归实现
前序遍历的顺序是：根节点、左子树、右子树。代码如下：
// 前序遍历：根-左-右
void preorder(TreeNode* root) {
if (root == nullptr) {
return;
}
std::cout << root->val << " "; // 访问根
preorder(root->left); // 遍历左
preorder(root->right); // 遍历右
}
中序遍历递归实现
中序遍历的顺序是：左子树、根节点、右子树。对于二叉搜索树，中序遍历会输出有序序列：
// 中序遍历：左-根-右
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left); // 遍历左
std::cout << root->val << " "; // 访问根
inorder(root->right); // 遍历右
}
后序遍历递归实现
后序遍历的顺序是：左子树、右子树、根节点：
// 后序遍历：左-右-根
void postorder(TreeNode* root) {
if (root == nullptr) {
return;
}
postorder(root->left); // 遍历左
postorder(root->right); // 遍历右
std::cout << root->val << " "; // 访问根
}
完整使用示例
下面构造一个简单二叉树并调用三种遍历函数：
int main() {
// 构造树:
// 1
// /
// 2 3
// /
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
std::cout << "前序: ";
preorder(root);
std::cout << "n中序: ";
inorder(root);
std::cout << "n后序: ";
postorder(root);
return 0;
}
递归逻辑小结
三种递归遍历写法非常相似，核心都依赖函数调用栈来保存返回位置。当节点为空时直接返回，否则按照对应顺序安排cout输出与左右递归调用的位置。理解这些基础递归算法，有助于后续学习使用栈模拟递归或非递归遍历方式。