二叉树中序遍历次序
二叉树是一种常用的数据结构，其遍历方式有前序遍历、中序遍历、后序遍历等多种方式，其中，中序遍历是一种重要的遍历方式。本文将从多个角度对二叉树中序遍历次序进行分析。
一、什么是中序遍历
中序遍历是二叉树遍历方式中的一种，它的遍历顺序是先遍历左子树，再遍历根节点，最后遍历右子树。中序遍历的执行顺序为“左子树→根节点→右子树”。中序遍历是按照根节点的大小顺序输出节点的，它可以将任意一棵二叉树转化为一个递增的序列。
二、中序遍历的实现方式
中序遍历有递归和非递归两种实现方式。
1. 递归方式
递归方式是中序遍历的最常见实现方式，其代码实现如下：
```
void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.println(root.val);
inOrderTraversal(root.right);
}
```
2. 非递归方式
非递归方式是通过栈来实现的，它将中序遍历过程分为两步：
- 第一步，将所有左节点入栈，并找到最左节点。
- 第二步，将左节点出栈，并将右节点入栈，右节点再执行步骤一。
非递归方式的代码实现如下：
```
void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack
TreeNode curNode = root;
while (curNode != null || !stack.isEmpty()) {
//将所有左节点入栈，并找到最左节点
while (curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
//将左节点出栈，并将右节点入栈
TreeNode node = stack.pop();
System.out.println(node.val);
curNode = node.right;
}
}
```
三、中序遍历的应用
1. 二叉搜索树
中序遍历可以将任意一棵二叉树转化为一个递增序列，这一特性在二叉搜索树中得到了广泛的应用。二叉搜索树是一种左子节点小于根节点，右子节点大于根节点的二叉树。通过中序遍历可以将一个无序的数组构建为一棵二叉搜索树。
2. 二叉树的重建
通过中序遍历和前序遍历可以重建出一棵二叉树。比如有这样一棵二叉树：
它的中序遍历为5→3→8→2→6→9→4→7，前序遍历为4→2→3→5→8→6→9→7。通过这两序列可以唯一重建出原来的二叉树。
四、总结
中序遍历是二叉树中的一种重要遍历方式，它通过遍历左子树、根节点、右子树的方式输出节点。中序遍历可以通过递归和非递归两种方式实现。中序遍历有很多应用，包括二叉搜索树和二叉树的重建等。
