數(shù)據(jù)結(jié)構(gòu) 嚴蔚敏 -第6章 樹和二叉樹2-遍歷二叉樹(劉)

1、 劉靈麗 湘南學院 遍歷二叉樹遍歷二叉樹二二 幾種遍歷方法幾種遍歷方法1.先序遍歷（先序遍歷（DLR)： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1)訪問根結(jié)點訪問根結(jié)點 (2)先序遍歷左子樹先序遍歷左子樹 (3)先序遍歷右子樹先序遍歷右子樹2.中序遍歷：中序遍歷：3.后序遍歷：后序遍歷：4.按層次遍歷：從上到下、從左到右訪問各結(jié)點。按層次遍歷：從上到下、從左到右訪問各結(jié)點。一一 什么叫遍歷什么叫遍歷 樹中每個節(jié)點被訪問有且僅有一次。樹中每個節(jié)點被訪問有且僅有一次。ADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷:A

2、DBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:Bvoid preorder(BiTree T) if(T) printf(%c ,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTC

3、printf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C-+/a*b-efcd先序遍歷：先序遍歷：中序遍歷：后序遍歷：后序遍歷：層次遍歷：-+ a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f以字符串的形式表示一棵二叉樹以字符串的形式表示一棵二叉樹ABCD 以字符串“表示空樹空樹只含根結(jié)點的二只含根結(jié)點的二叉樹叉樹A 以字符串“ A 表示 以“ AB C D表示Status CreateBiTree(BiTree &am

4、p;T) scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; / 生成根結(jié)點 CreateBiTree(T-lchild); / 構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; A B C D A BCD上頁算法執(zhí)行過程舉例如下：ATBCD1，根結(jié)點入棧，根結(jié)點入棧2，若?？談t轉(zhuǎn)，若?？談t轉(zhuǎn)83，while(棧頂元素不是空指針棧頂元素不是空指針)左孩子入棧左孩子入棧4，若棧頂元素為空指針，則空指針出棧，若棧頂元素

5、為空指針，則空指針出棧5，若棧不空，出棧，訪問結(jié)點，若棧不空，出棧，訪問結(jié)點6，右孩子入棧，右孩子入棧7，轉(zhuǎn)，轉(zhuǎn)28，returnvoid InorderTraverse(BiTree T, void (*Visit) (TelemType& e) /中序遍歷二叉樹中序遍歷二叉樹T T的非遞歸算法的非遞歸算法 Stack *S; InitStack(S); Push(S,T); while(!StackEmpty(S) while(Gettop(S,p)&p) Push(S,p-lchild);/左孩子入棧左孩子入棧 Pop(S,pPop(S,p) ) /空指針出?？罩羔槼鰲?

6、if(!StackEmpty(Sif(!StackEmpty(S) ) /訪問結(jié)點訪問結(jié)點 Pop(S,p); if(!Visit(pPop(S,p); if(!Visit(p-data) return ERROR;-data) return ERROR; Push(S,p-rchild Push(S,p-rchild);); /if /if / while return OK; 4 非遞歸算法實現(xiàn)中序遍歷時棧的狀態(tài)非遞歸算法實現(xiàn)中序遍歷時棧的狀態(tài)ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B

7、訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪

8、問：C B E G D F Ap=NULL(15)后序遍歷非遞歸算法5.1 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹，在遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個由此，需在遍歷算法中增添一個“計數(shù)計數(shù)”的參數(shù)，并將算法中的參數(shù)，并將算法中“訪問結(jié)點訪問結(jié)點”的操的操作改為：若是葉子，則計數(shù)器增作改為：若是葉子，則計數(shù)器增1 1。5 遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例void CountLeaf (BiTree T, int&

9、 count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 對葉子結(jié)點計數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf5.2 求二叉樹的深度求二叉樹的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的深二叉樹的深度應(yīng)為其左、右子樹深度的最大值加度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右求得左、右

10、子樹深度的最大值，然后加子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之間的關(guān)系。int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;以字符串的形式定義一棵二叉樹以字符串的形式定義一棵二叉

11、樹ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空樹空樹只含一個根結(jié)點只含一個根結(jié)點的二叉樹的二叉樹A以字符串“A ”表示以下列字符串表示Status CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; / 生成根結(jié)點 CreateBiTree(T-lchild); / 構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; A B C D A

12、BCD上頁算法執(zhí)行過程舉例如下：ATBCDl可使用一個順序存儲的隊列可使用一個順序存儲的隊列q100,存放存放還沒有處理的子樹的根結(jié)點的地址。注還沒有處理的子樹的根結(jié)點的地址。注意意,隊首和隊尾指針分別指向隊首結(jié)點隊首和隊尾指針分別指向隊首結(jié)點和下次進隊結(jié)點的存放位置。和下次進隊結(jié)點的存放位置。1) 首先把根節(jié)點入隊。首先把根節(jié)點入隊。2) 然后訪問隊頭的一個結(jié)點，再把該結(jié)點然后訪問隊頭的一個結(jié)點，再把該結(jié)點非空的左右子樹入隊。非空的左右子樹入隊。3) 如果隊列不空，重復(fù)如果隊列不空，重復(fù)2)。l 當用棧非遞歸實現(xiàn)樹當用棧非遞歸實現(xiàn)樹的先序遍歷時，寫出的先序遍歷時，寫出遍歷右邊所表示的樹遍歷右邊所表示的樹的全過程。像講義中的全過程。像講義中那樣，寫出遍歷每一那樣，寫出遍歷每一步棧中的數(shù)據(jù)。不是步棧中的數(shù)據(jù)。不是寫具體的實現(xiàn)代碼。寫具體的實現(xiàn)代碼。ABCDEFGl分別寫一個函數(shù)，統(tǒng)計二叉樹的節(jié)點個數(shù)；分別寫一個函數(shù)，統(tǒng)計二叉樹的節(jié)點個數(shù)；輸出樹的深度；最大元；最小元；輸出樹的深度；最大元；最小元；用樹形結(jié)用樹形結(jié)構(gòu)打印出該二叉樹。構(gòu)打印出該二叉樹。l