二叉树的遍历

二叉树的遍历主要分为深度优先遍历(dfs)和广度优先遍历(bfs)。

深度优先遍历包括前序遍历、中序遍历和后序遍历，这三种遍历方式都有递归和迭代两种实现方式。

广度优先遍历也就是通常我们所说的层次遍历，通常用迭代方式实现。

前序、中序与后序都是从根节点的视角描述的，前序遍历顺序是根节点——左子树——右子树，中序是左子树——根节点——右子树，后序是左子树——右子树——根节点。

树的定义本身就是递归定义，所以采用递归方式实现树的前序、中序、后序遍历容易理解且代码简洁。方法的调用栈会保证树的完全遍历。

而通过非递归的方式实现遍历，则需要借助其他的数据结构，比如栈、队列、堆等。

递归和迭代本质上都是循环。

递归存在着方法调用方法自身。迭代暗示着循环的某次计算结果（输出）会作为下一次循环计算的参数（输入）。

1. 深度优先遍历

节点定义。

class TreeNode{
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int v){
		this.val=v;
	}
	
}

1.1 前序遍历

递归方式实现。

public void preOrderTraversal(TreeNode root){
    if(root != null){
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
}

迭代方式实现。

//利用 栈 模拟 递归过程 实现循环前序遍历二叉树

public void nonrecursivePreOrderTraversal(TreeNode root){
    if(root==null){
        return;
    }
    
    Deque<TreeNode> stack = new LinkedList<>();
    
   while(root != null || !stack.isEmpty()){
       while(root != null){
           System.out.print(root.val+" ");
           stack.push(root); //先访问，再入栈
           
           root=root.left;
       }
       
       if(!stack.isEmpty()){
            TreeNode root = stack.pop();    //出栈，并处理右子树
            root=root.right;
       }
   }
    
}

1.2 中序遍历

递归方式实现。

public void inOrderTraversal(TreeNode root){
    if(root != null){
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
}

迭代方式实现。

public void nonrecursiveInOrderTraversal(TreeNode root){
    
    if(root == null){
        return;
    }
    
    Deque<TreeNode> stack = new LinkedList<>();
    
    while( root != null || !stack.isEmpty()){
    
        while(root != null){
          stack.push(root);
          root = root.left;
        }
        
        if(!stack.isEmpty()){
            TreeNode root=stack.pop();  //出栈
            System.out.print(root.val+" ");
            root=root.right;    //处理右子树
        }
    }
    
    
}

1.3 后序遍历

递归方式实现。

public void postOrderTraversal(TreeNode root){
    if(root != null){
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }
}

迭代方式实现。

//后序遍历与前、中序遍历不太一样
//当前节点是否打印：它的右子树为 null ,或者它的右子树已经被访问了（游标标识）

public void nonrecursivePostOrderTraversal(TreeNode root){
    if(root==null) {return;}
    
    Deque<TreeNode> stack = new LinkedList<>();
    
    TreeNode node = root; //替换，使用node变量
    TreeNode lastVisit = root;
    
    while(node != null || !stack.isEmpty()){
        
        while(node != null){
            stack.push(node);
            node=node.left;
        }
        
        node=stack.peek();  //查看当前栈顶元素
        
        if(node.right == null || node.right==lastVisit){  //如果当前节点右子树为空或者右子树已经被访问
            System.out.print(node.val+" ");
            stack.pop();
            lastVisit=node;
            node=null;
        }else{  //否则，继续遍历右子树（保证遍历完全部节点）
            node=node.right;
        }
        
    }
}

2. 广度优先遍历(层次遍历)

通过迭代方式实现。

public void levelTraversal(TreeNode root){
    if(root==null){
        return;
    }
    
    Queue<TreeNode> queue=new LinkedList<>();
    
    queue.add(root);
    
    while(!queue.isEmpty()){
        TreeNode node=queue.remove();
        System.out.print(node.val+" ");
        
        if(node.left != null){
            queue.add(node.left);
        }
        
        if(node.right != null){
            queue.add(node.right);
        }
    }
    
}

这里可以对照着广度优先遍历的代码形式，重新描述一下深度优先遍历（非递归实现前序遍历）。

下述这种遍历方式不具备扩展性，类似于图的深度优先遍历（DFS）。这种方式应该是对先序遍历的一种特殊实现，思路清晰明了，在中序和后序方式中不适用。

public void depthOrderTraversal(TreeNode root){
    if(root==null){
        return;
    }
    
    Deque<TreeNode> stack=new LinkedList<>();
    
    stack.push(root);
    
    while(!stack.isEmpty()){
        
        TreeNode node=stack.pop();
        System.out.print(node.val+" ");
        
        if(node.right != null){
            stack.push(node.right);
        }
        
        if(node.left != null){
            stack.push(node.left);
        }
        
    }
    
}

3. 参考资料

二叉树遍历(先序、中序、后序)

JAVA下实现二叉树的先序、中序、后序、层序遍历（递归和循环）