中序遍历是怎么遍历的
中序遍历是二叉树的一种遍历方式，从左根右的顺序遍历整棵树。对于每个节点，中序遍历会先遍历它的左子节点，再遍历自身，最后遍历右子节点。这种遍历方式广泛应用于对树的搜索和排序算法中。那么，我们就来看一看中序遍历是怎么遍历的。
首先，我们需要理解中序遍历的原理。对于一个二叉树来说，其中每个节点都有左右两个子节点。如下图所示：
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
对于该二叉树，中序遍历的顺序是 4, 2, 5, 1, 6, 3, 7。我们可以这样来理解中序遍历：
- 遍历左子树，即先遍历节点 4。
- 遍历根节点 2。
- 继续遍历左子树，遍历节点 5。
- 遍历根节点 1。
- 遍历右子树，遍历节点 6。
- 遍历根节点 3。
- 继续遍历右子树，遍历节点 7。
从这个例子中，我们可以看出中序遍历的原理：遍历二叉树时，先遍历左子树，再遍历根节点，最后遍历右子树。这个顺序保证了遍历结果的有序性。
接下来，我们来看一下中序遍历的实现。
递归实现
最常见的中序遍历实现方式是递归实现。递归实现的代码简短易懂，如下：
```
void inorder(Node* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->val << endl;
inorder(root->right);
}
```
在这个代码中，函数 `inorder` 接收一个节点 `root`，表示以当前节点为根的子树。如果当前节点为 `nullptr`，说明子树为空，直接返回。否则，先递归遍历左子树（`root->left`），再打印根节点（`root->val`），最后递归遍历右子树（`root->right`）。
非递归实现
递归实现中序遍历的缺点是可能会造成函数调用栈溢出。因此，我们还需要另一种实现方式，即非递归实现。非递归实现不使用函数调用栈，而是使用栈这种数据结构来存储节点。
如下是中序遍历的非递归实现：
```
void inorder(Node* root) {
stack
Node* curr = root;
while (curr != nullptr || !st.empty()) {
while (curr != nullptr) {
st.push(curr);
curr = curr->left;
}
curr = st.top();
st.pop();
cout << curr->val << endl;
curr = curr->right;
}
}
```
这个代码使用了一个栈 `st`，来存储节点。开始时，将当前节点设置为根节点 `root`，然后进入循环。在循环中，首先遍历左子树，将所有左子节点入栈。当左子树遍历完后，弹出栈顶元素，并输出其值。如果当前节点有右子节点，将其设置为当前节点，继续遍历右子树。
在非递归实现中，我们使用了一个 while 循环对栈进行操作，从而遍历整个树，我们不再需要使用多个函数调用栈。
另外，中序遍历还有后继节点（inorder successor）的概念，即中序遍历中一个节点之后第一个被遍历的节点。后继节点通常用于删除节点和查找二叉树中一个节点的下一个节点。找到后继节点的方法是从当前节点开始向上查找，直到找到一个节点为其父节点的左孩子，这个节点就是后继节点。
