二叉树遍历

循环遍历(只有层次遍历用到了队，其他都是栈)

• 前序遍历
  1.使用一个栈来存储元素，刚开始的时候将栈顶元素压入栈
  2.当栈不为空的时候做如下操作：弹出栈顶元素并遍历，依次将出栈结点的右孩子和左孩子入栈

//非递归前序遍历二叉树
    public static void printTree1(Node root){
        SequenceStack<Node> stack=new SequenceStack<Node>();
        List<Node> list=new ArrayList<Node>();
        //首先先把根节点压栈
        stack.push(root);
        //当栈不为空的时候循环遍历
        while(!stack.isEmpty()){
            //弹出栈顶元素
            Node node=stack.pop();
            //遍历栈顶元素
            list.add(node);
            //如果栈顶元素的右孩子不为空，则进栈
            if(node.right!=null){
                stack.push(node.right);
            }
            //如果栈顶元素的左孩子不为空，则进栈
            if(node.left!=null){
                stack.push(node.left);
            }       
        }
        System.out.println(list);
}

• 中序遍历
  1.刚开始先把根节点压入栈，往后每次判断节点不为空则入栈
  2.弹出栈顶元素并遍历，判断栈顶元素是否存在右孩子结点，根据结果进行相应的操作~
  有：继续将右孩子结点压栈
  无：继续出栈

//采用非递归中序遍历二叉树
    public static void printTree(Node root){
        SequenceStack<Node> stack=new SequenceStack<Node>();
        List<Node> list=new ArrayList<Node>();
        Node node=root;
        //刚开始先把根节点压入栈，往后每次判断节点不为空则压栈
        do {
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            list.add(node);
            //如果出栈的结点存在右节点，则指向该节点
            if(node.right!=null){
                node=node.right;
            }else{//否则设置为空，下次循环继续出栈
                node=null;
            }//当栈不为空，或者当前节点引用不为空时循环
        } while (!stack.isEmpty()||node!=null);
        System.out.println(list);
    }

• 后序遍历
  1.将根节点以及左结点依次入栈
  2.获取栈顶元素，对栈顶元素进行右孩子判断，诺为空，则遍历栈顶元素并弹出栈，否则指向右孩子结点
  3.重复1-2两步
  重点：这里需要注意pre变量在遍历过程中的作用（下方代码有详细注释该变量的作用）

//非递归实现后序遍历
    public static void printTree2(Node root){
        SequenceStack<Node> stack=new SequenceStack<Node>();
        List<Node> list=new ArrayList<Node>();
        //定义两个节点变量node和pre（这里需要注意pre节点的作用，下方的注释有详细地介绍）
        Node node=root;
        Node pre=null;
        do {
            //将左结点一次压入栈
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            //获取栈顶节点
            node = stack.get();
            //如果栈顶节点的右孩子不为空，说明还得把右子树压入栈中，这里需要注意
            //node.right!=pre这个条件，因为我们在遍历的过程中，对于（子树）根节点的判断会存在两次
            //第一次是弹出左孩子节点后，对根节点进行是否有右孩子的判断，如果有，则将右孩子压栈
            //第二次是弹出右孩子节点后，这时候因为循环的原因（代码的原因），我们再次对根节点进行了右孩子判断，
            //所以这里就必须得判断该右孩子节点是否在之前的循环中已经判断过了，如果判断过了，则弹出根节点，否则压入右孩子节点。
            //总的来说，pre节点的作用是用来防止重复遍历右孩子节点的。
            if(node.right!=null&&node.right!=pre){
                //node指向右孩子节点
                node=node.right;
            }else{//只要有一个条件不满足则执行
                //弹出栈顶元素
                node=stack.pop();
                //遍历栈顶元素
                list.add(node);
                //将pre指向当前弹出的元素，用来做下次对根节点的再次判断时，右孩子不重复遍历的一个条件
                pre=node;
                //将node设置为null，防止根节点重复压入左孩子节点。
                node=null;
            }
            
        } while (node!=null||!stack.isEmpty());
        System.out.println(list);
    }

• 层次遍历
  先将根节点入队，当前节点是队头节点，将其出队并访问，如果当前节点的左节点不为空将左节点入队，如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。

public class PrintFromTopToBottom {
    public static class TreeNode{
        int val;
        TreeNode left=null;
        TreeNode right=null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list=new ArrayList<Integer>();  //存放结果
        Queue<TreeNode> queue= new LinkedList<TreeNode>();   //辅助队列
        if (root!=null){
            //根节点入队
            queue.offer(root);
        }
        //队列不为空，执行循环
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();
            list.add(node.val);     //将队列元素输出

            //如果有左节点，就把左节点加入
            if (node.left!=null){
                queue.offer(node.left);
            }
            //如果有右节点，就把右节点加入
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        return list;
    }
}

递归遍历

• 定义结点

public class TreeNode {
    public char value;
    public TreeNode left;
    public TreeNode right;
 
    TreeNode(char value) {
        this.value = value;
    }
 
    TreeNode(char value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

• 建立二叉树结构 image.png
• 递归遍历

public class Order {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TreeNode root = init();
 
        System.out.println("先序");
        ProOrder(root);
 
        System.out.println("中序");
        InOrder(root);
 
        System.out.println("后序");
        PostOrder(root);
 
    }
 
    /** 构造树 */
    public static TreeNode init() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B', null, a);
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D', b, c);
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F', e, null);
        TreeNode g = new TreeNode('G', null, f);
        TreeNode h = new TreeNode('H', d, g);
        return h;// root
    }
 
    /**
     * 递归前序遍历
     * 
     * @param tree
     */
    public static void ProOrder(TreeNode tree) {
        System.out.println(tree.value);
        if (tree.left != null) {
            ProOrder(tree.left);
        }
        if (tree.right != null) {
            ProOrder(tree.right);
        }
    }
 
    /**
     * 递归中序遍历
     * 
     * @param tree
     */
    public static void InOrder(TreeNode tree) {
 
        if (tree.left != null) {
            InOrder(tree.left);
        }
        System.out.println(tree.value);
        if (tree.right != null) {
            InOrder(tree.right);
        }
    }
 
    /**
     * 递归后顺遍历
     * 
     * @param tree
     */
    public static void PostOrder(TreeNode tree) {
 
        if (tree.left != null) {
            PostOrder(tree.left);
        }
 
        if (tree.right != null) {
            PostOrder(tree.right);
        }
        System.out.println(tree.value);
    }
}