《二叉树基础》二叉树的遍历-蒲公英云

前言：

·二叉树的深度优先遍历和宽度优先遍历是解决二叉树题目的基础，熟练的掌握二叉树的常见遍历方式可以让我们解决二叉树问题更加得心应手。

前言：

二叉树的前中后序遍历的递归形式

代码：

二叉树的前中后序遍历的非递归形式

用迭代实现二叉树的前序遍历

思路：

代码：

用迭代实现二叉树的后序遍历

思路：

代码：

用迭代实现二叉树的中序遍历

思路：

代码：

二叉树的宽度优先遍历

思路：

代码：

二叉树的前中后序遍历的递归形式

#

?：我们知道二叉树的前中后序遍历中，每个节点都会经过三次，我们在第一次来到每个节点的时候处理该节点就是前序遍历，第二次来到每个节点的时候处理该节点就是中序遍历，第三次来到

这个节点的时候处理该节点就是后序遍历，我们把这个规律称为递归序。

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

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

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

代码：

public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
//前序遍历
    public static void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val);//第一次来到的时候打印
        preOrder(root.left);
        preOrder(root.right);
    }
//中序遍历
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val);//第二次来到的时候打印
        inorder(root.right);
    }
//后序遍历
    public static void posOrder(TreeNode root){
        if(root==null){
            return;
        }
        posOrder(root.left);
        posOrder(root.right);
        System.out.println(root.val);//第三次来到的时候打印
    }

二叉树的前中后序遍历的非递归形式

?：由上文我们知道了递归序的概念，二叉树的前中后序遍历中每个节点都会来到三次，那递归是如何实现来到每个节点三次呢？答案是递归利用了系统栈，如果我们不用递归来实现二叉树的前中后序遍历就必须自己手动压栈来模拟系统栈。

用迭代实现二叉树的前序遍历

思路：

?准备一个栈：设计一个栈来模拟系统栈的功能

栈的规则如下

(1):每次弹出一个节点

(2):有右孩子将右孩子压入栈中

(3):有左孩子将左孩子压入栈中

(4):要保证先右孩子再左孩子

代码：

public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    //自己压栈来实现
    //规则
    //1:弹出栈顶
    //2:有右孩子压入右孩子
    //3:有左孩子压入左孩子
    //4:先右再左
    public static void pre(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode cur=stack.pop();
            System.out.print(cur.val+" ");
            if(cur.right!=null){
                stack.add(cur.right);
            }
            if(cur.left!=null){
                stack.add(cur.left);
            }
        }
        System.out.println();
    }

用迭代实现二叉树的后序遍历

思路：

?：学完前序遍历的代码后，我们可以通过一些改动将前序遍历改为后序遍历。

前序遍历是头节点-左子树-右子树的顺序。我们用迭代实现前序遍历的时候是弹出节点，先压入右孩子再压入左孩子，如果我们先压入左孩子再压入右孩子就能得到头节点-右子树

-左子树的遍历顺序，再把这个顺序逆序过来就是左子树-右子树-头节点的顺序。

那么我们如何逆序呢？

我们只需要头节点-右子树-左子树的遍历结果依次放入另外一个辅助栈中，再从栈中依次弹出所有元素，就得到了左子树-右子树-头节点的顺序。

代码：

public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static void posOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> help=new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode cur=stack.pop();
            help.add(cur);
            if(cur.left!=null){
                stack.add(cur.left);
            }
            if(cur.right!=null){
                stack.add(cur.right);
            }
        }
        while(!help.isEmpty()){
            System.out.print(help.pop().val+" ");
        }
        System.out.println();
    }

用迭代实现二叉树的中序遍历

思路：

?：中序遍历是左子树-头节点-右子树的遍历顺序。

要保证每一颗子树都是左子树-头节点-右子树的遍历顺序，所以我们遍历顺序是左到不能再左的时候打印节点，再去右树进行相同的操作，即我们将每一颗子树的左边界全压入栈中，弹出左到不能再左的节点后，对右子树进行相同的操作，之所以可以这样做是因为任意一颗二叉树是可以被左边界完全分解的。

代码：

public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    //规则cur从头开始
    //(1)cur!=null 在栈中压入cur，cur=cur.left扫描左边界
    //(2)cur==null 弹出栈顶元素，并打印，cur来到弹出元素的右子树上
    public static void inorder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            if(cur!=null){
                stack.add(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();
                System.out.print(cur.val+" ");
                cur=cur.right;
            }
        }
        System.out.println();
    }

二叉树的宽度优先遍历

思路：

?：二叉树的宽度优先遍历（也称层序遍历）的经典实现方式是通过队列来实现的，队列的使用规则是，从队列中弹出一个节点，有右孩子则压入右孩子，有左孩子则压入左孩子，这样每一层遍历结束后都可以将下一层压入队列。

代码：

//方法论：准备一个队列:在遍历每一层的时候，让下一层的节点入队列
    //规则1：每次从队列中弹出一个节点
    //2:有左孩子的让左孩子入队列
    //3:有有孩子则让右孩子入队列
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static void bfs(TreeNode head){
        if(head==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val);
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if(cur.right!=null){
                queue.add(cur.right);
            }
        }
        System.out.println();
    }