逐層遍歷是計算機科學術語。二叉樹的層次遍歷 ，顧名思義就是指從二叉樹的第一層（根節點）開始，從上至下逐層遍歷，在同一層中，則按照從左到右的順序對節點逐個訪問。在逐層遍歷過程中，按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進行訪問。
基本介紹
- 中文名：逐層遍歷
- 外文名：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。被刪除的元素指向下一個欲訪問的節點。
