C語言程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)第14章

C語言程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)第14章第1頁/共42頁14.1棧14.2隊列14.3樹第2頁/共42頁14.1棧14.1.1什么是棧14.1.2順序棧的實現(xiàn)第3頁/共42頁棧和隊列是在軟件設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同。其特點在于運算受到了限制：棧按“后進先出”的規(guī)則進行操作，隊按“先進先出”的規(guī)則進行操作，故稱操作受限制的線性表。樹型結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu)，它是具有分支關(guān)系的層次結(jié)構(gòu)，可以用來描述較復(fù)雜的數(shù)據(jù)關(guān)系。樹型結(jié)構(gòu)應(yīng)用非常廣泛，特別是在數(shù)據(jù)處理方面，如在文件系統(tǒng)、編譯系統(tǒng)、目錄組織等方面，顯得更加突出。第4頁/共42頁14.1.1什么是棧

棧（Stack）是限定僅在表的一端進行插入和刪除操作的線性表。通常將表中允許插入、刪除操作的這一端稱為棧頂（top），因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底（bottom）。棧頂?shù)牡谝粋€元素叫做棧頂元素。不含任何數(shù)據(jù)元素的棧稱為空棧。棧的插入操作被形象的稱為進棧或入棧，刪除操作稱為出棧或退棧。假設(shè)有棧S=(a1,a2,…,an)，如圖14.1(a)所示，元素是以a1,a2,…,an的順序進棧，因此棧底元素是a1，棧頂元素是an。退棧的第一個元素應(yīng)為棧頂元素an。

圖14.1(a)棧第5頁/共42頁下面舉例說明棧的結(jié)構(gòu)特征。

假設(shè)有一個很窄的死胡同，胡同里能容納若干人，但每次只能容許一個人進出。現(xiàn)有五個人，分別編號為①～⑤，按編號的順序進入胡同，如圖14.1(b)所示。若④要出來，必須等⑤退出后才有可能。若①要退出，則必須等到⑤④③②依次都退出后才行。這里，人進出胡同的原則是后進去的先出來。換句話說，先進去的后出來。棧可以比作這里的死胡同，棧頂相當于胡同口，棧底相當于胡同的另一端，進、出胡同可看作棧的插入、刪除運算。插入、刪除都在棧頂進行，進出都經(jīng)過胡同口。這表明棧的原則是后進先出。因此，棧又稱為后進先出(lastinfirstout)線性表，簡稱LIFO表。棧的基本操作除了在進棧（棧頂插入）、出棧（刪除棧頂元素）外，還有建立堆棧（棧的初始化）、判空和取棧頂元素等運算。基本操作：（1）INI_STACK(S)（2）EMPTY_STACK(S)（3）PUSH_STACK(S,x)（4）POP_STACK(S)（5）TOP_STACK(S)第6頁/共42頁14.1.2順序棧的實現(xiàn)

棧作為一種特殊的線性表，在計算機中也主要有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。我們稱順序存儲的棧為順序棧，鏈式存儲的棧為鏈棧。順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧。順序棧的存儲結(jié)構(gòu)可以用C語言中的一維數(shù)組來表示。棧的順序存儲結(jié)構(gòu)定義如下：#defineMaxSize /*線性表可能達到的最大長度*/typedefstruct /*順序棧類型定義*/{Elemtypedata[MaxSize];inttop; /*指示棧頂位置*/}SeqStack;這里把存放棧中元素的數(shù)組和指向棧頂?shù)淖兞慷甲鳛榻Y(jié)構(gòu)體類型SeqStack的分量來定義。鑒于C語言中數(shù)組的下標值約定從0開始，則當以C語言作描述語言時，數(shù)組的0下標端設(shè)為棧底。這樣，空棧時，棧頂指針top為-1；入棧時，棧頂指針top加1；出棧時，棧頂指針top減1。

第7頁/共42頁假設(shè)用一維數(shù)組sq表示一個棧，圖14.2說明了這個順序棧的幾種狀態(tài)。圖14.2棧頂指針和棧中元素之間的關(guān)系圖14.2(a)是空棧；圖14.2(b)是只有一個元素時的狀態(tài)；圖14.2(c)是A、B、C、D、E、F這六個元素依次進入棧之后的狀態(tài)；圖14.2(d)是刪除E、F兩個元素后的狀態(tài)，此時棧中還有四個元素，或許剛出棧的元素E、F仍然在原先的單元存儲著，但top指針已經(jīng)指向了新的棧頂，則元素E、F已不在棧中了，通過這個示意圖要深刻理解棧頂指針的作用。由于棧是一個動態(tài)結(jié)構(gòu)，而數(shù)組是靜態(tài)結(jié)構(gòu)，因此會出現(xiàn)所謂的溢出問題。當棧中已經(jīng)有MaxSize個元素時，如果再進行進棧操作，則會產(chǎn)生溢出，通常稱為上溢(overflow)；而對空棧進行出棧操作時，也會產(chǎn)生溢出，通常稱為下溢(underflow)。為了避免溢出，在對棧進行進棧操作和出棧操作前，應(yīng)分別檢查棧是否已滿或者是否已空。

第8頁/共42頁順序棧的基本操作的實現(xiàn)如下：（1）初始化順序棧的初始化即構(gòu)造一個空的順序棧。為棧結(jié)構(gòu)申請空間，并將棧頂指針賦值為-1。具體算法描述如下：【算法14.1】構(gòu)造一個空棧SeqStack*Init_SeqStack(){SeqStack*s; s=(SeqStack*)malloc(sizeof(SeqStack)); if(s==NULL) printf("Outofspace!\n"); else s->top=-1; return(s);}（2）判?？张袟？者\算，即判斷一個棧是否為空棧，為空時，返回TRUE，否則返回FALSE。具體算法描述如下：【算法14.2】intEmpty_SeqStack(SeqStack*s)/*判斷棧s是否為空*/{if(s->top==-1)return(TRUE);elsereturn(FALSE);}第9頁/共42頁（3）進棧入棧運算，即往棧中插入(或稱為壓入或推入)一個值為x的新元素。完成這一操作的基本步驟：(1)首先判斷棧是否已滿；(2)當棧不滿時，先修改棧頂指針，將其值加1；(3)然后把元素x放入棧頂指針指向的位置中。具體算法描述如下：【算法14.3】intPush_SeqStack(SeqStack*s,Elemtypex)/*向棧s中壓入一個新元素x為棧頂元素，并返回成功與否的標志*/{if(s->top==MaxSize-1){printf("Overflow!\n");return(FALSE);/*棧滿不能入棧，返回FALSE*/}

else{s->top++;s->data[s->top]=x;return(TRUE);/*操作成功，返回TRUE*/}}第10頁/共42頁（4）出棧出棧運算，即從棧中刪除(或稱為彈出)一個元素。當棧不空時，可通過將棧頂指針減1，達到元素刪除的目的。這里需要說明的是，所謂的刪除，只是將棧頂位置下移一位，這樣原來的棧頂元素就認為不包括在棧中了。實際上，該元素還存在于原來的存儲單元中，只是當新的元素入棧時，會將其覆蓋。具體算法描述如下：【算法14.4】intPop_SeqStack(SeqStack*s,Elemtype*x)/*若棧s不為空，則刪除棧頂元素，并返回棧頂元素值和刪除成功與否的標志*/{if(s->top==-1){printf("Underflow!\n");return(FALSE);/*?？詹荒艹鰲?，返回FALSE*/}else{*x=s->data[s->top];s->top--;/*修改棧頂指針*/return(TRUE);} /*棧頂元素存入*x，返回TRUE*/}第11頁/共42頁（5）取棧頂元素取棧頂元素運算，即當棧不為空時，將棧頂元素取出，而棧本身沒有發(fā)生任何變化。具體算法描述如下：【算法14.5】ElemtypeTop_SeqStack(SeqStack*s)/*當棧s不為空時，求棧頂元素*/{ifs->top!==-1return(s->data[s->top]);elsereturn(SPECIAL); /*棧為空，返回一個棧中沒有的特殊值*/}說明：(1)對于順序棧，入棧時，應(yīng)首先判棧是否已滿，棧滿的條件為s->top==MaxSize-1，棧滿時，不能入棧；否則出現(xiàn)空間溢出，引起上溢錯誤。(2)出棧和讀棧頂元素操作，應(yīng)先判棧是否為空，為空時不能操作，否則產(chǎn)生下溢錯誤。通常?？諘r常作為一種控制轉(zhuǎn)移的條件。第12頁/共42頁14.2隊列14.2.1什么是隊列14.2.2隊列的基本操作第13頁/共42頁14.2.1什么是隊列

隊列（Queue）是另一種操作受限的線性表，它是只允許在表的一端進行插入，而在另一端進行刪除的線性表。能進行插入的一端稱為隊列的尾（rear），能進行刪除的一端稱為隊列的頭（front）。先進入隊列的元素稱為隊列的頭元素（隊列的頭），最后進入隊列中的元素稱為隊列的尾元素（隊列的尾）。隊列稱為先進先出的線性表（FirstInFirstOut），簡稱FIFO表。例如，一個有六個元素的隊列q=(a1、a2、a3、a4、a5、a6)，那么a1就是隊頭元素，a6則是隊尾元素。入隊的順序依次為a1、a2、a3、a4、a5、a6，那么出隊時的順序?qū)⒁廊皇莂1、a2、a3、a4、a5、a6，也就是說，a1離開隊列后，a2才能退出隊列，a1、a2、a3、a4、a5都離開后，a6才能退出隊列。隊列q的示意圖如圖14.3所示。

圖14.3隊列q的示意圖第14頁/共42頁14.2.2隊列的基本操作隊列的基本操作：（1）Init_Queue(q)（2）IsEmpty_Queue(q)（3）En_Queue(q,x)（4）Out_Queue(q,x)（5）GetHead_Queue(q,x)第15頁/共42頁與棧類似，隊列通常有兩種實現(xiàn)方法，即順序隊列實現(xiàn)和鏈式隊列實現(xiàn)。隊列的順序存儲結(jié)構(gòu)稱為順序隊，它由一個一維數(shù)組(用于存儲隊列中元素)及兩個分別指示隊頭和隊尾的變量組成，這兩個變量分別稱為隊頭指針和隊尾指針(注意它們并非指針型變量)。因為在操作過程中，隊頭位置和隊尾位置經(jīng)常變化，所以設(shè)置了頭、尾兩個指針。通常約定隊尾指針指示隊尾元素在一維數(shù)組中的當前位置，隊頭指針指示隊頭元素在一維數(shù)組中的當前位置的前一個位置(這樣設(shè)置是為了某些操作的方便，并不是唯一的方法)。由此可見順序隊列實際上就是運算受限制的順序表。順序隊列的類型定義如下：#defineMaxSize線性表可能達到的最大長度typedefstruct{Elemtypedata[MaxSize];/*隊員的存儲空間*/intfront,rear;/*隊頭，隊尾指針*/}SeqQueue;定義一個指向隊的指針變量為SeqQueue*sq第16頁/共42頁

隊列的數(shù)據(jù)區(qū)為：sq->data[0]…sq->data[MaxSize-1]。每當插入新的隊尾元素時，在不考慮溢出的情況下，隊尾指針加1，指向新位置后，元素入隊。操作如下：sq->rear++;sq->data[sq->rear]=x;每當刪除隊頭元素時，在不考慮隊空的情況下，隊頭指針加1，表明隊頭元素出隊。操作如下：sq->front++;x=sq->data[sq->front];/*原隊頭元素送x中*/整個隊列的數(shù)據(jù)區(qū)為sq->data[0]至sq->data[MaxSize-1]。隊中元素的個數(shù)m為隊尾指針sq->rear減去隊頭指針sq->front的值。隊滿時，m=MaxSize；隊空時，m=0。置空隊則為sq->front=sq->rear=-1;如圖14.4所示，是一個隊列的操作示意圖，它描述了隊列的變化過程。

圖14.4隊列操作示意圖

第17頁/共42頁從圖14.4中可以看出，在這樣的順序隊列中，入隊操作就是要在隊尾增加元素，并將尾指針rear后移。出隊時，則是頭指針front后移。進行了一定數(shù)量的入隊和出隊后，會使整個隊列整體向后移動。這樣就可能會出現(xiàn)圖14.4(d)中的情況：隊尾指針rear已指到數(shù)組的最后一個元素，即rear==MaxSize-1，此時若再執(zhí)行入隊操作，便會出現(xiàn)溢出。然而，由于在此操作之前可能也執(zhí)行了若干次出隊操作，因而數(shù)組的前面部分可能還有閑置的元素空間，即這種溢出并非是真的沒有可用的存儲空間，故稱這種溢出現(xiàn)象為假溢出。顯然，必須要解決假溢出問題，才能保證隊列結(jié)構(gòu)的正確應(yīng)用。

第18頁/共42頁采用循環(huán)結(jié)構(gòu)就可以解決假溢出的問題，具體方法是：將數(shù)組元素data[0]看作是data[MaxSize-1]的下一個存儲位置，也就是說，將數(shù)組看作是一個循環(huán)結(jié)構(gòu)。這樣，當執(zhí)行入隊或出隊操作時，如果原指針rear或front的值為MaxSize-1，即已經(jīng)指向了數(shù)組的最后一個元素時，則執(zhí)行入隊或出隊操作后，相應(yīng)指針的值就要變?yōu)?。這樣就可以使被刪除的結(jié)點在被使用，稱這種形式的隊列為循環(huán)隊列，如圖14.5所示。圖14.5循環(huán)隊列示意圖第19頁/共42頁循環(huán)隊列操作如圖14.6所示。圖14.6循環(huán)隊列操作示意圖第20頁/共42頁

隊列的鏈式存儲結(jié)構(gòu)就是用一個線性鏈表來表示隊列，隊列中的每個元素對應(yīng)鏈表中的一個結(jié)點，這樣的隊列簡稱鏈式隊列。在采用鏈式隊列存儲時，首先要確定鏈表的形式及隊尾的位置。其討論如下：(1)一個鏈式隊列顯然需要兩個分別指示隊頭和隊尾的指針(分別稱為頭指針和尾指針)才能唯一確定。由于隊列的入隊和出隊操作分別是在隊尾和隊頭進行，故將鏈表頭作為隊頭、鏈表表尾作為隊尾比較合適。出隊時，只需要進行刪除表頭的操作，而入隊時所要做的操作是在表尾添加結(jié)點。(2)和線性表的單鏈表一樣，為了操作方便起見，也給鏈隊列添加一個頭結(jié)點，并令頭指針指向頭結(jié)點。鏈式隊列的結(jié)構(gòu)如圖14.7所示。圖14.7鏈式隊列示意圖第21頁/共42頁鏈式隊列的結(jié)點類型描述如下：typedefstructqueuenode/*結(jié)點結(jié)構(gòu)*/{Elemtypedata;structqueuenode*next;}QueueNode;為了強調(diào)隊頭和隊尾是隊列的屬性，將隊列封裝，引入鏈式隊列類型：typedefstruct{QueueNode*front,*rear; /*隊頭和隊尾指針*/}LinkQueue;按這種思想建立的帶頭結(jié)點的鏈式隊列如圖14.8所示。圖14.8頭尾指針封裝在一起的鏈式隊列第22頁/共42頁14.3樹14.3.1什么是樹14.3.2二叉樹的概念及性質(zhì)14.3.3二叉樹的存儲及遍歷第23頁/共42頁14.3.1什么是樹

1.樹的定義樹（Tree）是n（n≥0）個結(jié)點的有限集合。當n＝0時，稱這棵樹為空樹；當n>0時，該集合需滿足以下條件：（1）有且僅有一個稱為根（root）的結(jié)點，它沒有直接前驅(qū)，但有零個或者多個直接后繼。（2）其余n-1個結(jié)點可以被劃分成m（m>0）個互不相交的有限集T1，T2，…，Tm，其中每一個集合Ti（1≤i≤m）又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零個或者多個直接后繼?？梢姌涞亩x是一個遞歸定義，它反映了樹的固有特性，因為一棵樹是由根和它的子樹構(gòu)成，而子樹又由子樹的根和更小的子樹構(gòu)成。樹的表示形式如圖14.9所示。

圖14.9樹的一般形式第24頁/共42頁2.樹的常用術(shù)語結(jié)點：包含一個數(shù)據(jù)元素及若干指向其他結(jié)點的分支信息。結(jié)點的度：一個結(jié)點的子樹個數(shù)。圖14.9中，A的度為3，B的度為1。樹的度：樹中結(jié)點的最大度。圖14.9中，樹的度為3。終端結(jié)點(葉子結(jié)點)：度為0的結(jié)點，即無后繼的結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱非終端結(jié)點。孩子結(jié)點：一個結(jié)點的直接后繼結(jié)點。雙親結(jié)點：一個結(jié)點的直接前驅(qū)結(jié)點稱為該結(jié)點的雙親結(jié)點。結(jié)點的層次：根為第一層，根的直接后繼所在的層為第二層，以此類推。樹的深(高)度：樹中結(jié)點的最大層次稱為樹的深度(或高度)。兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。祖先結(jié)點：一個結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。子孫結(jié)點：以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫結(jié)點。有序樹：結(jié)點的子樹從左到右有順序，否則，稱為無序樹。圖14.9中的兩棵樹，若看成是有序樹，它們是不等價的；若看成是無序樹，兩者相等。森林：若干棵的互不相交的樹的集合就是森林，一棵樹除去根結(jié)點后的子樹集合也是森林。圖14.10有序樹和無序樹的比較第25頁/共42頁14.3.2二叉樹的概念及性質(zhì)二叉樹（BinaryTree）是一種特殊的樹形結(jié)構(gòu)，它必須滿足以下兩個條件：（1）樹中每個結(jié)點的度都不大于2；（2）樹中每個結(jié)點的子樹有左右之分，其次序不能任意顛倒。圖14.11給出了二叉樹的五種基本形態(tài)。（a）空二叉樹（b）只有根結(jié)點的二叉樹（c）只有左子樹的二叉樹（d）只有右子樹的二叉樹（e）左右子樹均非空的二叉樹圖14.11二叉樹的五種基本形態(tài)第26頁/共42頁滿二叉樹：一棵深度為k并且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。在滿二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有最大結(jié)點樹。圖14.12所示的二叉樹，即為一棵滿二叉樹。完全二叉樹：深度為k，結(jié)點數(shù)為n的二叉樹，當且僅當其每個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)，稱為完全二叉樹。完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在層次最大的兩層上；對任意一結(jié)點，若其右分支下的子孫的最大層次是L，則其左分支下的子孫的最大層次一定是L或L+1。

圖14.13完全二叉樹圖14.12滿二叉樹第27頁/共42頁由于二叉樹是一種特殊的樹，故前面所介紹的有關(guān)樹的術(shù)語都適用于二叉樹。另外二叉樹還具有下列性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。性質(zhì)2：深度(高度)為k的二叉樹最大結(jié)點數(shù)為2k-1(k>0)。性質(zhì)3：對任意一棵二叉樹，如果葉子結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則有n0=n2+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為。其中表示不大于x的最大整數(shù)。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹從上到下，從左到右對結(jié)點編號為1，2，…，n，然后按此編號將該二叉樹中各結(jié)點順序地存放于一個一維數(shù)組中，并簡稱編號為j的結(jié)點為j(1≤j≤n)，則有如下結(jié)論成立：(1)若j=1，則結(jié)點j為根結(jié)點，無雙親，否則j的雙親為；(2)若2j≤n，則結(jié)點j的左孩子為2j，否則無左孩子。即編號為j且滿足2j>n的結(jié)點為葉子結(jié)點；(3)若2j+1≤n，則結(jié)點j的右孩子為2j+1，否則無右孩子；(4)若結(jié)點j序號為奇數(shù)且不等于1，則它的左兄弟為j-1；(5)若結(jié)點j序號為偶數(shù)且不等于n，它的右兄弟為j+1。第28頁/共42頁14.3.3二叉樹的存儲及遍歷1.二叉樹的存儲結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每一個結(jié)點最多可以有兩個后繼。二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。（1）順序存儲結(jié)構(gòu)此結(jié)構(gòu)是將二叉樹的所有結(jié)點，按照一定的次序，存儲到一片連續(xù)的存儲單元中。因此，必須將結(jié)點排成一個適當?shù)木€性序列，使得結(jié)點在這個序列中的相應(yīng)位置能反映出結(jié)點之間的邏輯關(guān)系。這種結(jié)構(gòu)特別適用于完全二叉樹。在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上層到下層，逐層從左到右給所有結(jié)點編號，就能得到一個足以反映整個二叉樹結(jié)構(gòu)的線性序列。因此，可以對樹的類型作如下說明：#defineMAX50typedefstruct{ElementTypea[MAX];intcount;}BinTree;在結(jié)構(gòu)體類型中，count成員項用于記錄完全二叉樹中結(jié)點的個數(shù)。第29頁/共42頁將數(shù)組下標作為結(jié)點名稱(編號)，就可將二叉樹中所有結(jié)點的標號存儲在一維數(shù)組中。例如，圖14.14中的二叉樹的順序存儲結(jié)構(gòu)如圖14.15所示。

圖14.14完全二叉樹的結(jié)點編號圖14.15完全二叉樹的順序存儲示意圖ABCDEFGHIJKLMNOPQ1234567891011121314151617第30頁/共42頁對于圖14.14所示的一棵完全二叉樹，做如下實現(xiàn)為(1)給出某一結(jié)點編號x，求出該結(jié)點的左孩子。算法如下：【算法14.6】typedefcharElementTypeElementTypeLChild(BinTreeBT,intx){if(x>=1&&2*x<BT.count)return(BT.a[2*x-1];else{printf(“該結(jié)點無左孩子”);return(‘#’);/*用#表示孩子為空*/}}(2)給出某一結(jié)點的編號x，求出該結(jié)點的雙親。算法如下：【算法14.7】ElementTypeParent(BinTreeBT,intx){if(x<=1||x>BT.count){printf(“樹中無此結(jié)點或無雙親結(jié)點”);return(‘#’);}elsereturn(BT.a[x/2]);}順序存儲方式對于一棵完全二叉樹來說非常方便，但對于一般的二叉樹，空間的浪費太大，這是順序存儲結(jié)構(gòu)的一大缺點。為解決這一問題，可用鏈式存儲結(jié)構(gòu)來存儲樹。第31頁/共42頁（2）鏈式存儲結(jié)構(gòu)將一個結(jié)點分成三部分，一部分存放結(jié)點本身信息，另外兩部分為指針，分別存放左、右孩子的地址。結(jié)點形式如右圖所示：LChildDataRChild對于圖14.15所示二叉樹：

(a)完全二叉樹(b)非完全二叉樹圖14.15兩種不同類型的樹用二叉鏈表形式描述，如圖14.16所示。

(a)完全二叉樹的二叉鏈表表示法(b)非完全二叉樹的二叉鏈表表示法圖14.16二叉樹的二叉鏈表表示法

lchilddatarchild第32頁/共42頁1)二叉鏈表的數(shù)據(jù)類型數(shù)據(jù)類型描述如下：typedefstructnode{ElementTypedata;structnode*LChild,*RChild;}BinNode,*BinTree;2)二叉鏈表的建立為了用二叉鏈表表示一棵二叉樹，在此介紹建立二叉鏈表的算法(假設(shè)ElementType為char型)。假設(shè)二叉鏈表的數(shù)據(jù)類型描述如剛才所述，為建立二叉鏈表，用一個一維數(shù)組來模擬隊列，存放輸入的結(jié)點，但是，輸入結(jié)點時，必須按完全二叉樹形式，才能使結(jié)點間滿足性質(zhì)5，若為非完全二叉樹，則必須給定一些假想結(jié)點(虛結(jié)點)，使之符合完全二叉樹形式。為此，在輸入結(jié)點值時，存在的結(jié)點則輸入它對應(yīng)的字符，不存在的結(jié)點(虛結(jié)點)，輸入逗號，最后以一個特殊符號“#”作為輸入的結(jié)束，表示建二叉鏈表已完成。建成的二叉鏈表可以由根指針root唯一確定。算法描述如下：第33頁/共42頁【算法14.8】#include<stdio.h>typedefcharElementType;typedefstructnode{ElementTypedata;structnode*LChild,*RChild;}BinNode,*BinTree;建立樹的函數(shù)如下：BinTreeCreate(){BinTreeq[100],s;/*定義q數(shù)組作為隊列存放二叉鏈表中結(jié)點，100為最大容量，s為二叉鏈表中結(jié)點*/BinTreeroot; /*二叉鏈表的根指針*/intfront=1,rear=0;/*定義隊列的頭、尾指針*/charch; /*結(jié)點的data域值*/root=NULL;ch=getchar();while(ch!=’#’) /*輸入值為#號,算法結(jié)束*/{s=NULL;if(ch!=’,’)/*輸入數(shù)據(jù)不為逗號,表示不為虛結(jié)點,否則為虛結(jié)點*/{s=(BinNode*)malloc(sizeof(BinNode));s->data=ch;s->LChild=NULL;s->RChild=NULL;}

rear++;q[rear]=s; /*新結(jié)點或虛結(jié)點進隊*/if(rear==1)root=s;else{if((s!=NULL)&&(q[front]!=NULL)){if(rear%2==0)/*rear為偶數(shù),s為雙親左孩子*/q[front]->LChild=s;else/*rear為奇數(shù),s為雙親右孩子*/q[front]->RChild=s;}if(rear%2==1)front++; /*出隊*/}ch=getchar();}returnroot;}第34頁/共42頁2.二叉樹的遍歷二叉樹的遍歷是指按照一定的規(guī)律或路徑對二叉樹中的每一個結(jié)點進行訪問且僅訪問一次。遍歷在順序結(jié)構(gòu)中非常容易實現(xiàn)，但是在非線性結(jié)構(gòu)的二叉樹中，由于每個結(jié)點都有可能存在兩棵子樹，因此，遍歷操作就是將二叉樹中結(jié)點按一定規(guī)律線性化的操作，目的是將非線性化結(jié)構(gòu)變成線性化的訪問序列。二叉樹的遍歷操作是二叉樹中最基本的運算。日常習慣中，訪問順序一般按先左后右的順序。若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先序法(先根次序法)，中序法(中根次序法)，后序法(后根次序法)。三種遍歷的遞歸算法如下。1)先序法(DLR)若二叉樹為空，則空操作，否則執(zhí)行如下三個操作：訪問根結(jié)點；先序遍歷左子樹；先序遍歷右子樹。2)中序法(LDR)若二叉樹為空，則空操作，否則執(zhí)行如下三個操作：中序遍歷左子樹；訪問根結(jié)點；中序遍歷右子樹。3)后序法(LRD)若二叉樹為空，則空操作，否則執(zhí)行如下三個操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點。有一棵二叉樹，如圖14.19所示：

則其按先序、中序、后序遍歷得到的訪問序列如下。(1)先序遍歷序列：A、B、D、E、G、H、C、F；(2)中序遍歷序列：D、B、G、E、H、A、C、F；(3)后序遍歷序列：D、G、H、E、B、F、C、A。圖14.19樹第35頁/共42頁以二叉鏈表作為存儲結(jié)構(gòu)，描述二叉樹的遞歸遍歷算法如下。(1)先序遍歷算法，算法如下：【算法14.9】voidPreOrder(BinTreer){if(r!=NULL) /*NULL值為0，也可用if(r)*/{Visit(r->data); /*訪問根結(jié)點*/PreOrder(r->LChild); /*先序遍歷左子樹*/PreOrder(r->RChild); /*先序遍歷右子樹*/}}(2)中序遍歷算法，算法如下：【算法14.10】voidMidOrder(BinTreer){if(r){MidOrder(r->LChild); /*中序遍歷左子樹*/Visit(r->data); /*訪問根結(jié)點*/MidOrder(r->RChild); /*中序遍歷右子樹*/}}(3)后序遍歷算法，算法如下：【算法14.11】voidPreOrder(BinTreer){if(r){Visit(r->data);PreOrder(r->LChild);PreOrder(r->RChild);Visit(r->data);}}第36頁/共42頁14.4典型習題分析解答【例14.1】一個棧的入棧序列為a，b，c，d，e，則下列序列中不可能是棧的輸出序列的是________。(A)edcba(B)decba(C)dceab(D)abcde答案：C分析：本題主要考點是棧的特點：先進后出，所以eab是不可能出現(xiàn)的。d第一個出棧，說明a，b，c都已經(jīng)入棧，然后可以是棧頂元素c先出棧，再將e入棧然后出棧，這時a，b都已經(jīng)入棧，所以出棧的序列只能是b，a?！纠?4.2】若已知一個棧的入棧序列為1，2，3，…，n，其輸出序列為s1，s2，s3，…，sn，若s1=n，則si（1≤i≤n）為________。(A)i(B)n=i(C)n-i+1(D)不確定答案：C分析：當s1=n，即n是第一個最早出棧的，根據(jù)棧的原理，n必定是最后一個入棧的，所以輸入的順序必定是1，2，3，…，n，即n出棧的之后1，2，3，…，n-1都已經(jīng)入棧，所以出棧的序列必定為n，…，3，2，1，所以答案選C。第37頁/共42頁【例14.3】對于一個棧，給出輸入項a，b，c。如果輸入項序列由a，b，c所組成，試給出全部可能的輸出序列________________________________。答案：abc，acb，bac，bca，cba分析：本題利用棧的“先進先出”的特點，有如下幾種情況：a進a出b進b出c進c出產(chǎn)生的輸出序列為abca進a出b進c進c出b出產(chǎn)生的輸出序列為acba進b進b出a出c進c出產(chǎn)生的輸出序列為baca進b進b出c進c出a出產(chǎn)生的輸出序列為baca進b進c進c出b出a出產(chǎn)生的輸出序列為cba【例14.4】在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，則當做出棧處理時，top變化為________。(A)top--(B)top=0(C)top不變（D)top++答案：A分析：順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，同時設(shè)置了一個棧頂指針top來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧，當做出棧操作時top指針應(yīng)該下移?！纠?4.5】已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為________。(A)GEDHFBCA(B)DGEBHFCA(C)ABCDEFGH(D)ACBFEDHG答案：B分析：利用前序和中序遍歷的方法可以確定二叉樹的結(jié)構(gòu)，具體步驟如下：①前序遍歷的第一個結(jié)點A為樹的根結(jié)點；②中序遍歷中A的左邊的結(jié)點為A的左子樹，A的右邊的結(jié)點為A的右子樹；③再分別對A的左右子樹進行上述處理，直到每個結(jié)點都找到正確的位置。第38頁/共42頁【例14.6】樹是結(jié)點的集合，它的根結(jié)點的數(shù)目是________。(A)有且只有一個(B)1或者多于1(C)0或1(D)至少2答案：C分析：樹是n（n≥0）個結(jié)點的有限集合，當n=0時稱為空樹，對于空樹沒有根結(jié)點，即根結(jié)點的個數(shù)為0，對于非空樹有且只有一個根結(jié)點，所以樹的根結(jié)點的數(shù)目為0或者1?！纠?4.7】棧和隊列的共同特點是________。(A)都是先進先出(B)都是先進后出(C)只允許在端點處插入和刪除元素(D)沒有共同點答案：C分析：棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區(qū)別是：棧只允許在表的一端進行插入或刪除操作，是一種“后進先出”的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種“先進先出”的線性表?！纠?4.8】在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為________。(A)32(B)31(C)16(D)15答案：C分析：本題考察的是滿二叉樹的性質(zhì)。所謂滿二叉樹是指這樣的一種二叉樹：除了最后一層外，每一層上的所有的結(jié)點都有兩個葉子結(jié)點。這就是說，在滿二叉樹中，層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2k-1個結(jié)點，并且深度為m的滿二叉樹有2m-1個結(jié)點。第39頁/共42頁【例14.9】具有3個結(jié)點的二叉樹有________。(A)2種形態(tài)