二叉树的遍历

前序遍历：根节点-左子树-右子树

中序遍历：左子树-根节点-右子树

后序遍历：左子树-右子树-根节点

层次遍历：队列作为辅助结构

1、二叉树的前序遍历

• 递归：

public void preOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + " -> ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
}

初始。

第一步：执行preOrderRecur（Node root）方法，访问节点A，打印“A”。

第二步：执行preOrderRecur（root.left）方法，访问节点B，不为空，打印“B”。

第三步：递归调用preOrderRecur（B.left）方法，访问节点D，不为空，打印“D”。

第四步：
（1）递归调用preOrderRecur（D.left）方法，D.left为空，返回；
（2）递归调用preOrderRecur（D.right）方法，访问节点H，打印“H”。

第五步：
（1）递归调用preOrderRecur（H.left）方法，此时H.left为空，返回；
（2）递归调用preOrderRecur（H.right）方法，此时H.right为空，返回；
（3）返回到上一级递归方法，即到打印“D”的方法中，这个方法也执行完毕，继续返回到打印“B”的方法中；
（4）递归调用preOrderRecur（B.right）方法，访问节点E，打印“E”。

第六步：
（1）递归调用preOrderRecur（E.right）方法，访问节点I，打印“I”。

第七步：
（1）递归调用preOrderRecur（I.left）方法，此时I.left为空，返回；
（2）递归调用preOrderRecur（I.right）方法，此时I.right为空，返回；
（3）返回上一级递归方法，即打印“E”的方法中，递归调用preOrderRecur（E.right）方法，访问节点J，打印“J”。

第八步：
（1）J的左右子树都为空，返回到打印“E”的方法中，该方法执行完毕；
（2）返回到打印“B”的方法中，该方法也执行完毕，接着向上返回到打印“A”的方法中；
（3）递归调用preOrderRecur（A.right）方法，访问节点C，打印“C”。

第九步：

第十步：

打印顺序为：ABDHEIJCFG

• 非递归:

public void preOrder() {
        if (root == null)
            return;
        Node current;
        //把LinkedList当栈使用
        LinkedList<Node> s = new LinkedList<Node>();
        s.addFirst(root);
        while (!s.isEmpty()) {
            current = s.removeFirst();
            System.out.print(current.data + " -> ");
            if (current.right != null)
                s.addFirst(current.right);
            if (current.left != null)
                s.addFirst(current.left);
        }
}

初始：

第一步：
（1）s.addFirst(root);

第二步：
（1）取出A，打印“A”；
（2）A的左右孩子都不为空，先放入右孩子C，在放入左孩子B。

第三步：
（1）取出B，打印“B”；
（2）B的左右孩子都不为空，先放入B的右孩子E，再放入一左孩子D。

第四步：
（1）取出D，打印“D”；
（2）D的左孩子为空，不放入，D的右孩子为H放入。

第五步：
（1）取出H，打印“H”；
（2）H的左、右孩子都为空，都不放入；

第六步：
（1）取出E，打印“E”；
（2）E的左、右孩子都不为空，先放入E的右孩子J，在放入E的左孩子I。

第七步：
（1）因为I、J没有左、右子孩子，所以都只取出，不放入。

第八步：
（1）取出C，打印“C”；
（2）放入C的右孩子G和左孩子F。

第九步：
（1）因为F、G没有左、右子孩子，所以都只取出，不放入。

打印顺序为：ABDHEIJCFG

2、二叉树的中序遍历

• 递归：

public void inOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);    //中序遍历左子树
        System.out.print(root.data + " -> ");
        inOrderRecur(root.right);    //最后中序遍历右子树
}

3、二叉树的后序遍历

• 递归：

public void postOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        postOrderRecur(root.left);    //后序遍历左子树
        postOrderRecur(root.right);    //再后序遍历右子树
        System.out.print(root.data + " -> ");
}