[科普中國]-逐層遍歷

二叉樹的層次遍歷 ，顧名思義就是指從二叉樹的第一層（根節(jié)點）開始，從上至下逐層遍歷，在同一層中，則按照從左到右的順序?qū)?jié)點逐個訪問。在逐層遍歷過程中，按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進行訪問。

算法思想用一個隊列保存被訪問的當前節(jié)點的左右孩子以實現(xiàn)層序遍歷。

在進行層次遍歷的時候，設(shè)置一個隊列結(jié)構(gòu)，遍歷從二叉樹的根節(jié)點開始，首先將根節(jié)點指針入隊列，然后從隊頭取出一個元素，每取一個元素，執(zhí)行下面兩個操作：

1、訪問該元素所指向的節(jié)點

2、若該元素所指節(jié)點的左右孩子節(jié)點非空，則將該元素所指節(jié)點的左孩子指針和右孩子指針順序入隊。此過程不斷進行，當隊列為空時，二叉樹的層次遍歷結(jié)束。

實現(xiàn)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 list=new ArrayList(); private Queue queue=new LinkedList(); public ArrayList PrintFromTopToBottom(TreeNode root) { if(root!=null){ queue.offer(root); } while(queue.peek()!=null){ removeNext(); } return list; } /* *每次在隊列中取出一個節(jié)點，并將其值插入到List中， *此外每次取出一個節(jié)點需要把這個節(jié)點的子節(jié)點插入隊列 */ 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; }}1

C++語言由于遍歷中所使用的數(shù)據(jù)結(jié)構(gòu)是一個隊列而不是棧，因此寫一個按層遍歷的遞歸程序很困難。如下程序用來對二叉樹進行逐層遍歷，它采用了隊列數(shù)據(jù)結(jié)構(gòu)。隊列中的元素指向二叉樹節(jié)點。當然，也可以采用公式化隊列。

template void LevelOrder(BinaryTreeNode *t){// 對* t逐層遍歷L i n k e d Q u e u e Q;while (t) {Visit(t); // 訪問t// 將t的右孩子放入隊列if (t->LeftChild) Q.Add(t->LeftChild);if (t->RightChild) Q.Add(t->RightChild);// 訪問下一個節(jié)點try {Q.Delete(t);}catch (OutOfBounds) {return;}}}程序中，僅當樹非空時，才進入w h i l e循環(huán)。首先訪問根節(jié)點，然后把其子節(jié)點加到隊列中。當隊列添加操作失敗時，由Add引發(fā)NoMem異常，由于沒有捕獲該異常，因此當異常發(fā)生時LevelOrder函數(shù)將退出。在把t的子節(jié)點加入隊列后，要從隊列中刪除t元素。若隊列為空，則由Delete引發(fā)OutOfBounds異常，這由catch語句來處理。因為一個空隊列意味著遍歷的結(jié)束，所以執(zhí)行return語句。若隊列非空，則Delete把所刪除的元素返回至變量t。被刪除的元素指向下一個欲訪問的節(jié)點。2

復雜性分析設(shè)二叉樹中元素數(shù)目為n。逐層遍歷的空間復雜性均為O (n)，時間復雜性為O(n)。當t為滿二叉樹時，逐層遍歷所需要的隊列空間為O(n)。每個遍歷算法花在樹中每個節(jié)點上的時間為O(1) (假設(shè)訪問一個節(jié)點的時間為( 1 ) )。2

本詞條內(nèi)容貢獻者為:

王偉 - 副教授 - 上海交通大學