數(shù)據(jù)結構課件：第4章 樹1

1、4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應用第四章 樹樹結構在客觀世界中大量存在，如家譜、行政組織機構等都可用樹形象地表示。JoeJohnMaryAnnChrisSueMaryMary企業(yè)管理機構 在層次中地位最高的人(此處為總裁)在圖中位置最高。在層次中地位次之的(即副總裁)在圖中位于總裁之下等等。副總裁為總裁的下屬，總裁是他們的上級。每個副總裁都有自己的下屬，而其下屬又有自己的下屬。企業(yè)管理結構總裁財務副總裁市場副總裁開發(fā)副總裁銷售副總裁. 遞歸定義定義4.1： 一個樹（或樹形）就是一個有限非空的結點集合T，其中：有一個特別標出的被稱為該樹（

2、或樹形）之根root(T)的結點；其余結點（根除外）被分成m 0 個不相交的集合T1，T2，Tm，且T1，T2，Tm又都是樹（或樹形）。樹（或樹形）T1，T2，Tm被稱作root(T)的子樹（或子樹形）。一、樹的定義圖4.1為一棵由根結點A出發(fā)的樹，其中，A有三個子結點B、C和D；B有一個子結點E；E有一個子結點F；C有兩個子結點G和H；D有一個子結點I； F，G，H，I是葉結點，因為它們沒有子結點。從A到F的路徑為A-B-E-F。AECDBIHGF圖4.1 樹EBF（A）G（B）CHG（C）圖4.2 子樹 若斷掉一個結點與其父結點的連接，把該結點和它的子孫們單獨拿出，就是一棵以該結點為根結點

3、的樹，我們稱之為“子樹”。圖4.1.2中的（A）、（B）、（C）均是圖4.1所示樹的子樹。樹的相關術語1度一個結點的子結點的數(shù)目，稱為該結點的度或次數(shù)。一棵樹的度為maxi=1, n D (i)，其中n為樹中結點總數(shù)，i指樹中的第i個結點，D(i)表結點i的度。2葉結點、分支結點度為0的結點被稱為葉結點；度0的結點被稱為分支結點。在圖4.1中：B有一個子結點E，度為1；A有三個子結點B、C和D（換言之，A是B、C和D的父結點），度為3，故這棵樹的度也為3 .3結點的層數(shù)樹形T中結點的層數(shù)遞歸定義如下： root(T)層數(shù)為零； 其余結點的層數(shù)為其前驅結點的層數(shù)加1 .AECDBIHGF層次0層

4、次1層次2層次3樹的層數(shù)4路徑樹形中結點間的連線被稱為邊。若樹形T中存在結點序列vm vm+1 vmk，1 k T的最大層數(shù)，滿足vi+1是vi（m i mk1）的子結點，則稱此結點序列為vm到vmk的路徑，該路徑所經(jīng)歷的邊數(shù)nm被稱為路徑長度。5. 子孫結點、祖先結點一棵樹中若存在結點vm到vn的路徑，則稱vn為vm的子孫結點，vm為vn的祖先結點。 不難看出，一個結點到它的某個子孫結點有且僅有一條路徑。樹中結點之間的父子關系具有如下特征：（1）樹中任一結點都可以有零個或多個直接后繼(即子結點)，但至多只能有一個直接前驅(即父結點)。（2）樹中只有根結點無前驅，它是始結點；葉結點無后繼，它們

5、是終結點。（3）樹中某些結點之間具有父子關系或者祖先、子孫關系，祖先、子孫關系是對父子關系的擴展，一些結點之間，如兄弟結點（同一個父親的諸子結點被稱為兄弟結點）之間就沒有這種關系。6樹的高度 樹的高度為maxi=1, n NL (i)，其中n為樹中結點總數(shù)，i指樹中第i個結點，NL(i)之值為結點i的層數(shù)。 樹的高度是指樹中結點的最大層數(shù)。7 有序樹和無序樹 樹中結點的各棵子樹T1,T2,是有次序的，即為有序樹，否則為無序樹。8 森林 森林是m (m0）棵互不相交的樹的集合。樹的表示 1.集合嵌套表示法2.凹入表示法3.廣義表表示法4.樹形表示法ACBDEABCDEA(B,C(D,E)ABCD

6、E1243與線性結構的比較 線性結構 樹結構第一個數(shù)據(jù)元素 根結點 (無前驅) (無前驅)最后一個數(shù)據(jù)元素 多個葉子結點 (無后繼) (無后繼)其它數(shù)據(jù)元素 樹中其它結點(一個前驅、一個后繼) (一個前驅、多個后繼)樹的特點： 有一個總根。 沒有分枝相交。 樹有層次。樹的基本操作1、創(chuàng)建樹：CREATE_TREE(T)2、判樹空：TREEEMPTY(T)3、求根：ROOT(T) 4、求樹的高度：TREEDEPTH(T)5、 求某結點的兄弟: BROTHERS(T)6、求結點的雙親：PARENT(T)7、求結點的孩子：CHILD(T,e,i)8、遍歷樹：TRAVERSAL(T) 9、在樹T中搜索

7、數(shù)據(jù)域為item的結點：SEARCH(T,item,i)4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應用第四章 樹4.2二叉樹 4.2.1 二叉樹的定義和主要性質 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應用4.2.1 二叉樹的定義和主要性質二叉樹的定義：二叉樹是結點的有限集合，它或者是空集，或者由一個根及兩個不相交的稱為這個根的左、右子樹的二叉樹構成。 二叉樹的特征 （1） 二叉樹每個結點最多有2個子結點； （2） 二叉樹的子樹有左右之分。二叉樹的五種不同形態(tài) （a） （b） （

8、c） （d） （e）樹與二叉樹的主要區(qū)別：（1）二叉樹每個結點最多有 2 個子結點，樹則無此限制；（2） 二叉樹中結點的子樹分成左子樹和右子樹，即使某結點只有一棵子樹，也要指明該子樹是左子樹，還是右子樹，就是說二叉樹是有序的；（3） 樹不能為空，即它至少有一個結點，而一棵二叉樹可以是空的（或者說二叉樹可以為空集）。 含有3個結點的不同二叉樹 （a） （b） （c） （d） （e）二叉樹的性質引理4.1 二叉樹中層數(shù)為i的結點至多有2i個，i 0。(當根結點為1層時，有2i-1個結點。）證明：用數(shù)學歸納法。當i=0時，僅有一個根結點，其層數(shù)為0，因此i=0時引理成立。假定當i=k(k0)時引理成

9、立，即第j層至多有2k個結點。對于二叉樹的任意結點，其子結點個數(shù)最大為2，故第k+1層至多有 2*2k= 2k+1 個結點，因此當 i=k+1時，引理成立。由數(shù)學歸納法可知，對于所有的i0，均有“第 i 層上至多有 2i 個結點”。證畢。引理4.2 高度為k的二叉樹中至多有2k+1-1 (k 0)個結點。 (當根結點為1層時，有2k -1個結點。）證明：根據(jù)引理4.1 第0層上至多有20個結點，第1層上至多有21個結點, ，第k層上至多有2k個結點,因此，高度為k的二叉樹中至多有20 21+ 2k= 2k+1-1 個結點。證畢。高度為k (k 1)的二叉樹中至少有k1個結點。含有k (k 1)

10、個結點的二叉樹高度至多為k1 . 有4個結點、高度為3的二叉樹CABD引理4.3 設T是由n個結點構成的二叉樹，其中葉子結點個數(shù)為n0，度為2的結點個數(shù)為n2，則有：n0n21證明：設度為1的結點有n1個，總結點個數(shù)為n，總邊數(shù)為e，則： n=n0+n1+n2 (1) e=n-1 (2) e=2n2+n1 (3) 因此，有n0+n1+n2-1=2n2+n1 n0=n2+1證畢。定義4.4 一棵非空高度為k( k 0)的滿二叉樹，是有2k+11個結點的二叉樹。654372981013111214151高度為k（非空）二叉樹至多有2k+11個結點。滿二叉樹的特點是： 葉結點都在第k層上； 每個分支

11、結點都有兩個子結點； 葉結點的個數(shù)等于非葉結點個數(shù)加1 定義4.5 一棵包含n個結點高為k的二叉樹T，當按層次順序編號T的所有結點，對應于一棵高為k的滿二叉樹中編號由1至n的那些結點時，T被稱為完全二叉樹。65437298101具有n個結點高為k的完全二叉樹的特點是： 樹中只有最下面兩層結點的度可以小于2； 樹中最下面一層的結點都集中在該層最左邊的若干位置上（滿二叉樹意義上）； 樹中葉結點只能在層數(shù)最大的兩層上出現(xiàn)，即存在一個非負整數(shù)k使得樹中每個葉結點在第k層或第k 1層； 對樹中所有結點，按層次順序，用自然數(shù)從1開始編號，僅僅編號最大的非葉結點可以沒有右孩子，其余非葉結點都有兩個孩子結點。

12、 樹中所有結點對應于高度為k的滿二叉樹中編號由1至n的那些結點。引理4.4 若將一顆具有n個結點的完全二叉樹按層次次序從1開始編號，則對編號為i (1i n)的結點有： 若i1，則編號為i的結點的父結點的編號為 i/2 。若2in，則編號為i的結點的左孩子的編號為 2i，否則 i 無左孩子。若2i+1n，則i結點的右孩子結點編號為2i+1，否則 i 無右孩子。用歸納法證明 若i=1，如果n2，則左孩子的編號顯然為2. 假定對所有滿足ji的j，已知j的左孩子編號為2j. 那么對結點i+1，我們證明其左孩子編號為2(i+1). 如果2(i+1)n，則由層次次序得知，i+1的左孩子之前的兩個結點是i

13、的左孩子和右孩子，因為i的左孩子編號為2i(歸納假設)，故i的右孩子編號為2i+1，從而i+1的左孩子編號為2i+2= 2(i+1).證畢引理4.5 具有n個結點的完全二叉樹的高度是 log2n .證明： 設二叉樹高度為k，由定義知，完全二叉樹的結點個數(shù)介于高度為k-1和高度為k的滿二叉樹的結點數(shù)之間，即有： 2k-1 n2k+1-1 從而有2kn 2k+1，即klog2n k+1，因為k為整數(shù)，故有k= log2n .證畢請注意: 當根結點的層數(shù)為1時，樹的高度為 log2n +1 。4.2二叉樹 4.2.1 二叉樹的定義和主要性質 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲

14、 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應用要存儲一棵二叉樹，必須存儲其所有結點的數(shù)據(jù)信息、左孩子和右孩子地址，既可用順序結構存儲，也可用鏈接結構存儲。二叉樹的順序存儲是指將二叉樹中所有結點按層次順序存放在一塊地址連續(xù)的存儲空間中，同時反映出二叉樹中結點間的邏輯關系。4.2.2 二叉樹的順序存儲 對于完全二叉樹，結點的層次順序反映了其結構，可按層次順序給出一棵完全二叉樹之結點的編號，結點編號恰好反映了結點間的邏輯關系，事實上，這就是完全二叉樹的順序存儲方法。 只要對二叉樹之結點按照層次順序進行編號，就可利用一維數(shù)組A來存儲一棵含有n個結點的完全二叉樹，其中A1存儲二叉樹的根結點，A

15、i存儲二叉樹中編號為i的結點，并且結點Ai的左孩子（若存在）存放在A2i處，而Ai的右孩子（若存在）存放在A2i1處。完全二叉樹的順序存儲 A1A2A3A4A5A6 A7 A8 A9A10941766125236270493131 23 12 66 94 17 5 70 62 49 這種順序存儲方式是完全二叉樹最簡單、最節(jié)省空間的存儲方式。它實際上只存儲了結點信息域之值，而未存儲其左孩子和右孩子地址，通過計算可找到它的左孩子、右孩子和父結點，尋找子孫結點和祖先結點也非常方便。但這種方法應用到非完全二叉樹時，卻有很多缺點。如果采用上述的順序存儲方式，按照層次順序，對非完全二叉樹之結點進行編號，則

16、這時的編號不能與結點一一對應。為此，先加入若干虛結點將其轉換成一棵“完全二叉樹”，然后再對原來的結點和虛結點統(tǒng)一編號，最后完成順序存儲。但這增加了用于存儲虛結點的空間。 一般二叉樹必須仿照完全二叉樹那樣存儲。但可能會浪費很多存儲空間。一棵n個結點的二叉樹，最壞情況下需要2n-1個數(shù)組單元。4CB A 25731a1a2a3a4a5A B C a6a74.2二叉樹 4.2.1 二叉樹的定義和主要性質 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應用1、 二叉樹的鏈接存儲二叉樹諸結點被隨機存放在內(nèi)存空間中，結點之間的關系用指針說明。

17、 二叉樹的結點結構 二叉樹結點包含三個域：數(shù)據(jù)域data、指針域left和指針域right，其中左、右指針分別指向該結點的左、右孩子結點.leftright data 二叉樹的鏈接存儲結構ADCBEFGACBEFDG三叉鏈表表示法 Left data parent right 二叉樹結點類的定義 TemplateClass BinTreeNode friend class BinTree ; private:BinTreeNode *left;BinTreeNode *right; public: T data; 2、鏈接存儲的二叉樹的實現(xiàn) BinTreeNode (const T&item,

18、 BinTreeNode *lptr=NULL, BinTreeNode *rptr=NULL): data(item),left(lptr),right(rptr) / 構造函數(shù) BinTreeNode*GetLeft(void)const return Left; /返回左孩子 BinTreeNode*GetRight(void)const return right; /返回右孩子 void SetLeft(BinTreeNode * L) left = L; / 將左孩子更新為結點 L void SetRight(BinTreeNode * R) right=R; /將右孩子更新為結點

19、R ; 二叉樹類BinTree的定義templateclass BinTree private: BinTreeNode * root; /指向根結點 public: BinTree(BinTreeNode * t= NULL ): root(t) /構造函數(shù) BinTree( ) Del (root)； /析構函數(shù)刪除整棵二叉樹 BinTreeNode *Father (BinTreeNode * t, BinTreeNode* p); /在以t為根的子樹中搜索結點p的父結點int Find (BinTreeNode * & t，const T & item) const; /在以t為根的子

20、樹中查找data域為item的結點void DelSubtree (BinTreeNode* t); / 刪除以t為根的子樹void PreOrder (BinTreeNode *t ) const ; /先根遍歷以結點t為根的子樹void InOrder (BinTreeNode *t) const ; /中根遍歷以t為根的子樹void PostOrder (BinTreeNode *t) const ; /后根遍歷以結點t為根的子樹. 二叉樹類BinTree的部分實現(xiàn) (1) 搜索父結點算法Father ( t, p . q )/在以t為根的二叉樹中搜索p的父結點 F1 判斷t是否存在及p

21、是否為根結點 IF (t=NULL OR p=t)THEN ( qNULL . RETURN ) . F2 若t為所求 IF left(t)=p OR right(t)=p THEN ( qt . RETURN). F3 遞歸調用 Father( left(t), p . qL). IF qLNULL THEN qqL . RETURN.） ELSE ( Father(right(t), p . qR). qqR) . ABDCL1L2 二叉樹類BinTree的實現(xiàn) (1) 搜索父結點 / 私有函數(shù) father :返回父結點。 template BinTreeNode * BinNode :

22、 father(BinTreeNode *begin, BinTreeNode * current） 搜索父結點father(BinTreeNode *begin, BinTreeNode * current） BinTreeNode * temp; if( begin = = NULL) return NULL if( begin-left=current| begin-right=current) return begin; if（(temp=father(begin-left, current)!= NULL） return temp ； else return father(begin

23、-right,current); L1L2ABDFCE(2)搜索二叉樹中符合數(shù)據(jù)域條件的結點算法Find( t, item . q )Find1. 判斷t是否為空或為所求 IF t THEN (q . RETURN. ). IF Data(t)item THEN (q t . RETURN. ).Find2. 遞歸 Find ( Left(t), item . p ). IF p THEN (q p . RETURN. ). Find (Right(t), item . q ). RETURN.(3)刪除結點t及其左右子樹算法DST ( t )DST1. t? IF t THEN RETURN

24、 .DST2. troot? IF troot THEN (Del(t) . root . RETURN. )DST3. 找t的父結點q pt . Father(root, p. q).DST4. 修改q的指針域 IF Left(q)p THEN Left(q) . IF Right(q)p THEN Right(q) . DST5. 刪除p及其子樹 Del(p).算法Del( p )/* 刪除結點p及其左右子樹 */Del1. p ? IF p THEN RETURN.Del2. 遞歸刪除 Del(Left (p). Del(Right (p). AVAIL p .ABECD4.2二叉樹 4

25、.2.1 二叉樹的定義和主要性質 4.2.2 二叉樹的順序存儲 4.2.3 二叉樹的鏈接存儲 4.2.4 二叉樹的遍歷 4.2.5 二叉樹遍歷的應用 4.2.4 二叉樹的遍歷 二叉樹的遍歷：按照一定次序訪問二叉樹中所有結點，并且每個結點僅被訪問一次的過程。 二叉樹的某種（先根、中根、后根或層次）遍歷次序是二叉樹中結點的一個有序序列，稱為二叉樹的先根（中根、后根或層次）序列。 1. 二叉樹的遞歸遍歷算法遍歷方式先根遍歷： DLR中根遍歷： LDR后根遍歷： LRDLDR二叉樹 ABDFCE先根遍歷序列：A B C D E F中根遍歷序列： B D C A F E后根遍歷序列： D C B F E

26、 A若二叉樹為空，則空操作；否則中根遍歷左子樹；訪問根結點；中根遍歷右子樹。遍歷結果 A / B *C * D +E1）中根遍歷(中序遍歷)表達式語法樹At例*D/E*+CB二叉樹中根遍歷算法(遞歸)算法InOrder(t)InOrder1 遞歸遍歷 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t).) /中序遍歷以t為根的子樹,C+實現(xiàn)void BinTree:InOrder ( BinTreeNode * t ) if ( t != NULL ) InOrder( tleft ); cout tdata; InO

27、rder ( tright ); 中序遍歷結果： A / B *C * D +EAt例*D/E*+CB出棧的條件： t0 ，子程序結束且棧不空出棧。整個程序結束的條件： 子程序結束并且棧為空。2)先根遍歷 (前/先序遍歷)若二叉樹為空，則空操作；否則訪問根結點；先根遍歷左子樹；先根遍歷右子樹。表達式語法樹At例*D/E*+CB二叉樹先根遍歷算法(遞歸)算法PreOrder(t)PreOrder1 遞歸遍歷 IF tNULL THEN ( PRINT(data(t). PreOrder(left(t). PreOrder(right(t) ).) /先序遍歷以t為根的子樹,C+實現(xiàn)void Bi

28、nTree:PreOrder ( BinTreeNode * t ) if ( t != NULL ) cout tdata; PreOrder ( tleft ); PreOrder ( tright ); 3）后根遍歷 (后序遍歷)若二叉樹為空，則空操作；否則后根遍歷左子樹；后根遍歷右子樹；訪問根結點。二叉樹后根遍歷算法(遞歸)算法PostOrder(t)PostOrder1 遞歸遍歷 IF tNULL THEN (PostOrder(left(t). PostOrder(right(t). PRINT(data(t). ) 2. 二叉樹的非遞歸遍歷算法 非遞歸的中根遍歷遞歸算法InOrd

29、er(t)InOrder1 遞歸遍歷 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t). ) ABECD非遞歸的中根遍歷算法算法NIO( t )NIO1. 初始化 CREATE ( S ). p t . /* CREATE(S) 創(chuàng)建一個空堆棧 */NIO2. 入棧 WHILE p DO ( S p . p Left ( p) . )NIO3. 棧為空? IF S為空 THEN RETURN. ELSE p S .NIO4. 訪問p，更新p PRINT (Data ( p ) ). p Right ( p ). NI

30、O5. 返回 GOTO NIO2 .第 72 頁圖4.12 非遞歸中根遍歷二叉樹 (a) 二叉樹(b) 中根遍歷(a)中二叉樹, 堆棧內(nèi)容變化過程圖(b)中略去了進棧過程的描述ABCDEFABAADCCEAF訪問D訪問A訪問C訪問FAABA進棧B進棧訪問BADD進棧CC進棧E進棧CE訪問EF進棧FNIO2. 入棧 WHILE p DO ( S p. p Left ( p).)NIO3. 棧為空? 若S為空，則 RETURN. 否則 p S .NIO4. 訪問,更新p 打印 Data(p). pRight(p). 返回NIO2第 72 頁非遞歸的先根遍歷算法，與非遞歸的中根遍歷算法類似，區(qū)別在于

31、輸出語句的位置不同。先根和中根遍歷的非遞歸算法，一個結點僅進棧出棧一次，我們能夠判斷其輸出語句的位置，分別為結點進棧前及出棧后。而后根遍歷輸出結點的位置應為處理完右子樹之后，如果每個結點還是進棧、出棧一次，則無法確定何時輸出結點，即其左右子樹是否已處理完。非遞歸的后根遍歷算法 設置一個工作棧： 結點所處狀態(tài)i = 0, 1或2： 0：結點及左右子樹均未被訪問； 1：遍歷左子樹； 2：遍歷右子樹。樹中任一結點q都需進棧三次，出棧三次。第一次出棧是為遍歷結點q的左子樹，第二次出棧是為遍歷結點q的右子樹，第三次出棧是為訪問結點q . 結點 結點狀態(tài) i1) 將(根結點,0)壓入堆棧。2) 彈棧，對出

32、棧元素(p, i )中標號i進行判斷， 若 i0，則將(p,1)壓入堆棧；若結點p的左指針不為空，則將(Left(p), 0) 壓入堆棧，準備遍歷其左子樹.若 i1，此時已遍歷完結點p的左子樹，則將(p,2)壓入堆棧；若右指針不為空，則將(Right(p), 0)壓入堆棧，準備遍歷其右子樹.若 i2，此時已遍歷完結點p的右子樹，訪問結點p. 算法NPostOrder(t)NPO1建立堆棧 CREATS(S).NPO2堆棧初始化 S (t,0).NPO3利用棧實現(xiàn)遞歸 WHILE NOT(StackEmpty(S) DO ( (P,i) S. IF i=0 THEN ( S (P,1). IF

33、left(P) null THEN S (left(P),0) . ) IF i=1 THEN ( S (P,2). IF right (P) null THEN S (right(P),0). ) IF i=2 THEN PRINT(data(P) . ) 非遞歸的后根遍歷算法對左圖之二叉樹進行后序遍歷, 棧S 之變化 訪D訪BFCABDEWHILE 棧 S 非空 DO /分別簡記left、right為 Lt 和 Rt ( ( p , i ) S. IF i 0 THEN S( p , 1). 若 Lt ( p) , 則 S (Lt ( p), 0). IF i 1 THEN S( p ,

34、2). 若 Rt ( p) , 則 S (Rt ( p), 0). IF i 2 THEN PRINT (data( p). ) 第 77 頁第 77 頁由先根序列和中根序列可以唯一 確定一棵二叉樹。例 先根序列 A B C K D E H F 中根序列B K C A H E D F先根序列 A B C K D E H F 中根序列 B K C A H E D FAB CKDEHFABEDCKFHABDCKEHF由后根序列和中根序列可以唯一地確定一棵二叉樹。例 后根序列 C E F D B H G A 中根序列 C B E D F A G H后根序列 C E F D B H G A 中根序列C

35、 B E D F A G HACBEDFGHABCDEFGHABCGDEHF3、二叉樹的層次遍歷按層數(shù)由小到大，同層由左向右的次序訪問結點。遍歷結果: A B E C F DABDFCE通過觀察發(fā)現(xiàn)，第i層上，若結點x在結點y的左邊，則x一定在y之前被訪問。同理，第i+1層上，x的子結點一定在y的子結點前被訪問。若訪問第i層上的所有結點，必須知道該層上所有結點的地址，地址保存在其父結點的left和right指針中。用一個隊列來實現(xiàn)。二叉樹層次遍歷算法需要一個輔助隊列具體方法如下：根結點入隊.重復本步驟直至隊為空:若隊非空，取隊頭結點并訪問； 若其左指針不空，將其左孩子入隊； 若其右指針不空，將其右孩子入隊. ABFEDC算法LevelOrder ( t )LevelOrder1. 建空隊 CREATE ( Q ). LevelOrder 2. 入隊 p t . IF p THEN Q p .LevelOrder 3. 層次遍歷 WHILE Q 非空 D