二叉树的遍历方式【迭代和递归】

二叉树的广度遍历和深度遍历

对于二叉树的遍历：分为二叉树的广度遍历和深度遍历，所谓广度遍历即是迭代的方式进行遍历，深度遍历即使用递归的方式进行递归遍历

1丶深度遍历

分为三种

前序遍历：先输出父节点，再遍历左子树和右子树

中序遍历：先遍历左子树，再输出父节点，再遍历右子树

后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

在讲递归遍历之前，我们先使用递归遍历遍历一下单链表（这里是为了更好地理解遍历二叉树）

    public void show(Node node){
        System.out.println(node);
        if(node.next != null){
            show(node.next);
        }
    }

对于上面的简单递归代码，这里我们是学习思想，正常情况不会使用递归遍历单链表（耗性能）

对于上面的递归遍历单链表，联想二叉树：对于二叉树的遍历：和单链表的递归遍历一样，多一个节点而已

1丶前序遍历

   public void Pre_list(A_Node node){
   		System.out.print(node.element+"\t");
        if(node.left!=null){
            Pre_list(node.left);
        }
        if(node.right != null){
            Pre_list(node.right);
        }
    }

2丶中序遍历

   public void Middle_list(A_Node node){
        if(node.left!=null){
            Middle_list(node.left);
        }
        System.out.print(node.element+"\t");
        if(node.right != null){
            Middle_list(node.right);
        }
    }

3丶后续遍历

   public void after_list(A_Node node){
        if(node.left!=null){
            after_list(node.left);
        }
        if(node.right != null){
            after_list(node.right);
        }
         System.out.print(node.element+"\t");
    }

对于上面的理解以后，对于任何多节点的树（B树）的遍历都能使用类似递归遍历……

2丶广度遍历

所谓广度遍历就是指一层一层进行遍历（1~5层）

对于广度遍历的实现是使用队列这个数据结构进行实现
代码如下

    public void Level_OrderTraversal(AVL_Node root){
        Queue<AVL_Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            AVL_Node poll = queue.poll();
            System.out.println(poll.element+"\t");
            if(poll.left!=null){
                queue.offer(poll.left);
            }
            if(poll.right!=null){
                queue.offer(poll.right);
            }
        }
    }