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

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

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

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

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

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

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

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

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

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

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

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

圖14.4隊(duì)列操作示意圖

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

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

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

1.樹的定義樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱這棵樹為空樹；當(dāng)n>0時(shí)，該集合需滿足以下條件：（1）有且僅有一個(gè)稱為根（root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或者多個(gè)直接后繼。（2）其余n-1個(gè)結(jié)點(diǎn)可以被劃分成m（m>0）個(gè)互不相交的有限集T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或者多個(gè)直接后繼。可見樹的定義是一個(gè)遞歸定義，它反映了樹的固有特性，因?yàn)橐豢脴涫怯筛退淖訕錁?gòu)成，而子樹又由子樹的根和更小的子樹構(gòu)成。樹的表示形式如圖14.9所示。

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

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

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

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

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

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

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

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