二叉树中序遍历次序

二叉树是一种常用的数据结构，其遍历方式有前序遍历、中序遍历、后序遍历等多种方式，其中，中序遍历是一种重要的遍历方式。本文将从多个角度对二叉树中序遍历次序进行分析。

一、什么是中序遍历

中序遍历是二叉树遍历方式中的一种，它的遍历顺序是先遍历左子树，再遍历根节点，最后遍历右子树。中序遍历的执行顺序为“左子树→根节点→右子树”。中序遍历是按照根节点的大小顺序输出节点的，它可以将任意一棵二叉树转化为一个递增的序列。

二、中序遍历的实现方式

中序遍历有递归和非递归两种实现方式。

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 stack = new 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。通过这两序列可以唯一重建出原来的二叉树。

四、总结

中序遍历是二叉树中的一种重要遍历方式，它通过遍历左子树、根节点、右子树的方式输出节点。中序遍历可以通过递归和非递归两种方式实现。中序遍历有很多应用，包括二叉搜索树和二叉树的重建等。