深入理解C++二叉树遍历算法（从零开始掌握前序、中序与后序遍历）

三种基本遍历方式

数据结构二叉树教程中，最核心的就是以下三种深度优先遍历方法：

• 前序遍历（Pre-order）：根 → 左 → 右
• 中序遍历（In-order）：左 → 根 → 右
• 后序遍历（Post-order）：左 → 右 → 根

C++实现二叉树节点结构

首先，我们需要定义一个二叉树节点的结构体：

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;        // 构造函数    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};  

1. 前序遍历（Pre-order Traversal）

访问顺序：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

void preOrder(TreeNode* root) {    // 递归终止条件    if (root == nullptr) {        return;    }        // 访问当前节点    std::cout << root->val << " ";        // 递归遍历左子树    preOrder(root->left);        // 递归遍历右子树    preOrder(root->right);}  

2. 中序遍历（In-order Traversal）

访问顺序：先递归遍历左子树，再访问根节点，最后递归遍历右子树。对于二叉搜索树，中序遍历会输出有序序列。

void inOrder(TreeNode* root) {    if (root == nullptr) {        return;    }        inOrder(root->left);           // 遍历左子树    std::cout << root->val << " "; // 访问根节点    inOrder(root->right);          // 遍历右子树}  

3. 后序遍历（Post-order Traversal）

访问顺序：先递归遍历左子树，再递归遍历右子树，最后访问根节点。常用于释放树内存或计算目录大小等场景。

void postOrder(TreeNode* root) {    if (root == nullptr) {        return;    }        postOrder(root->left);         // 遍历左子树    postOrder(root->right);        // 遍历右子树    std::cout << root->val << " "; // 访问根节点}  

完整示例程序

下面是一个完整的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) return;    std::cout << root->val << " ";    preOrder(root->left);    preOrder(root->right);}void inOrder(TreeNode* root) {    if (!root) return;    inOrder(root->left);    std::cout << root->val << " ";    inOrder(root->right);}void postOrder(TreeNode* root) {    if (!root) 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);  // 输出: 1 2 4 5 3    std::cout << std::endl;        std::cout << "中序遍历: ";    inOrder(root);   // 输出: 4 2 5 1 3    std::cout << std::endl;        std::cout << "后序遍历: ";    postOrder(root); // 输出: 4 5 2 3 1    std::cout << std::endl;        // 注意：实际项目中应释放动态分配的内存    return 0;}  

总结

通过本教程，你已经掌握了C++递归遍历二叉树的三种基本方法。记住它们的核心区别在于“访问根节点”的时机不同。多加练习，尝试在纸上画出遍历过程，你会对数据结构二叉树教程中的这些概念有更深刻的理解。

无论是面试还是实际开发，熟练运用C++二叉树遍历都是程序员的基本功。希望这篇二叉树前序中序后序的入门指南能为你打下坚实基础！