深入理解C++中序遍历（手把手教你实现二叉树中序遍历算法）

C++中如何定义二叉树节点？

在实现遍历之前，我们需要先定义一个二叉树节点的结构。通常使用结构体（struct）来表示：

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

递归实现中序遍历

最直观的方式是使用递归。根据“左→根→右”的顺序，我们可以轻松写出如下代码：

#include <iostream>#include <vector>using namespace std;// 中序遍历函数（递归）void inorderTraversal(TreeNode* root, vector<int>& result) {    if (root == nullptr) {        return;    }        // 先遍历左子树    inorderTraversal(root->left, result);        // 访问根节点    result.push_back(root->val);        // 再遍历右子树    inorderTraversal(root->right, result);}// 使用示例int main() {    // 构建一个简单的二叉树    //       1    //        \    //         2    //        /    //       3    TreeNode* root = new TreeNode(1);    root->right = new TreeNode(2);    root->right->left = new TreeNode(3);        vector<int> result;    inorderTraversal(root, result);        // 输出结果：1 3 2    for (int val : result) {        cout << val << " ";    }    cout << endl;        return 0;}

这段代码清晰地体现了中序遍历递归实现的核心思想：先递归处理左子树，再处理当前节点，最后递归处理右子树。

非递归实现（使用栈）

虽然递归写法简洁，但在某些场景下（如树很深时）可能导致栈溢出。因此，我们也可以使用显式栈来模拟递归过程：

#include <iostream>#include <vector>#include <stack>using namespace std;vector<int> inorderTraversalIterative(TreeNode* root) {    vector<int> result;    stack<TreeNode*> stk;    TreeNode* current = root;        while (current != nullptr || !stk.empty()) {        // 一直向左走到底，并将路径上的节点入栈        while (current != nullptr) {            stk.push(current);            current = current->left;        }                // 弹出栈顶（即最左节点）        current = stk.top();        stk.pop();                // 访问该节点        result.push_back(current->val);                // 转向右子树        current = current->right;    }        return result;}

总结

通过本教程，你已经掌握了C++中序遍历的两种实现方式：递归与非递归。无论是面试还是实际开发，二叉树中序遍历都是非常基础且重要的知识点。建议你动手编写并调试代码，加深理解。

记住，学习数据结构的关键在于多练习、多思考。希望这篇教程能帮助你在C++编程和算法学习的道路上更进一步！