二叉树遍历算法之二：中序遍历

中序遍历的递归实现

中序遍历遍历指的是先访问二叉树中节点的左孩子，再访问当前节点，最后再访问其右孩子。具体访问步骤如下：

首先访问根节点，判断根节点是否有左孩子，如果有，进行第二步；如果没有，跳到第三步；

访问左孩子，继续判断当前节点是否有左孩子，如果有则继续访问其左孩子，直到某节点的左孩子为空

判断是否有右孩子，如果有，则继续判断当前节点是否有左孩子，一直到某节点没有左孩子为止

把第二步访问的节点做为当前节点（该节点无左孩子，如图中的15节点），按照规则，下一步应该访问其右孩子

返回到第四部节点的双亲节点（15的双亲节点是5），并设为当前访问的节点，下一步访问的是其右孩子（这里5没有右孩子）

继续访问第五步访问节点的双亲节点（5的双亲节点是6），下一步仍然访问其右孩子。

左子树访问完毕，继续第三步中右子树的访问，步骤与上面一直，最终每个节点都将访问一遍

仍然以上一篇博客中前序遍历的例子作为说明：

按照中序遍历的访问规则，最终的输出序列应该是15，24，5，6，7，8，30，9，10，11，28。

可以发现这是一个递归过程，其递归代码也很简单，代码如下：

中序遍历的非递归实现

下面我们讨论一下非递归实现，与上一篇前序遍历的非递归实现由一些类是，主要的访问次序的改变，所以只需要在前面代码的基础上做一些适当修改就可以了，下面是对中序遍历代码的实现（经测试可用）：