本文共 3957 字，大约阅读时间需要 13 分钟。

JAVA实现二叉树的层次遍历问题

所谓二叉树的层次遍历顺序：首先访问根节点，接着访问层数1上的节点，随后访问层数2上的节点，依次类推。

层次遍历：A、B、C、D、E、null，F，G，null

算法设计

1、首先定义树节点

public class TreeNode {    int data; //节点值    TreeNode leftChild; //左子树节点    TreeNode rightChild; //右子树节点    //构造方法    TreeNode(){        this.leftChild=null;        this.rightChild=null;        this.data=-1;    }    //构造方法    TreeNode(int data){        this.leftChild=null;        this.rightChild=null;        this.data=data;    }    //构造方法    public TreeNode(int data, TreeNode leftChild, TreeNode rightChild) {        this.data = data;        this.leftChild = leftChild;        this.rightChild = rightChild;    }    //以下为get***和set***方法    public int getData() {        return data;    }    public void setData(int data) {        this.data = data;    }    public TreeNode getLeftChild() {        return leftChild;    }    public void setLeft(TreeNode leftChild) {        this.leftChild = leftChild;    }    public TreeNode getRightChild() {        return rightChild;    }    public void setRight(TreeNode rightChild) {        this.rightChild = rightChild;    }}

2、层次遍历算法

/*     * 二叉树的层次遍历     * */    public static ArrayList
   
    
     > levelOrder(TreeNode root){        ArrayList
     
      
       > result = new ArrayList
       
        
         >(); if(root == null){ return result; } Queue
         
           queue = new LinkedList
          
           (); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList
           
             level = new ArrayList
            
             (); for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.data); if(node.leftChild != null){ queue.offer(node.leftChild); } if(node.rightChild != null){ queue.offer(node.rightChild); } } result.add(level); } System.out.println(result); return result; }
            
           
          
         
        
       
      
     
    
   

3、测试代码

以下面的数组创建一颗二叉树，二叉树的形态如图所示：

层次遍历代码

public class CreateBinaryTree {    private int[] array = {
  3,9,20,0,0,15,7};    private static List
   
     nodeList = null;      public void createBinTree() {          nodeList = new LinkedList
    
     ();          // 将一个数组的值依次转换为Node节点          for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {              nodeList.add(new TreeNode(array[nodeIndex]));          }          // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树          for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {              // 左孩子              nodeList.get(parentIndex).leftChild = nodeList                      .get(parentIndex * 2 + 1);              // 右孩子              nodeList.get(parentIndex).rightChild = nodeList                      .get(parentIndex * 2 + 2);          }          // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理          int lastParentIndex = array.length / 2 - 1;          // 左孩子          nodeList.get(lastParentIndex).leftChild = nodeList                  .get(lastParentIndex * 2 + 1);          // 右孩子,如果数组的长度为奇数才建立右孩子          if (array.length % 2 == 1) {              nodeList.get(lastParentIndex).rightChild = nodeList                      .get(lastParentIndex * 2 + 2);          }      }      /*     * 二叉树的层次遍历     * */    public static ArrayList
     
      
       > levelOrder(TreeNode root){        ArrayList
       
        
         > result = new ArrayList
         
          
           >(); if(root == null){ return result; } Queue
           
             queue = new LinkedList
            
             (); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList
             
               level = new ArrayList
              
               (); for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.data); if(node.leftChild != null){ queue.offer(node.leftChild); } if(node.rightChild != null){ queue.offer(node.rightChild); } } result.add(level); } System.out.println(result); return result; } public static void main(String[] args) { // TODO Auto-generated method stub CreateBinaryTree createBinaryTree=new CreateBinaryTree(); createBinaryTree.createBinTree(); TreeNode root = nodeList.get(0); System.out.println("二叉树的层次遍历为："); levelOrder(root); System.out.println("------------------------------------"); }}
              
             
            
           
          
         
        
       
      
     
    
   

（完）