二叉树层序遍历

层序遍历序列为：ABCDEFG

思路：栈是先进后出的数据结构，而队列是先进先出的数据结构。

我们层序遍历，很明显，先遇到的节点先打印，不同于前中后序遍历，我们采用队列结构。

具体执行过程如下：

1、初始化——放入根节点

2、检查队列是否为空，如果是空则遍历完成

3、队列弹出元素，并打印

4、把弹出的元素的左孩子（如果存在的话）和右孩子（如果存在的话）放入队列。

5、重复2、3、4步。

下面是实现代码，按照思路实现即可。

  

   

    

     

    
    

     

      public void levelOrder() {
     
    
   

    

     

    
    

     

       Node<E> node =root;//根
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       LinkedList<Node<E>> list = new LinkedList<>();//队列
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       list.add(node);//放入根
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while(!list.isEmpty()) {
     
    
   

    

     

    
    

     

       node=list.poll();
     
    
   

    

     

    
    

     

       System.out.print(node.data);
     
    
   

    

     

    
    

     
 if(node.lchild!=null)
     
    
   

    

     

    
    

     

       list.offer(node.lchild);
     
    
   

    

     

    
    

     
 if(node.rchild!=null)
     
    
   

    

     

    
    

     

       list.offer(node.rchild);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

我们通过图来看一下实际的过程。

1、放入根节点

接下来循环执行2、3、4步：

2、检查队列不为空；

3、打印A；弹出

4、放入左右孩子B、C

继续循环执行2、3、4步：

2、检查队列不为空；

3、打印B；弹出

4、放入左右孩子D、E

继续循环执行2、3、4步：

2、检查队列不为空；

3、打印C；弹出

4、放入左右孩子F、G

最后四个一次弹出，不再压入，因为他们的孩子都是空。

遍历完成

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/102454497