資料結構與算法：二叉樹的廣度優先周遊

一、廣度優先周遊

廣度優先周遊也叫層序周遊，顧名思義，就是二叉樹按照從根節點到葉子節點的層次關系，一層一層橫向周遊各 個節點。

二叉樹同一層次的節點之間是沒有直接關聯的，利用隊列可以實作。

二、實作思路

1、根節點1進入隊列

2、節點1出隊，輸出節點1，并得到節點1的左孩子節點2、右孩子節點3。讓節點2和節點3入隊

3、節點2出隊，輸出節點2，并得到節點2的左孩子節點4、右孩子節點5。讓節點4和節點5入隊

4、節點3出隊，輸出節點3，并得到節點3的右孩子節點6。讓節點6入隊

5、節點4出隊，輸出節點4，由于節點4沒有孩子節點，是以沒有新節點入隊

6、節點5出隊，輸出節點5，由于節點5同樣沒有孩子節點，是以沒有新節點入隊

7、節點6出隊，輸出節點6，節點6沒有孩子節點，沒有新節點入隊

二、代碼實作

/*
 * 層序周遊
 */
public void levelOrderTraversal(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if (node.leftChild != null) {
            queue.offer(node.leftChild);
        }
        if (node.rightChild != null) {
            queue.offer(node.rightChild);
        }
    }
}