數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷

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

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

3、子樹 右子樹 2 根1 3 左子樹 右子樹 3 根1 2 左子樹 右子樹假設(shè)二叉樹為空，則空操作；否則1訪問根結(jié)點(diǎn)；2前序遍歷左子樹；3前序遍歷右子樹。假設(shè)二叉樹為空，則空操作；否則1中序遍歷左子樹； 2訪問根結(jié)點(diǎn)；3中序遍歷右子樹。假設(shè)二叉樹為空，則空操作；否則1后序遍歷左子樹；2后序遍歷右子樹。3訪問根結(jié)點(diǎn)；從上述定義可以看出，三種遍歷的不同之處僅在于訪問根結(jié)點(diǎn)、遍歷左、右子樹的先后次序不同。前序是指最先訪問根結(jié)點(diǎn)；中序是指根結(jié)點(diǎn)在訪問左、右子樹之間被訪問；后序是指根結(jié)點(diǎn)在左、右子樹訪問之后被訪問。對于如圖6.15所示的二叉樹，前序遍歷該二叉樹時(shí)的結(jié)點(diǎn)訪問序列為：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遞歸算法由前序遍歷二叉樹的遞歸定義，容易得到相應(yīng)的遞歸算法。前序遍歷首先訪問根結(jié)點(diǎn)，再訪問左子樹，然后訪問右子樹。對左子樹的訪問，也是先訪問其根結(jié)點(diǎn)，再訪問左其子樹，然后訪問其右子樹，如此反復(fù)，逐步將大樹的訪問分解為左、右子樹的訪問，直到其子樹為空。這是一個(gè)典型的遞歸模型。假設(shè)二叉樹以二叉鏈表存儲，對結(jié)點(diǎn)的訪問操作簡化為輸出打印結(jié)點(diǎn)值，可根據(jù)實(shí)際應(yīng)用具體化為其他操作，則前序遍歷二叉樹的遞歸算法如下：算法6.

5、1void Preorder(Bitree T)/*前序遍歷二叉樹的遞歸算法*/If (T)Printf(%d,T-data); /訪問根結(jié)點(diǎn)Preorder(T-Lchild); / 遍歷左子樹Preorder(T-Rchild); / 遍歷右子樹return; 如圖6.17所示為前序遍歷二叉樹的過程示意圖。帶箭頭的包圍虛線表示前序遍歷過程中所走的一條搜索路徑，其中向下的箭頭表示向更深一層的遞歸調(diào)用，向上的箭頭表示從遞歸調(diào)用返回，包圍虛線旁方形內(nèi)的字符表示搜索路徑中訪問的結(jié)點(diǎn)，訪問序列為：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.非遞歸算法下面，我們來討論前序遍歷算法的非遞歸實(shí)現(xiàn)。一個(gè)具有遞歸特點(diǎn)的問題，如果用非遞歸的程序?qū)崿F(xiàn)，通?？梢越柚跅韺?shí)現(xiàn)遞歸層次調(diào)用時(shí)的參數(shù)傳遞。前序遍歷的順序?yàn)椋篘LR，在訪問根結(jié)點(diǎn)后對根的左子樹遍歷，當(dāng)左子樹遍歷完后沿走過的路線返回到根結(jié)點(diǎn)，再通過根結(jié)點(diǎn)找到其右子樹。因此，為了在左子樹遍歷完后能夠找到其右子樹，該根結(jié)點(diǎn)必須在左子樹遍歷前入棧保存。假設(shè)棧為一順序棧，二叉樹遍歷的非遞歸算法涉及棧的入棧、出棧等多種操作，將充分展示棧的威力，是棧構(gòu)造的一個(gè)極好的應(yīng)用。算法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); /訪問根結(jié)點(diǎn)top+; /根結(jié)點(diǎn)入棧stacktop=p;p=p-Lchild; /指向左子樹 if (top0)p=stacktop; /根結(jié)點(diǎn)出棧top-;p=p-Rchild; /指向右子樹; while p!=NULL| (top!=0); / 當(dāng)根結(jié)點(diǎn)不為空或者棧不空時(shí)3.算法分析假定是n個(gè)結(jié)點(diǎn)的二叉樹，由于每個(gè)結(jié)點(diǎn)僅被訪問一次，每個(gè)結(jié)點(diǎn)要進(jìn)一次

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

9、點(diǎn)的操作在遍歷左子樹與遍歷右子樹之間。只要重新安排三個(gè)操作的次序就可以得到中序遍歷遞歸算法算法6.3 void Inorder(Bitree T)/*中序遍歷二叉樹的遞歸算法*/If (T)Inorder(T-Lchild); /遍歷左子樹Printf(%d,T-data); /訪問根結(jié)點(diǎn)Inorder(T-Rchild); /遍歷右子樹return; 如圖6.18所示為二叉樹中序遍歷過程。從A開場，向其左子樹遞歸調(diào)用，直到左子樹為空，訪問其根結(jié)點(diǎn)，第一個(gè)被訪問的結(jié)點(diǎn)為D，再遍歷D的右子樹，為空返回到結(jié)點(diǎn)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非遞歸算法中序遍歷的過程是遍歷根結(jié)點(diǎn)的所有左子樹的左結(jié)點(diǎn)并入棧，直到結(jié)點(diǎn)為空返回，結(jié)點(diǎn)出棧，被訪問，然后轉(zhuǎn)右子樹結(jié)點(diǎn)。中序遍歷的非遞歸算法在算法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+; /根結(jié)點(diǎn)入棧s

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

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

13、字符為訪問結(jié)點(diǎn)。 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. 非遞歸算法后序遍歷的非遞歸算法比前序遍歷、中序遍歷要復(fù)雜。在后序遍歷時(shí)，如果存在左子樹，則首先查看該結(jié)點(diǎn)的左子樹，在按后序遍歷左子樹時(shí)，該結(jié)點(diǎn)進(jìn)棧保存，以便返回時(shí)遍歷其右子樹。在按后序遍歷其右子樹時(shí)，該結(jié)點(diǎn)還得進(jìn)棧保存，因?yàn)樵摻Y(jié)點(diǎn)需在右子樹訪問完后才被訪問。這樣，樹中的每個(gè)結(jié)點(diǎn)都應(yīng)兩次進(jìn)棧、兩次出棧。第一次出棧是在遍歷訪問完所有的左子樹結(jié)點(diǎn)，出棧的目的是為了訪問其右子樹；第二次出棧是在遍歷訪問完所有的右子樹結(jié)

14、點(diǎn)，出棧的目的是為了訪問該根結(jié)點(diǎn)。如何區(qū)分兩次出棧？方法一是為每個(gè)結(jié)點(diǎn)設(shè)置標(biāo)志位tagi: 0 訪問左子樹，需出棧找右子樹 tagi=1 訪問右子樹，需出訪問該結(jié)點(diǎn)算法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+; /根結(jié)點(diǎn)入棧stacktop=p;tagtop=0; /設(shè)置標(biāo)志位p=p-Lchild; /指向左子樹 b=1; while (top!=0) &b p=

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

16、遍歷，即它的右孩子不是最近一次訪問的結(jié)點(diǎn)，則現(xiàn)在不訪問棧頂元素所指結(jié)點(diǎn)，而應(yīng)去遍歷右子樹。因此，在遍歷過程中，只需要用一指針記住最近訪問過的結(jié)點(diǎn)即可。算法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+; /根結(jié)點(diǎn)入棧stacktop=p;p=p-Lchild; /指向左子樹 b=1;q=NULL; while (top!=0) & b p=stacktop; /根結(jié)點(diǎn)出棧if p-rc

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

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

19、將該葉子結(jié)點(diǎn)的數(shù)目1累加到一個(gè)全局變量n中n初值為0,每個(gè)結(jié)點(diǎn)被訪問時(shí)即被判斷、條件計(jì)數(shù)。算法如下：算法6.8void Inord-Leaves( Bitree T) /*將二叉樹T中的結(jié)點(diǎn)數(shù)累加到全局變量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是一個(gè)標(biāo)準(zhǔn)中序遍歷算法，其訪問操作為是否為葉子的判斷和累加計(jì)數(shù)。該算法也可很方便地改為前序遍歷和后序遍歷算法。例6.2 建立二叉樹的存儲構(gòu)造二叉鏈表

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

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

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

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

24、ight簡化表示為H，注意H與h值得區(qū)別。圖6.20 前序遍歷求二叉樹高度算法執(zhí)行過程求二叉樹高度也可通過后序遍歷二叉樹來得到。二叉樹高度可遞歸定義為：假設(shè)二叉樹為空，則其高度為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 表達(dá)式求值表達(dá)式的計(jì)算曾在第三章作為棧的典型應(yīng)用進(jìn)展了討論，這里，選擇二叉樹這種數(shù)據(jù)構(gòu)造存儲表達(dá)式，討論其求值問題。一般情況下，一個(gè)表達(dá)式由一個(gè)運(yùn)算符和兩個(gè)操作數(shù)構(gòu)成，兩個(gè)操作數(shù)之間有次序之分，并且操作數(shù)也可是表達(dá)式，這種構(gòu)造類似于二叉樹，因此，可以用二叉樹表示表達(dá)式。表示表達(dá)式的二叉樹稱為表達(dá)式樹E*pression Trees,這類二叉樹具有以下特點(diǎn)：1. 每個(gè)葉子是操作數(shù)；2. 根結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)是操作符；3. 子樹是子表達(dá)式樹。如表達(dá)式a*(b+c)+d,可表示成圖6.22所示的二叉樹。前序遍歷這棵二叉樹，得到線性序列：+*a+bcd，這是表達(dá)式的前綴形式，或稱為波蘭表示。中序遍歷這棵二叉樹，得到線性序列：a*b+c+d，這恰是表達(dá)式的中綴形式。后序遍歷這棵二叉樹，得到