C++实现二叉树中序遍历

二叉树的中序遍历是一种深度优先搜索（Depth-First Search, DFS）在二叉树中的应用，它按照特定顺序访问二叉树的节点，对于理解数据结构和算法至关重要。中序遍历遵循以下步骤： 1. **递归定义**： - 中序遍历的顺序是左子树 -> 根节点 -> 右子树。 - 当遍历到一个节点时，首先遍历其左子树（如果存在），然后访问当前节点，最后遍历右子树。 2. **迭代实现**： - 使用栈来辅助遍历，避免递归带来的栈溢出问题。以下是C++代码实现的迭代中序遍历方法： ```cpp class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); // 将根节点压入栈中 while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { // 将当前节点压入栈中，然后将右子节点（未访问）压入栈顶 st.push(node); st.push(NULL); if (node->right) st.push(node->right); // 右子树 // 跳过当前节点，先处理左子树 st.pop(); // 退出当前节点 } else { // 当栈顶节点为空或已访问完，取出并添加到结果列表 node = st.top(); st.pop(); result.push_back(node->val); } } return result; } }; ``` 在这个实现中，我们首先检查根节点是否为空，如果不为空则将其压入栈。然后进入一个循环，只要栈不为空，就从栈顶取出节点进行操作。当遇到非空节点时，先将当前节点及其右子节点压入栈，然后回溯到左子节点。当遍历到叶子节点时，将节点值加入结果列表，然后继续处理下一个节点。 3. **时间复杂度**： - 由于每层节点都被访问一次，时间复杂度为O(n)，其中n是二叉树的节点总数。 4. **空间复杂度**： - 最坏情况下，二叉树完全不平衡时，栈的高度等于树的高度，因此空间复杂度为O(h)，h为树的高度。 5. **应用场景**： - 中序遍历常用于构建二叉搜索树（如二叉查找树），因为它能保证节点值的有序性。 - 在实际编程中，它也常用于序列化和反序列化二叉树，以及解决某些与树形态相关的问题。 总结：二叉树的中序遍历是一种基础且实用的算法，它不仅加深了对数据结构的理解，还在许多实际场景中发挥着关键作用。通过理解和掌握迭代版本的中序遍历，程序员能够更高效地处理和操作二叉树数据结构。