二叉树中序遍历：递归与非递归实现详解

什么是二叉树的中序遍历？

中序遍历（Inorder Traversal）是二叉树遍历的一种经典方式，其遍历顺序遵循 “左子树 → 根节点 → 右子树” 的原则。

对于下面这个二叉树：

        A
       / \
      B   C
     / \   \
    D   E   F

中序遍历的结果是：D → B → E → A → C → F

中序遍历的核心原理

递归思想（最直观的理解）

1. 遍历左子树
2. 访问根节点
3. 遍历右子树

这种分治思想非常适合用递归实现，因为每个子树都可以看作是一个更小的二叉树。

非递归思想（手动维护栈）

模拟递归调用的过程，需要显式地使用栈来保存待访问的节点：

1. 从根节点开始，将所有左子节点压入栈
2. 弹出栈顶节点并访问
3. 转向该节点的右子树，重复步骤1

完整C++实现

1. 二叉树节点定义

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 递归实现

class Solution {
public:
    // 递归中序遍历
    vector<int> inorderTraversalRecursive(TreeNode* root) {
        vector<int> result;
        inorderHelper(root, result);
        return result;
    }
    
private:
    void inorderHelper(TreeNode* node, vector<int>& result) {
        if (!node) return;  // 递归终止条件
        
        inorderHelper(node->left, result);  // 遍历左子树
        result.push_back(node->val);        // 访问根节点
        inorderHelper(node->right, result); // 遍历右子树
    }
};

递归流程分析：

调用 inorder(A)
├── 调用 inorder(B)
│   ├── 调用 inorder(D) → 访问 D
│   ├── 访问 B
│   └── 调用 inorder(E) → 访问 E
├── 访问 A
└── 调用 inorder(C)
    ├── 访问 C
    └── 调用 inorder(F) → 访问 F

3. 非递归实现（使用栈）

class Solution {
public:
    // 非递归中序遍历（迭代法）
    vector<int> inorderTraversalIterative(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodeStack;
        TreeNode* current = root;
        
        // 当当前节点不为空或栈不为空时继续
        while (current != nullptr || !nodeStack.empty()) {
            // 深入左子树，将所有左子节点入栈
            while (current != nullptr) {
                nodeStack.push(current);
                current = current->left;
            }
            
            // 弹出栈顶节点并访问
            current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->val);
            
            // 转向右子树
            current = current->right;
        }
        
        return result;
    }
};

非递归流程分析（示例二叉树）：

初始：current = A, stack = []
1. 将A、B、D依次入栈 → stack = [A, B, D], current = null
2. 弹出D访问 → result = [D], current = D.right = null
3. 弹出B访问 → result = [D, B], current = B.right = E
4. 将E入栈 → stack = [A, E], current = null
5. 弹出E访问 → result = [D, B, E], current = E.right = null
6. 弹出A访问 → result = [D, B, E, A], current = A.right = C
7. 将C入栈 → stack = [C], current = null
8. 弹出C访问 → result = [D, B, E, A, C], current = C.right = F
9. 将F入栈 → stack = [F], current = null
10. 弹出F访问 → result = [D, B, E, A, C, F], current = null
结束

对比分析

测试示例

// 创建测试二叉树
TreeNode* createTestTree() {
    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);
    root->right->right = new TreeNode(6);
    return root;
}

int main() {
    TreeNode* root = createTestTree();
    Solution solution;
    
    cout << "递归中序遍历结果: ";
    vector<int> recursiveResult = solution.inorderTraversalRecursive(root);
    for (int val : recursiveResult) {
        cout << val << " ";
    }
    cout << endl;
    
    cout << "非递归中序遍历结果: ";
    vector<int> iterativeResult = solution.inorderTraversalIterative(root);
    for (int val : iterativeResult) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果：

递归中序遍历结果: 4 2 5 1 3 6 
非递归中序遍历结果: 4 2 5 1 3 6 

应用场景

1. 二叉搜索树（BST）排序：中序遍历BST会得到有序序列
2. 表达式树求值：中序遍历可以还原中缀表达式
3. 复制二叉树：按中序顺序复制节点
4. 调试和分析：查看树的结构

总结

中序遍历是二叉树算法的基础，掌握其递归和非递归实现非常重要：

• 递归实现：直观易懂，适合快速实现和教学
• 非递归实现：更高效，避免递归深度限制，是面试常考点

理解两种实现方式不仅有助于掌握二叉树遍历，还能加深对递归和栈的理解，为学习更复杂的树形结构算法打下坚实基础。