二叉树的三种遍历方法

一、二叉树遍历基础概念

二叉树的遍历是指按某种规则访问树中所有节点，且每个节点仅访问一次。核心的三种遍历方式基于节点访问顺序划分：

• 前序遍历（Pre-order）：根节点 → 左子树 → 右子树        “根左右”
• 中序遍历（In-order）：左子树 → 根节点 → 右子树          “左根右”
• 后序遍历（Post-order）：左子树 → 右子树 → 根节点       “左右根”

以下实现基于二叉树节点的标准定义：

struct TreeNode {
    int val;
    TreeNode *left;  // 左子节点
    TreeNode *right; // 右子节点
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

二、递归实现（简洁直观）

递归是二叉树遍历最自然的实现方式，利用函数栈实现节点访问顺序控制。

2.1 前序遍历（递归）

#include <vector>
using namespace std;

// 前序遍历：根 → 左 → 右
void preorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return; // 递归终止条件：空节点
    result.push_back(root->val); // 访问根节点
    preorderRecursive(root->left, result);  // 遍历左子树
    preorderRecursive(root->right, result); // 遍历右子树
}

// 对外接口
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    preorderRecursive(root, result);
    return result;
}

2.2 中序遍历（递归）

// 中序遍历：左 → 根 → 右
void inorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderRecursive(root->left, result);  // 遍历左子树
    result.push_back(root->val); // 访问根节点
    inorderRecursive(root->right, result); // 遍历右子树
}

// 对外接口
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorderRecursive(root, result);
    return result;
}

2.3 后序遍历（递归）

// 后序遍历：左 → 右 → 根
void postorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderRecursive(root->left, result);  // 遍历左子树
    postorderRecursive(root->right, result); // 遍历右子树
    result.push_back(root->val); // 访问根节点
}

// 对外接口
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    postorderRecursive(root, result);
    return result;
}

递归优势：代码简洁，逻辑清晰；缺点：深度过大时可能栈溢出，不适合极端大规模树。

三、迭代实现（手动控制栈）

迭代方式通过显式栈模拟递归过程，避免递归栈溢出风险，更适合工程实践。

3.1 前序遍历（迭代）

核心思路：根节点先入栈，出栈时访问，再依次入栈右子树、左子树（利用栈的 LIFO 特性）。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    st.push(root); // 根节点先入栈
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val); // 访问根节点
        
        // 右子树先入栈（后访问），左子树后入栈（先访问）
        if (node->right != nullptr) st.push(node->right);
        if (node->left != nullptr) st.push(node->left);
    }
    return result;
}

3.2 中序遍历（迭代）

核心思路：左子树一路入栈，触底后出栈访问，再转向右子树重复。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    TreeNode* cur = root;
    
    while (cur != nullptr || !st.empty()) {
        // 左子树全部入栈
        while (cur != nullptr) {
            st.push(cur);
            cur = cur->left;
        }
        
        // 出栈访问根节点
        cur = st.top();
        st.pop();
        result.push_back(cur->val);
        
        // 转向右子树
        cur = cur->right;
    }
    return result;
}

3.3 后序遍历（迭代）

核心思路：前序遍历变种（根→右→左），最后反转结果得到左→右→根。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val); // 先按根→右→左顺序收集
        
        // 左子树先入栈（后访问），右子树后入栈（先访问）
        if (node->left != nullptr) st.push(node->left);
        if (node->right != nullptr) st.push(node->right);
    }
    
    reverse(result.begin(), result.end()); // 反转得到后序遍历
    return result;
}

迭代优势：无栈溢出风险，可控性强；缺点：逻辑稍复杂，需手动控制节点入栈顺序。

四、遍历验证与示例

4.1 测试用例构建

以如下二叉树为例，验证三种遍历结果：

      1
       \
        2
       /
      3

构建代码：

TreeNode* buildTestTree() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    return root;
}

4.2 预期输出

• 前序遍历：[1, 2, 3]
• 中序遍历：[1, 3, 2]
• 后序遍历：[3, 2, 1]

五、三种遍历对比与应用场景

（注：n 为节点数，h 为树的高度，平衡树 h=logn，极端链状树 h=n）

六、代码封装与扩展

实际开发中可封装为工具类，支持多种遍历方式切换：

class BinaryTreeTraversal {
public:
    enum TraversalType { PREORDER, INORDER, POSTORDER };
    
    vector<int> traverse(TreeNode* root, TraversalType type) {
        switch (type) {
            case PREORDER: return preorder(root);
            case INORDER: return inorder(root);
            case POSTORDER: return postorder(root);
            default: return {};
        }
    }

private:
    // 此处省略前序、中序、后序的迭代实现（复用前文代码）
    vector<int> preorder(TreeNode* root) { /* ... */ }
    vector<int> inorder(TreeNode* root) { /* ... */ }
    vector<int> postorder(TreeNode* root) { /* ... */ }
};

扩展建议：

• 增加层序遍历（广度优先）支持；
• 实现 Morris 遍历（O (1) 空间复杂度，无栈）；
• 支持自定义节点访问函数（如打印、计算等）。

通过掌握二叉树的三种核心遍历方式，可奠定树结构算法的基础，后续复杂树问题（如路径求和、子树判断）均需基于遍历逻辑扩展。实际开发中根据场景选择递归（简单场景）或迭代（高性能需求）实现。