package test;

import java.util.LinkedList;
import java.util.Queue;

/**
* 内容：二叉树的层次遍历
* 需要借助队列这个数据结构，直接import就可以了
*   1.首先将根节点放入队列中。
    2.当队列为非空时，循环执行步骤3到步骤5，否则执行6；
    3.出队列取得一个结点，访问该结点；
    4.若该结点的左子树为非空，则将该结点的左子树入队列；
    5.若该结点的右子树为非空，则将该结点的右子树入队列；
    6.结束。
* Created by fc.w on 2018/4/17.
*/
public class BinTree {

   private char data;
   private BinTree lchild;   //左孩子
   private BinTree rchild;  //右孩子

   private BinTree(char c) {
       data = c;
   }

   public static void BFSOrder(BinTree T) {
       if (null == T) return;
       //队列小知识：使用offer和poll优于add和remove之处在于它们返回值可以判断成功与否，而不抛出异常
       Queue<BinTree> queue = new LinkedList<BinTree>();
       queue.offer(T); //算法1：根结点进入队列
       while (!queue.isEmpty()) { //算法2：若队列非空，循环执行步骤 3-5，否则执行步骤6
           T = queue.poll();      //算法3：将一个结点出队列，并访问该结点
           System.out.print(T.data);
           if (T.lchild != null)  //算法4：若该结点的左子树为非空，则将该结点的左孩子结点入队列；
               queue.offer(T.lchild);
           if (T.rchild != null)  //算法5：若该结点的左子树为非空，则将该结点的右孩子结点入队列；
               queue.offer(T.rchild);
       }
       //步骤6结束
   }

   public static void main(String[] args) {
       BinTree b1 = new BinTree('a');
       BinTree b2 = new BinTree('b');
       BinTree b3 = new BinTree('c');
       BinTree b4 = new BinTree('d');
       BinTree b5 = new BinTree('e');
       BinTree b6 = new BinTree('f');
       BinTree b7 = new BinTree('g');

       /**
        *      a
        *    /   \
        *   b     c
        *  / \   / \
        * d   e f   g
        */
       b1.lchild = b2;
       b1.rchild = b3;
       b2.lchild = b4;
       b2.rchild = b5;
       b3.lchild = b6;
       b3.rchild = b7;

       BinTree.BFSOrder(b1);
       System.out.println();
   }

}