前序遍历

根节点-->左子树-->右子树

image.png

    /**
     * 前序遍历:通过栈保留待操作值
     */
    public static void preOrder(TreeNode head){
        if(head == null){
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.value + " ");
            if(treeNode.right != null){
                stack.push(treeNode.right);
            }
            if(treeNode.left != null){
                stack.push(treeNode.left);
            }
        }
        System.out.println();
    }

中序遍历

左子树-->根节点-->右子树

image.png

    /**
     * 中序遍历:当有结点时入栈,当没结点时出栈并输出
     */
    public static void midOrder(TreeNode head){
        if(head == null){
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        while(head != null || !stack.isEmpty()){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else {
                TreeNode treeNode = stack.pop();
                System.out.print(treeNode.value + " ");
                head = treeNode.right;
            }
        }
        System.out.println();
    }

后序遍历

左子树-->右子树-->根节点

image.png

    /**
     * 后序遍历:通过栈保留待操作值,类似于前序遍历
     */
    public static void postOrder(TreeNode head){
        if(head == null){
            return;
        }

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while(!stack1.isEmpty()){
            TreeNode treeNode = stack1.pop();
            stack2.push(treeNode);//头结点是最后一个
            if(treeNode.left != null){
                stack1.push(treeNode.left);
            }
            if(treeNode.right != null){
                stack1.push(treeNode.right);
            }
        }

        while(!stack2.isEmpty()){
            System.out.print(stack2.pop().value + " ");
        }
        System.out.println();
    }

层次遍历

不同层,从上到下;相同层,从左到右

image.png

    /**
     * 层次遍历:使用队列实现
     */
    public static void levelOrder(TreeNode head){
        if(head == null){
            return;
        }

        //deque:双端队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(head);

        while(!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            System.out.print(treeNode.value + " ");

            if(treeNode.left != null){
                queue.offer(treeNode.left);
            }
            if(treeNode.right != null){
                queue.offer(treeNode.right);
            }
        }
        System.out.println();
    }

测试结果

    public static TreeNode init(){
        TreeNode a = new TreeNode("A");
        TreeNode b = new TreeNode("B");
        TreeNode c = new TreeNode("C");
        TreeNode d = new TreeNode("D");
        TreeNode e = new TreeNode("E");
        TreeNode f = new TreeNode("F");
        TreeNode g = new TreeNode("G");
        TreeNode h = new TreeNode("H");
        TreeNode i = new TreeNode("I");
        TreeNode j = new TreeNode("J");
        TreeNode k = new TreeNode("K");

        a.left = b;
        a.right = c;

        b.left = d;
        b.right = e;

        d.left = h;
        d.right = i;

        e.right = j;

        c.left = f;
        c.right = g;

        f.right = k;

        return a;
    }

    public static void main(String[] args) {
        TreeNode head = init();

        //前序遍历
        preOrder(head);//A B D H I E J C F K G

        //中序遍历
        midOrder(head);//H D I B E J A F K C G

        //后序遍历
        postOrder(head);//H I D J E B K F G C A

        //层次遍历
        levelOrder(head);//A B C D E F G H I J K
    }