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

中序遍历的递归实现

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

首先访问根节点，判断根节点是否有左孩子，如果有，进行第二步；如果没有，跳到第三步；
访问左孩子，继续判断当前节点是否有左孩子，如果有则继续访问其左孩子，直到某节点的左孩子为空
判断是否有右孩子，如果有，则继续判断当前节点是否有左孩子，一直到某节点没有左孩子为止
把第二步访问的节点做为当前节点（该节点无左孩子，如图中的15节点），按照规则，下一步应该访问其右孩子
返回到第四部节点的双亲节点（15的双亲节点是5），并设为当前访问的节点，下一步访问的是其右孩子（这里5没有右孩子）
继续访问第五步访问节点的双亲节点（5的双亲节点是6），下一步仍然访问其右孩子。
左子树访问完毕，继续第三步中右子树的访问，步骤与上面一直，最终每个节点都将访问一遍

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

二叉树

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

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

package com.rhwayfun.algorithm.tree;

public class TravelTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public void inOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        inOrderTraverse(node.left);
        System.out.print(node.val + " ");
        inOrderTraverse(node.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);
        TreeNode node7 = new TreeNode(15);
        TreeNode node8 = new TreeNode(24);
        TreeNode node9 = new TreeNode(30);
        TreeNode node10 = new TreeNode(28);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node3.left = node7;
        node7.right = node8;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node5.left = node9;
        node6.right = node10;

        new TravelTree().inOrderTraverse(root);
    }
}

中序遍历的非递归实现

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

public void inOrderTraverse2(TreeNode node){
        Stack<TreeNode> s = new Stack<TreeNode>();
        while(node != null || !s.isEmpty()){
            //遍历左子树
            while(node != null){
                s.push(node);
                node = node.left;
            }
            //遍历右子树
            if(!s.isEmpty()){
                node = s.pop();
                System.out.print(node.val + " ");
                node = node.right;
            }
        }
    }

相关文章：