二叉樹的層次遍歷 ，顧名思義就是指從二叉樹的第一層（根節點）開始，從上至下逐層遍歷，在同一層中，則按照從左到右的順序對節點逐個訪問。在逐層遍歷過程中，按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進行訪問。
基本介紹
- 中文名：逐層遍歷
- 外文名：Traversal by layer by layer
- 遍歷起點：二叉樹的根節點
- 遍歷方式：從頂層到底層的次序訪問樹中元素
- 同層遍歷：從左到右進行訪問
- 套用學科：計算機科學、測繪科學
算法思想,實現,Java語言,C++語言,複雜性分析,
算法思想
用一個佇列保存被訪問的當前節點的左右孩子以實現層序遍歷。
在進行層次遍歷的時候，設定一個佇列結構，遍歷從二叉樹的根節點開始，首先將根節點指針入佇列，然後從隊頭取出一個元素，每取一個元素，執行下面兩個操作：
1、訪問該元素所指向的節點
2、若該元素所指節點的左右孩子節點非空，則將該元素所指節點的左孩子指針和右孩子指針順序入隊。此過程不斷進行，當佇列為空時，二叉樹的層次遍歷結束。
實現
Java語言
import java.util.*;class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }public class Solution { private ArrayList<Integer> list=new ArrayList<Integer>(); private Queue<TreeNode> queue=new LinkedList<TreeNode>(); public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { if(root!=null){ queue.offer(root); } while(queue.peek()!=null){ removeNext(); } return list; } /* *每次在佇列中取出一個節點，並將其值插入到List中， *此外每次取出一個節點需要把這個節點的子節點插入佇列 */ public void removeNext(){ TreeNode temp=queue.poll(); if(temp!=null){ list.add(temp.val); if(temp.left!=null){ queue.offer(temp.left); } if(temp.right!=null){ queue.offer(temp.right); } } else return; }}C++語言
template <class T>void LevelOrder(BinaryTreeNode<T> *t){// 對* t逐層遍歷L i n k e d Q u e u e < B i n a r y TreeNode<T>*> Q;while (t) {Visit(t); // 訪問t// 將t的右孩子放入佇列if (t->LeftChild) Q.Add(t->LeftChild);if (t->RightChild) Q.Add(t->RightChild);// 訪問下一個節點try {Q.Delete(t);}catch (OutOfBounds) {return;}}}程式中，僅當樹非空時，才進入w h i l e循環。首先訪問根節點，然後把其子節點加到佇列中。當佇列添加操作失敗時，由Add引發NoMem異常，由於沒有捕獲該異常，因此當異常發生時LevelOrder函式將退出。在把t的子節點加入佇列後，要從佇列中刪除t元素。若佇列為空，則由Delete引發OutOfBounds異常，這由catch語句來處理。因為一個空佇列意味著遍歷的結束，所以執行return語句。若佇列非空，則Delete把所刪除的元素返回至變數t。被刪除的元素指向下一個欲訪問的節點。
