二叉树遍历

二叉树的遍历方式分别为：前序遍历、中序遍历、后序遍历。

前序遍历：

先访问根节点，再访问左节点，最后访问右节点

中序遍历：

先访问左节点，再访问根节点，最后访问右节点

后序遍历：

先访问左节点，再访问右节点，最后访问根节点
也就是根节点的访问顺序。

先定义一个二叉树节点

/**
 * Definition for a binary tree node.
 */
public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

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

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

这里手动创建一个二叉树用于展示

    /**
     * 创建一个二叉树
     */
    public static TreeNode createBinaryTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node8;
        node5.left = node9;

        node3.left = node6;
        node3.right = node7;
        node6.left = node10;
        return node1;
    }

构建完成的二叉树结构如下

binaryTree.png

递归方式

前序遍历

    /**
     * 前序遍历
     * 根->左->右
     * 输出 1 2 4 8 5 9 3 6 10 7
     */
    public static void preorderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

中序遍历

    /**
     * 中序遍历
     * 左->根->右
     * 输出 8 4 2 9 5 1 10 6 3 7
     */
    public static void inorderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

后序遍历

    /**
     * 后序遍历
     * 左->右->根
     * 输出 8 4 9 5 2 10 6 7 3 1
     */
    public static void postorderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }

测试代码

    public static void main(String[] args) {

        TreeNode root = createBinaryTree();

        // 1 2 4 8 5 9 3 6 10 7
        preorderTraversal(root);
        System.out.println();
        // 8 4 2 9 5 1 10 6 3 7
        inorderTraversal(root);
        System.out.println();
        // 8 4 9 5 2 10 6 7 3 1
        postorderTraversal(root);
    }

非递归方式

这里新建一个类用于记录节点状态

/**
 * 记录节点状态
 */
public class Record {

    //  true 表示输出 false 表示继续访问
    boolean flag;
    TreeNode node;

    public Record(TreeNode node, boolean flag){
        this.flag = flag;
        this.node = node;
    }
}

前序遍历

    /**
     * 前序遍历
     * 根->左->右
     * 输出 1 2 4 8 5 9 3 6 10 7
     */
    public static void preorderTraversal(TreeNode root){

        if (root == null){
            return;
        }
        Stack<Record> stack = new Stack<>();
        stack.push(new Record(root,false));

        while (!stack.isEmpty()){
            Record Record = stack.pop();
            if (Record.flag){
                System.out.print(Record.node.val + " ");
            }else {
                if (Record.node.right != null){
                    stack.push(new Record(Record.node.right,false));
                }
                if (Record.node.left != null){
                    stack.push(new Record(Record.node.left,false));
                }
                stack.push(new Record(Record.node,true));
            }
        }
    }

中序遍历

    /**
     * 中序遍历
     * 左->根->右
     * 输出 8 4 2 9 5 1 10 6 3 7
     */
    public static void inorderTraversal(TreeNode root){

        if (root == null){
            return;
        }
        Stack<Record> stack = new Stack<>();
        stack.push(new Record(root,false));

        while (!stack.isEmpty()){
            Record Record = stack.pop();
            if (Record.flag){
                System.out.print(Record.node.val + " ");
            }else {
                if (Record.node.right != null){
                    stack.push(new Record(Record.node.right,false));
                }
                stack.push(new Record(Record.node,true));
                if (Record.node.left != null){
                    stack.push(new Record(Record.node.left,false));
                }

            }
        }
    }

后序遍历

    /**
     * 后序遍历
     * 左->右->根
     * 输出 8 4 9 5 2 10 6 7 3 1
     */
    public static void postorderTraversal(TreeNode root){

        if (root == null){
            return;
        }
        Stack<Record> stack = new Stack<>();
        stack.push(new Record(root,false));

        while (!stack.isEmpty()){
            Record Record = stack.pop();
            if (Record.flag){
                System.out.print(Record.node.val + " ");
            }else {
                stack.push(new Record(Record.node,true));
                if (Record.node.right != null){
                    stack.push(new Record(Record.node.right,false));
                }
                if (Record.node.left != null){
                    stack.push(new Record(Record.node.left,false));
                }
            }
        }
    }

其实同递归方式一样只需要改变节点输出位置即可。

层序遍历

二叉树还有一种遍历方式层序遍历，即逐层地从左到右访问所有节点。与前三种方式不同这里需要借助队列先进先出的特点。
具体思路是在队列中每取到一个节点会把该节点的左右子节点分别添加到队列中

    /**
     * 层序遍历
     * 输出 1 2 3 4 5 6 7 8 9 10
     */
    public static void levelOrderTraveral(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        // offer 把根节点添加到队列中
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 移除队列头部并打印
            TreeNode treeNode = queue.poll();
            System.out.print(treeNode.val + " ");
            // 把左节点添加到队列中
            if (treeNode.left != null) {
                queue.offer(treeNode.left);
            }
            // 把右节点添加到队列中
            if (treeNode.right != null) {
                queue.offer(treeNode.right);
            }
        }
    }