1、-. z.6.3 二叉樹遍歷二叉樹遍歷的定義所謂二叉樹遍歷，就是按*種規(guī)則訪問二叉樹的每個結點，且每個結點僅被訪問一次。訪問的含義十分廣泛，包括對結點所作的各種操作與處理，如有關學生考試成績的信息存儲在一棵二叉樹中，每個結點含有*、*、成績等信息，在對這些信息進展管理時常常需要做這樣的工作：1 打印每個學生的*、*、成績等信息；2 將每個學生的成績由百分制記分改為五級制記分；3 統(tǒng)計優(yōu)、良、中、及格和不及格各檔次的人數。在1中訪問的含義是打印每個結點的信息；對于2，訪問是對成績進展修改的操作；3中訪問是統(tǒng)計操作。不管訪問的具體操作是什么，都必須做到既無重復，又無遺漏。一棵二叉樹由根結點、左子樹

2、、右子樹三個根本單元組成，根結點處于一個分割左子樹和右子樹的位置，假設能遍歷這三局部，則完成對一棵二叉樹的遍歷。假設以NNode、L(Left)、R(Right)分別代表訪問根結點、遍歷左子樹、遍歷右子樹，則訪問二叉樹結點的規(guī)則可有NLR、LNR、LRN三種遍歷和NRL、RNL、RLN三種逆遍歷方式。一般限定先左后右，僅討論前三種遍歷，分別稱之為前序遍歷Preorder Traversal、中序遍歷Inorder Traversal和后序遍歷Postorder Traversal。基于二叉樹的遞歸定義，可得三種遍歷二叉樹的遞歸定義： 前序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹1 根 2 3 左

3、子樹 右子樹 2 根1 3 左子樹 右子樹 3 根1 2 左子樹 右子樹假設二叉樹為空，則空操作；否則1訪問根結點；2前序遍歷左子樹；3前序遍歷右子樹。假設二叉樹為空，則空操作；否則1中序遍歷左子樹； 2訪問根結點；3中序遍歷右子樹。假設二叉樹為空，則空操作；否則1后序遍歷左子樹；2后序遍歷右子樹。3訪問根結點；從上述定義可以看出，三種遍歷的不同之處僅在于訪問根結點、遍歷左、右子樹的先后次序不同。前序是指最先訪問根結點；中序是指根結點在訪問左、右子樹之間被訪問；后序是指根結點在左、右子樹訪問之后被訪問。對于如圖6.15所示的二叉樹，前序遍歷該二叉樹時的結點訪問序列為：A B D E G C F

4、 H I；中序訪問序列為：D B G E A C H F I；后序訪問序列為：D G E B H I F C A。 A B C D E F G H I圖6.16 二叉樹遍歷前序遍歷算法描述1遞歸算法由前序遍歷二叉樹的遞歸定義，容易得到相應的遞歸算法。前序遍歷首先訪問根結點，再訪問左子樹，然后訪問右子樹。對左子樹的訪問，也是先訪問其根結點，再訪問左其子樹，然后訪問其右子樹，如此反復，逐步將大樹的訪問分解為左、右子樹的訪問，直到其子樹為空。這是一個典型的遞歸模型。假設二叉樹以二叉鏈表存儲，對結點的訪問操作簡化為輸出打印結點值，可根據實際應用具體化為其他操作，則前序遍歷二叉樹的遞歸算法如下：算法6.

5、1void Preorder(Bitree T)/*前序遍歷二叉樹的遞歸算法*/If (T)Printf(%d,T-data); /訪問根結點Preorder(T-Lchild); / 遍歷左子樹Preorder(T-Rchild); / 遍歷右子樹return; 如圖6.17所示為前序遍歷二叉樹的過程示意圖。帶箭頭的包圍虛線表示前序遍歷過程中所走的一條搜索路徑，其中向下的箭頭表示向更深一層的遞歸調用，向上的箭頭表示從遞歸調用返回，包圍虛線旁方形內的字符表示搜索路徑中訪問的結點，訪問序列為：A B D E C F。 A A AB C B B C D E F D D E FA B D E C F

6、a前序遍歷二叉樹A B D E C F b前序遍歷過程示意圖圖6.16二叉樹前序遍歷過程示意圖2.非遞歸算法下面，我們來討論前序遍歷算法的非遞歸實現。一個具有遞歸特點的問題，如果用非遞歸的程序實現，通?？梢越柚跅韺崿F遞歸層次調用時的參數傳遞。前序遍歷的順序為：NLR，在訪問根結點后對根的左子樹遍歷，當左子樹遍歷完后沿走過的路線返回到根結點，再通過根結點找到其右子樹。因此，為了在左子樹遍歷完后能夠找到其右子樹，該根結點必須在左子樹遍歷前入棧保存。假設棧為一順序棧，二叉樹遍歷的非遞歸算法涉及棧的入棧、出棧等多種操作，將充分展示棧的威力，是棧構造的一個極好的應用。算法6.2#define MA*

7、LEN 100void preorder(Bitree T)/*前序遍歷二叉樹的遞歸算法*/Bitree StackMA*LEN,p; int top=0; p=T; do While( p!=NULL)Printf(%d,p-data); /訪問根結點top+; /根結點入棧stacktop=p;p=p-Lchild; /指向左子樹 if (top0)p=stacktop; /根結點出棧top-;p=p-Rchild; /指向右子樹; while p!=NULL| (top!=0); / 當根結點不為空或者棧不空時3.算法分析假定是n個結點的二叉樹，由于每個結點僅被訪問一次，每個結點要進一次

8、棧，出一次棧，因此算法中的根本操作進棧、出棧、訪問等操作均被執(zhí)行一次，算法的時間復雜度為O(n)。算法中的棧所需最大容量與二叉樹的深度直接相關。從6.17(b)中可以看出，棧中元素序列實際上是由二叉樹的根結點到*個結點所經分支上的結點所組成的，所以棧中元素的個數最多等于二叉樹的深度。而有n個結點二叉樹深度的最大值為n (單支樹的情況)，因此，棧所需要的最大容量不超過n。中序遍歷算法描述中序遍歷與前序遍歷算法思想非常類似，以下我們只簡單給出中序遍歷遞歸與非遞歸算法。1遞歸算法中序遍歷的順序為：LNR，中序遍歷與前序遍歷的區(qū)別僅在于訪問根結點、遍歷左子樹、遍歷右子樹三個操作的次序不同而已，訪問根結

9、點的操作在遍歷左子樹與遍歷右子樹之間。只要重新安排三個操作的次序就可以得到中序遍歷遞歸算法算法6.3 void Inorder(Bitree T)/*中序遍歷二叉樹的遞歸算法*/If (T)Inorder(T-Lchild); /遍歷左子樹Printf(%d,T-data); /訪問根結點Inorder(T-Rchild); /遍歷右子樹return; 如圖6.18所示為二叉樹中序遍歷過程。從A開場，向其左子樹遞歸調用，直到左子樹為空，訪問其根結點，第一個被訪問的結點為D，再遍歷D的右子樹，為空返回到結點B，遍歷其右子樹，依次類推，得到中序遍歷的序列為：D B E A C F。 A AB C

10、B C B D E F D D E FD B E A C Fa中序遍歷二叉樹D B E AC F b中序遍歷過程示意圖圖6.18二叉樹中序遍歷過程示意圖2非遞歸算法中序遍歷的過程是遍歷根結點的所有左子樹的左結點并入棧，直到結點為空返回，結點出棧，被訪問，然后轉右子樹結點。中序遍歷的非遞歸算法在算法6.2的根底上稍作修改即得算法6.4。算法6.4#define MA*LEN 100void Inorder(Bitree T)/*中序遍歷二叉樹的非遞歸算法*/Bitree StackMA*LEN,p; int top=0; p=T; do While( p!=NULL) top+; /根結點入棧s

11、tacktop=p;p=p-Lchild; /指向左子樹 if (top0)p=stacktop; /根結點出棧top-;Printf(%d,p-data); /訪問根結點p=p-Rchild; /指向右子樹; while p!=NULL| (top!=0); / 當根結點不為空或者棧不空時3.算法分析上述算法與前序遍歷算法類似，只是訪問根結點的語句在程序中的位置不同，并不影響算法的復雜性。因此，n個結點的二叉樹，中序遍歷算法的時間復雜度仍為O(n)，棧所需要的最大容量不超過二叉樹的深度。后序遍歷算法描述1遞歸算法后序遍歷的順序為：LRN，后序遍歷與前序遍歷的區(qū)別在于訪問根結點的操作在遍歷左子

12、樹與遍歷右子樹之后。調整三個操作的次序就可以得到后序遍歷遞歸算法。算法6.5 void Postorder(Bitree T)/*后序遍歷二叉樹的遞歸算法*/If (T)Postorder(T-Lchild); /遍歷左子樹Postorder(T-Rchild); /遍歷右子樹Printf(%d,T-data); /訪問根結點return; 如圖6.19所示為二叉樹后序遍歷過程。從A開場，向其左子樹遞歸調用，直到結點D，左子樹為空，再遍歷D的右子樹，也為空返回，訪問結點D，再返回到結點B，遍歷其右子樹，依次類推，得到后序遍歷的序列為：D E B F C A ，如圖6.19b中包圍虛線旁的三角內

13、字符為訪問結點。 A AB C B C D E F D E F D E B F C Aa后序遍歷二叉樹D E B F C A b后序遍歷過程示意圖圖6.18 二叉樹后序遍歷過程示意圖2. 非遞歸算法后序遍歷的非遞歸算法比前序遍歷、中序遍歷要復雜。在后序遍歷時，如果存在左子樹，則首先查看該結點的左子樹，在按后序遍歷左子樹時，該結點進棧保存，以便返回時遍歷其右子樹。在按后序遍歷其右子樹時，該結點還得進棧保存，因為該結點需在右子樹訪問完后才被訪問。這樣，樹中的每個結點都應兩次進棧、兩次出棧。第一次出棧是在遍歷訪問完所有的左子樹結點，出棧的目的是為了訪問其右子樹；第二次出棧是在遍歷訪問完所有的右子樹結

14、點，出棧的目的是為了訪問該根結點。如何區(qū)分兩次出棧？方法一是為每個結點設置標志位tagi: 0 訪問左子樹，需出棧找右子樹 tagi=1 訪問右子樹，需出訪問該結點算法6.6#define MA*LEN 100void Postorder1(Bitree T)/*后序遍歷二叉樹的非遞歸算法一*/Bitree StackMA*LEN,p; int tagMA*LEN,top=0，b; p=T; do While( p!=NULL) top+; /根結點入棧stacktop=p;tagtop=0; /設置標志位p=p-Lchild; /指向左子樹 b=1; while (top!=0) &b p=

15、stacktop; /根結點出棧if (tagtop= =1)top-;Printf(%d,p-data); /訪問根結點 else p=p-Rchild; /指向右子樹tagtop=1;b=0; ; while p!=NULL| (top!=0); / 當根結點不為空或者棧不空時方法二是設一指針q，用于記住最近一次被訪問的結點。這種方法不需要記住什么時候應訪問根結點，不必為每個結點設立標志位，只需在結點每次出棧前判斷其右子樹是否為空，假設為空，即不存在右孩子，則該結點出棧應被訪問；假設右子樹非空但已遍歷完畢，即它的右孩子恰好是最近一次訪問的結點，則棧頂元素出棧應被訪問；假設右子樹非空而且尚未

16、遍歷，即它的右孩子不是最近一次訪問的結點，則現在不訪問棧頂元素所指結點，而應去遍歷右子樹。因此，在遍歷過程中，只需要用一指針記住最近訪問過的結點即可。算法6.7#define MA*LEN 100void Postorder2(Bitree T)/*后序遍歷二叉樹的非遞歸算法二*/Bitree StackMA*LEN,p，q; int top=0，b; p=T; do While( p!=NULL) top+; /根結點入棧stacktop=p;p=p-Lchild; /指向左子樹 b=1;q=NULL; while (top!=0) & b p=stacktop; /根結點出棧if p-rc

17、hild=q /棧頂元素所指結點其右子樹是否為空或者其右子樹是否為最近被訪問的結點top-;Printf(%d,p-data); /訪問根結點q=p; /q指向最近被訪問的結點 else p=p-Rchild; /指向右子樹b=0; ; while p!=NULL| (top!=0); / 當根結點不為空或者棧不空時3.算法分析上述算法與前序、中序遍歷算法相比要復雜一些，理論上分析需要二次入棧，二次出棧，但從算法的實現來看，第一次并未真正出棧，只需取棧頂元素作判斷即可，也就不需二次入棧。因此，對算法的復雜性并沒有多大影響，n個結點的二叉樹，后序遍歷算法的時間復雜度仍為O(n)，棧所需要的最大容

18、量在小于二叉樹的深度時不會出現溢出。遍歷算法的應用遍歷二叉樹是二叉樹各種操作運算的根底，很多操作可以在遍歷過程中完成。如前所述，遍歷算法中對每個結點進展一次訪問操作，而訪問結點的操作可以是多種形式及多個操作。利用這一特點，根據遍歷算法的程序框架，適當修改訪問操作的內容，便可得到求解許多問題的算法，如求二叉樹的結點數、葉子數，判定結點的層次等。因此，二叉樹遍歷算法是二叉樹應用算法的根底，其程序框架是非常根底又相當重要。下面給出幾個典型問題的求解。例6.1求二叉樹T中的葉子結點數本算法求二叉樹T中的結點數，只需將遍歷算法中的訪問操作改為條件計數操作，即在訪問結點時判斷該結點是否為葉子，假設為葉子，

19、將該葉子結點的數目1累加到一個全局變量n中n初值為0,每個結點被訪問時即被判斷、條件計數。算法如下：算法6.8void Inord-Leaves( Bitree T) /*將二叉樹T中的結點數累加到全局變量n中，n初值為0*/if (T)Inorder-Leaves(T-Lchild);If (T-Lchild = = NULL) & (T-Rchild = = NULLl) n=n+1;Inorder-Leaves(T-Lchild);算法6.8是一個標準中序遍歷算法，其訪問操作為是否為葉子的判斷和累加計數。該算法也可很方便地改為前序遍歷和后序遍歷算法。例6.2 建立二叉樹的存儲構造二叉鏈表

20、建立二叉樹的存儲構造是對二叉樹進展操作的前提，也就是說，對二叉樹的操作必須是在建立二叉樹存儲構造的根底上進展，包括遍歷操作。如圖6.20(a)所示的二叉樹，如何建立其圖6.20(b)所示的二叉鏈表呢？假設按其前序遍歷的線性順序：A B # # C D # E # # # (空子樹用表示)輸入來建立二叉鏈表，T為指向根結點的指針，首先輸入一個根結點，假設輸入的是一個特殊字符如，則說明該二叉樹為空樹，即TNULL；否則，申請一個結點空間，輸入的字符賦給T-data，之后依次遞歸建立其左子樹T-Lchild和T-Rchild。按前序遍歷算法框架設計該算法如下： A A B C B C D D E E

21、a二叉樹例如 (b) 二叉鏈表圖6.19 二叉樹及其二叉鏈表算法6.9 void CreateBiTree ( BiTree & T) /*按前序遍歷序列輸入結點字符，建立二叉鏈表存儲構造*/ scanf (&ch); if (ch=#) T= NULL; /建空樹 else if (!(T= (BiTNode *)malloc(sizeof (BiTNode ) /生成根結點printf (OVERFLOW); return;T-data =ch;CreateBiTree (T -Lchild); /遞歸建立左子樹CreateBiTree (T -Rchild); /遞歸建立右子樹 retu

22、rn ;算法6.9是一個標準前序遍歷算法，其訪問操作為根結點生成操作。例6.3 求二叉樹的高度二叉樹的高度為二叉樹中所有結點的最大層次數。結點的層次從根結點開場遞推，設二叉樹根結點的層次數為1，其子樹根結點在第2層上，依此類推，第k層結點的子樹根結點在第k+1層。因此求二叉樹的高度，可在前序遍歷二叉樹的過程中求每個結點的層次數，其中的最大值即為二叉樹的高度。算法6.10void BiTreeHeight ( BiTree T,int h,int &Height) /*求二叉樹的高度Height，初值為0，h為T所指向的結點所在層次，初值為1*/if (T) if (hHeight) Heigh

23、t=h;BiTreeHeight ( T-Lchild, h+1,Height); BiTreeHeight ( T-Rchild, h+1,Height);算法6.10也是一個標準的前序遍歷算法，其訪問操作為當前訪問結點的層次數h與當前求得的最大層次數Height比擬，Height取大值。該算法參數表中設置的值參h，始終保持和當前T所指結點層次一致，這是很多遍歷應用算法中采用的一種技巧，請注意掌握這種技巧的應用。圖6.19(a)所示的二叉樹，求其高度算法執(zhí)行過程如圖6.20所示，向下的虛線表示遞歸調用，虛線旁邊括號內的值為調用傳遞的參數值，向上的虛線表示調用返回，虛線旁的值為調用返回值。He

24、ight簡化表示為H，注意H與h值得區(qū)別。圖6.20 前序遍歷求二叉樹高度算法執(zhí)行過程求二叉樹高度也可通過后序遍歷二叉樹來得到。二叉樹高度可遞歸定義為：假設二叉樹為空，則其高度為0;否則其高度等于左或右子樹的最大高度加1。由此遞歸定義得到遞歸模型為： 0 T=NULLHeight(T)= Ma* (Height(T-Lchild) , Height(T-Rchild)+1 TNULL從而得到以下算法：算法6.11void BiTreeHeight ( BiTree T) /*求二叉樹的高度Height*/if (！T) return 0 else HL=BiTreeHeight ( T-Lch

25、ild); HR=BiTreeHeight ( T-Rchild);if (HL=HR) return HL+1;else return HR+1;例6.3 表達式求值表達式的計算曾在第三章作為棧的典型應用進展了討論，這里，選擇二叉樹這種數據構造存儲表達式，討論其求值問題。一般情況下，一個表達式由一個運算符和兩個操作數構成，兩個操作數之間有次序之分，并且操作數也可是表達式，這種構造類似于二叉樹，因此，可以用二叉樹表示表達式。表示表達式的二叉樹稱為表達式樹E*pression Trees,這類二叉樹具有以下特點：1. 每個葉子是操作數；2. 根結點和內部結點是操作符；3. 子樹是子表達式樹。如表達式a*(b+c)+d,可表示成圖6.22所示的二叉樹。前序遍歷這棵二叉樹，得到線性序列：+*a+bcd，這是表達式的前綴形式，或稱為波蘭表示。中序遍歷這棵二叉樹，得到線性序列：a*b+c+d，這恰是表達式的中綴形式。后序遍歷這棵二叉樹，得到