數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)-3

第一課緒論

覆蓋的知識點(diǎn)最小集：我們的地址是，重慶市九龍坡區(qū)白市驛鎮(zhèn)金橋2號重慶市農(nóng)業(yè)學(xué)校

1.數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)的概念

2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的概念

3.算法設(shè)計(jì)時(shí)的注意事項(xiàng)

4.時(shí)間復(fù)雜度的概念及度量方法

5.空間復(fù)雜度的概念及度量方法

知識點(diǎn)細(xì)化：

1-001數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)

科。數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的操作三部分組成。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素

的集合，是數(shù)據(jù)的子集。數(shù)據(jù)是所有需輸入計(jì)算機(jī)并為程序所處理的對象的總稱。

1-002數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，對后面的名詞要能區(qū)分哪些是屬于邏輯結(jié)構(gòu)哪些屬于物理結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素間的邏輯關(guān)系，分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)，或分為

線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)元素及其間邏輯關(guān)系在計(jì)算機(jī)中的表示，也稱存儲結(jié)構(gòu)。其中數(shù)據(jù)元素間

關(guān)系的表示有順序映象(順序存儲結(jié)構(gòu))和非順序映象(鏈?zhǔn)酱鎯Y(jié)構(gòu))兩種方式，前者以存儲地址上的

聯(lián)系來體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系，后者則通過指針的指向來體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系。

1-003算法設(shè)計(jì)時(shí)的注意事項(xiàng)

算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法的特性：有窮性、確定性、可行性、

零或多個(gè)輸入、一或多個(gè)輸出。算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、高效性。

1-004時(shí)間復(fù)雜度的概念及度量方法

算法的時(shí)間復(fù)雜度是算法執(zhí)行效率的量度，記作：T(n)=O(f(n)),其中n為問題的規(guī)模。

衡量算法效率時(shí)，通常在算法中選擇一種不可再分解的基本操作(該操作的重復(fù)執(zhí)行次數(shù)應(yīng)與算法的

執(zhí)行時(shí)間成正比)，若該操作的執(zhí)行次數(shù)為f(n),則記該算法的時(shí)間復(fù)雜度為O(f(n))。

若基本操作的執(zhí)行次數(shù)與輸入數(shù)據(jù)有關(guān)，則可求算法的平均時(shí)間復(fù)雜度或最壞時(shí)間復(fù)雜度。一般，當(dāng)

所有可能的輸入數(shù)據(jù)集及其出現(xiàn)概率均可知時(shí)，可求算法的平均時(shí)間復(fù)雜度，否則求最壞情況下的時(shí)間復(fù)

雜度。

1-005空間復(fù)雜度的概念及度量方法

算法的空間復(fù)雜度是算法執(zhí)行時(shí)所需存儲空間的量度，記作：S(n)=O(f(n)),其中n為問題的規(guī)模。

分析算法空間復(fù)雜度時(shí)，一般只考慮執(zhí)行算法所需輔助空間，但若輸入數(shù)據(jù)所占空間與算法本身有關(guān),

則也應(yīng)計(jì)算在內(nèi)。若執(zhí)行算法所需輔助空間與輸入數(shù)據(jù)有關(guān)，則可求最壞情況下的空間復(fù)雜度。

第二課線性表

覆蓋的知識點(diǎn)最小集：

1.線性表的定義和基本操作

2.線性表的實(shí)現(xiàn)

(1)順序存儲

⑵鏈?zhǔn)酱鎯?/p>

(3)線性表的應(yīng)用

知識點(diǎn)細(xì)化：

2-010線性表基本概念

線性表是n個(gè)數(shù)據(jù)元素構(gòu)成的有限序列。表長指線性表中數(shù)據(jù)元素的個(gè)數(shù)，表長20?？毡碇副黹L為

0的線性表。若線性表非空，則表中第一個(gè)元素沒有直接前趨，有且僅有一個(gè)直接后繼；表中最后一個(gè)元

素沒有直接后繼，有且僅有一個(gè)直接前趨；其余每個(gè)數(shù)據(jù)元素有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接

后繼。

2-011線性表的基本操作

(1)取元素

GetElem(L,i,&e)

初始條件：線性表L已存在，iWiWListLength(L)

操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值

(2)插入

Li>tInsert(&L,i,e)

初始條件：線性表L已存在，1WiWListLength(L)+l

操作結(jié)果：在L中第i個(gè)位置之前插入數(shù)據(jù)元素e,L的長度加1

(3)刪除

LiitDelete(&L,i,&e)

初始條件：線性表L已存在且非空，iWiWLislLength(L)

操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1

2-012線性表的順序存儲方式

用一組地址連續(xù)的存儲單元依次存儲線性表中數(shù)據(jù)元素，以數(shù)據(jù)元素物理地址上的相鄰關(guān)系表示其邏

輯上的先后關(guān)系。以順序存儲方式保存的線性表也稱順序表。

在順序表中訪問結(jié)點(diǎn)時(shí)，由丁第一個(gè)元素就存儲在相對地址為i-1的位置上(隨機(jī)存取)，算法時(shí)間復(fù):

雜度為。⑴。

設(shè)順序表長為n,則在第i(lWiWn+1)個(gè)元素前插入時(shí)，需移動(dòng)n-i+1個(gè)元素。設(shè)在各位置上插入元

素的概率相等，則需移動(dòng)元素的平均個(gè)數(shù)為n/2,算法時(shí)間復(fù)雜度為O(n)。

設(shè)順序表長為n,則刪除第i(iWiWn)個(gè)數(shù)據(jù)元素時(shí)，需移動(dòng)n-i個(gè)元素。設(shè)刪除任一元素的概率相

等，則需移動(dòng)元素的平均個(gè)數(shù)為：(n-l)/2,算法時(shí)間復(fù)雜度為O(n)。

2-013以靜態(tài)分配方法實(shí)現(xiàn)順序表

由于線性表的長度是可變的，采用靜態(tài)分配，則需定義最大可能長度，并需設(shè)變量記錄線性表長。

#defineMAXSIZE1000〃最大可能長度

typedefstruct(

ElemTypeelem[MAXSIZE];〃保存數(shù)據(jù)元素

intlen;〃線性表長度

JSqList;〃順序表類型名(靜態(tài)線性表就是用數(shù)組來存儲的那種形式)

2-014以一次性動(dòng)態(tài)分配方法實(shí)現(xiàn)順序表

采用一次性的動(dòng)態(tài)分配方法時(shí)，需定義最大可能長度，并需設(shè)變量記錄線性表長。

#defineMAXSIZE1000〃最大可能長度

typedcfstruct{

ElemType*elem;//保存首地址

intlen;〃線性表長度

ISqList;〃順序表類型名（動(dòng)態(tài)的就是需要用指針來實(shí)現(xiàn)的）

2-015以帶增量的動(dòng)態(tài)分配方法實(shí)現(xiàn)順序表

采用帶增量的動(dòng)態(tài)分配方法時(shí)，需定義初始分配量和增量，并需分別設(shè)變量以記錄線性表長及當(dāng)前分

配總量。

#defineLISTJNIT_SIZE100//初始分配量，以數(shù)據(jù)元素個(gè)數(shù)為單位

#defineLISTINCREMENT10〃增量

typedefstruct）

ElemType*elem;//保存首地址

intlen;〃線性表長度

intlistsize;〃當(dāng)前分配量，以數(shù)據(jù)元素個(gè)數(shù)為單位

JSqList;〃順序表類型名

在該結(jié)構(gòu)上實(shí)現(xiàn)三個(gè)基本操作。

2?016線性表的鏈?zhǔn)酱鎯Ψ绞?/p>

用一組任意的（可連續(xù)可不連續(xù)）存儲單元存儲線性表中數(shù)據(jù)元素，用指針來表示數(shù)據(jù)元素間的邏輯

關(guān)系。根據(jù)所用指針的類型、個(gè)數(shù)、方法等的不同，又可分為：、循環(huán)鏈表、雙向線性鏈表（單鏈表）鏈

表、雙向循環(huán)鏈表、靜態(tài)鏈表等。

2?017線性鏈表（單鏈表）及其特點(diǎn)

每個(gè)結(jié)點(diǎn)由兩個(gè)域組成，其中數(shù)據(jù)域用以保存數(shù)據(jù)元素的值，指針域用以保存其直接后繼結(jié)點(diǎn)的絕對

地址。表中最后一個(gè)結(jié)點(diǎn)的指針域值為空指針NULL。在首元結(jié)點(diǎn)前還可附設(shè)頭結(jié)點(diǎn)，以方便運(yùn)算的實(shí)現(xiàn)

（無論表空與否，頭指針值不變；插入時(shí)不必特別判斷是否在第一個(gè)元素之前插入：刪除時(shí)不必特別判斷

是否刪除第一個(gè)元素）。頭結(jié)點(diǎn)的數(shù)據(jù)域一般不使用。頭結(jié)點(diǎn)（若表中不含頭結(jié)點(diǎn)則為首元結(jié)點(diǎn)）的地址

保存在頭指針中。

typedefstructLNode!

ElemTypedata;〃數(shù)據(jù)域

slruclLNodc*ncxl;〃指針域

）LNode,*LinkList;

在該結(jié)構(gòu)上實(shí)現(xiàn)三個(gè)基本操作。

在單鏈表中訪問結(jié)點(diǎn)時(shí)，必須從頭指針開始順序查找該結(jié)點(diǎn)，指針的移動(dòng)是其中的基本操作，查找第

i個(gè)結(jié)點(diǎn)時(shí)需移動(dòng)i-1次。設(shè)查找任一元素的概率相等，則需移動(dòng)指針的平均次數(shù)為（n-l）/2,算法時(shí)間復(fù)雜

度為0（n）。

在單鏈表中插入結(jié)點(diǎn)時(shí)，時(shí)間主要用于查找插入位置，即查找第i-1個(gè)結(jié)點(diǎn)上。算法的時(shí)間復(fù)雜度為

O（n）o

在單鏈表中刪除結(jié)點(diǎn)時(shí)，時(shí)間主要用于查找待刪結(jié)點(diǎn)。算法的時(shí)間復(fù)雜度為O（n）。

2.018循環(huán)鏈表及其特點(diǎn)

循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)同單鏈表，但表中最后一個(gè)結(jié)點(diǎn)的指針域保存頭結(jié)點(diǎn)（若表中不含頭結(jié)點(diǎn)則為首

元結(jié)點(diǎn)）的絕對地址。在循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)均可訪問到表中其余結(jié)點(diǎn)。

循環(huán)鏈表上基本操作的實(shí)現(xiàn)與單鏈表基本相同，主要區(qū)別在于算法中的循環(huán)條件。

2.019雙向鏈表及其特點(diǎn)

2-024線性表的應(yīng)用

基于線性表的各種存儲方式實(shí)現(xiàn)指定的操作，尤其是各種鏈表（帶頭結(jié)點(diǎn)、不帶頭結(jié)點(diǎn)）（僅設(shè)頭指

針、僅設(shè)尾指針、分設(shè)頭尾指針）上插入（當(dāng)前結(jié)點(diǎn)之前，當(dāng)前結(jié)點(diǎn)之后，頭結(jié)點(diǎn)之后，尾結(jié)點(diǎn)之后，其

它位置），刪除（當(dāng)前結(jié)點(diǎn)、前趨結(jié)點(diǎn)、后繼結(jié)點(diǎn)、首元結(jié)點(diǎn)、具它結(jié)點(diǎn)），分解（一表到多表），歸并（多

表合一表），查找（順序表上的順序和折半查找，鏈表上的順序查找）、排序（各種排序方法的實(shí)現(xiàn)）等。

第三課棧、隊(duì)列和數(shù)組

覆蓋的知識點(diǎn)最小集：

1.棧和隊(duì)列的基本概念

2.棧和隊(duì)列的順序存儲結(jié)構(gòu)

3.棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

4.棧和隊(duì)列的應(yīng)用

5.特殊矩陣的壓縮存儲

知識點(diǎn)細(xì)化：

3-001棧的基本概念

棧是限定僅在表尾端進(jìn)行插入、刪除的線性表；表尾端稱棧頂，而稱棧頂元素；表頭端稱棧底，ai稱

棧底元素。棧的長度即棧中元素個(gè)數(shù)。長度為0的棧稱空棧。向棧中插入元素稱入棧，從棧中刪除元素稱

出棧,棧的修改是按后進(jìn)先出的原則進(jìn)行的。

3-002棧的順序存儲方式

與線性表的順序存儲方式類似：三種分配方法；線性表長度分量一棧頂指針分量（指向棧頂元素的下

一個(gè)位置）。以順序存儲方式保存的棧稱順序棧。

設(shè)采用靜態(tài)分配。實(shí)現(xiàn)入棧和出棧操作。

#defineMAXSIZE1000〃棧的最人容量

typedefstruct（

ElemTypeelem[MAXSIZE];〃保存數(shù)據(jù)元素，以低地址為棧底

inttop;〃棧頂指針

JSqStack;

3?003棧的鏈?zhǔn)酱鎯Ψ绞?/p>

與單鏈表類似：帶/不帶頭結(jié)點(diǎn)；插入、刪除操作點(diǎn)（即棧頂端）放在靠近頭指針的一端。以鏈?zhǔn)酱鎯?/p>

方式保存的棧稱鏈棧。

實(shí)現(xiàn)入棧和出棧操作

typedefstructSNode（

ElemTypedata;

structSNodc*next;

}SNode,*LinkStack;

3-101隊(duì)列的基本概念

隊(duì)列是限定僅在表尾端進(jìn)行插入，而在表頭端進(jìn)行刪除的線性表。表頭端稱隊(duì)頭，a1稱隊(duì)頭元素；表

尾端稱隊(duì)尾，“稱隊(duì)尾元素。隊(duì)列的長度即隊(duì)列中元素個(gè)數(shù)。長度為。的隊(duì)列稱空隊(duì)。向隊(duì)列中插入元素

稱入隊(duì)，從隊(duì)列中刪除元素稱出隊(duì)。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的。

雙端隊(duì)列是限定僅在表的兩端進(jìn)行插入刪除操作的線性表（如果規(guī)定從哪端入的只能從哪端出，則退

化為兩個(gè)棧底相鄰的棧）。輸入受限的雙端隊(duì)列是插入操作僅在一端進(jìn)行而刪除操作可在兩端進(jìn)行的線性

表。輸出受限的雙端隊(duì)列是刪除操作僅在--端進(jìn)行而插入操作可在兩端進(jìn)行的線性表。

3-102隊(duì)列的順序存儲方式

線性表的順序存儲方式f去除線性表長度分量，添加指向隊(duì)頭元素所在位置的隊(duì)頭指針以及指向隊(duì)尾

元素的下一個(gè)位置的隊(duì)尾指針一產(chǎn)生假溢出問題f三個(gè)解決方案：（1）每刪一個(gè)元素，其余元素向前移；（2）

發(fā)生假溢出時(shí)才移動(dòng)剩余元素；（3）采用循環(huán)隊(duì)列，不移動(dòng)元素，但不能采用帶增量的動(dòng)態(tài)分配，且需解決

隊(duì)空、隊(duì)滿判定條件相同的問題，解決方法可為：①添加長度分量（添加標(biāo)志分量）②浪費(fèi)一個(gè)元素的存

儲空間。

循環(huán)隊(duì)列另一設(shè)計(jì)方案：以數(shù)組存儲元素，以隊(duì)尾指針指示隊(duì)尾元素所在位置，并記錄隊(duì)列長度。

循環(huán)隊(duì)列只能采用靜態(tài)分配或一次性動(dòng)態(tài)分配，不能采用帶增量的動(dòng)態(tài)分配，因而隊(duì)列最大長度應(yīng)能

預(yù)估。

3-103循環(huán)隊(duì)列的入隊(duì)和出隊(duì)

設(shè)采用一次性動(dòng)態(tài)分配，設(shè)置隊(duì)頭隊(duì)尾指針，以浪費(fèi)一個(gè)元素存儲空間的方式解決隊(duì)空、隊(duì)滿判定條

件相同的問題。

實(shí)現(xiàn)入隊(duì)、出隊(duì)和求隊(duì)列長度操作。

#defineMAXSIZE1000

typedefstruct{

ElemType*base;

intfront;

intrear;

JCirQueue;

3-104隊(duì)列的鏈?zhǔn)酱鎯Ψ绞?/p>

與單鏈表類似：帶/不帶頭結(jié)點(diǎn)；刪除操作點(diǎn)（即隊(duì)頭端）放在靠近頭指針的一端，另設(shè)尾指針，指向

隊(duì)尾元素結(jié)點(diǎn)，以方便插入操作的執(zhí)行。以鏈?zhǔn)酱鎯Ψ绞奖４娴年?duì)列稱鏈隊(duì)列。

鏈隊(duì)列在執(zhí)行出隊(duì)操作時(shí)要考慮空隊(duì)列和隊(duì)列中只有一個(gè)結(jié)點(diǎn)這兩種特殊情況。

3405鏈隊(duì)列的入隊(duì)和出隊(duì)

實(shí)現(xiàn)入隊(duì)和出隊(duì)操作。

typedefstructQNode{

ElemTypedata;

structQNode*next;

}QNode;

typedefstruct（

QNode*front;

QNode*rear;

JLinkQueue;

3-106棧和隊(duì)列的應(yīng)用

棧在表達(dá)式求值、括號匹配、進(jìn)制轉(zhuǎn)換、遞歸問題等中都有應(yīng)用。隊(duì)列在共享打印機(jī)緩沖池、消息隊(duì)

列、二叉樹的層序遍歷、圖的廣度優(yōu)先遍歷等中都有應(yīng)用。

3-107從遞歸到非遞歸

一個(gè)函數(shù)直接或間接調(diào)用自己即為遞歸。

函數(shù)遞歸是因?yàn)椋海?）有很多數(shù)學(xué)函數(shù)是遞歸定義的；（2）有些數(shù)據(jù)結(jié)構(gòu)本身就有遞歸性（廣義表、樹、

二叉樹），其上操作常用遞歸描述；（3）有些問題本身雖無明顯遞歸結(jié)構(gòu)，但用遞歸求解較簡單（漢諾塔）。

遞歸算法可轉(zhuǎn)換為用棧來實(shí)現(xiàn)的半遞歸算法。

3-201對稱陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)卻，ijG[l,n]/[0,n-l],則稱A為n階對稱陣。

壓縮存儲時(shí)用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存對稱陣上或下三角（含對角線）中的

數(shù)據(jù)元素，共n（n+l）/2個(gè)。

對矩陣進(jìn)行壓縮存儲是為了節(jié)省空間，仍屬隨機(jī)存取，但計(jì)算地址的運(yùn)算會復(fù)雜。

3-202上三角陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)C,7￡[1,亞[0.1]且間，C為常量，則稱A為n階上三角陣。上三角陣中下三

角部分元素（不含對角線）的值為常量。

壓縮存儲時(shí)用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存上三角（含對角線）中的數(shù)據(jù)元素，

再加一個(gè)下三角常量，共n（n+l）/2+l個(gè)。

3-203下二角陣的定義及壓縮存儲

若n階方陣A有a產(chǎn)C,且i<j,C為常量，則稱A為n階下三角陣。下三角陣中上三

角部分元素（不含對角線）的值為常量。

壓縮存儲時(shí)用一組地址連續(xù)的存儲單元按行或列優(yōu)先的順序保存下三角（含對角線）中的數(shù)據(jù)元素，

再加一個(gè)上三角常量，共n（n+l）/2+l個(gè)。

3-204對角陣的定義及壓縮存儲

若n階方陣A中除主對角線及其上下若干條對角線上的元素之外，其余元素均為0,則稱對角陣。

將矩陣中的非零元按某種次序（行優(yōu)先、列優(yōu)先、對角線順序等）存儲于一組地址連續(xù)的存儲單元。

對n階x對角陣A進(jìn)行壓縮存儲，采用行優(yōu)先/列優(yōu)先/指定的對角線順序-第一元素為aoo/a”，保存在

足夠大的一維數(shù)組e中。若a.保存在e[k]中，要求由ij值求k值。

3-205稀疏陣的定義及壓縮存儲

設(shè)在mXn矩陣中，有t個(gè)數(shù)據(jù)元素不為零，則通常認(rèn)為當(dāng)B=」一<0.05時(shí)，稱該矩陣為稀疏矩陣,

mxn

其中6稱稀疏因子。

對稀疏矩陣進(jìn)行壓縮存儲時(shí)，可只保存其中非零元，同時(shí)還需指明非零元所處的行列位置及總的行數(shù)、

列數(shù)（可再加非零元個(gè)數(shù)），此即稀疏矩陣的三元組表示法。此時(shí)不能再隨機(jī)存取。

第四課樹與二叉樹

覆蓋的知識點(diǎn)最小集：

I.樹的基本概念

2.二叉樹

(1)二叉樹的定義及具主要特征

(2)二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

(3)二叉樹的遍歷

(4)線索二叉樹的基本概念和構(gòu)造

3.樹、森林

(1)樹的存儲結(jié)構(gòu)

(2)森林與二叉樹的轉(zhuǎn)換

(3)樹和森林的遍歷

4.樹與二叉樹的應(yīng)用

(1)二叉排序樹

⑵平衡二叉樹

(3)哈夫曼(Huffman)樹和哈夫曼編碼

知識點(diǎn)細(xì)化：

4-001樹和結(jié)點(diǎn)

樹是n520)個(gè)結(jié)點(diǎn)的有限集。若n=0則為空樹，記為中。若nWO,貝的⑴有且僅有一個(gè)根結(jié)點(diǎn)；

⑵若n>l,則其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集TI,T2,…,Tm，其中每一集合又是一棵樹，

并稱根的子樹.若將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，即不能互換的，則稱該樹為有序樹，否

則稱無序樹，結(jié)點(diǎn)可分為分支結(jié)點(diǎn)(根結(jié)點(diǎn)+內(nèi)部結(jié)點(diǎn))和葉子結(jié)點(diǎn)°結(jié)點(diǎn)的度即結(jié)點(diǎn)擁有的子樹數(shù)。樹

的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層，余則類

推。樹的深度(高度)即樹內(nèi)結(jié)點(diǎn)的層次的最大值。

4-002二叉樹

二叉樹是具有如下特點(diǎn)的樹型結(jié)構(gòu)：⑴每個(gè)結(jié)點(diǎn)至多只有兩棵子樹；⑵二叉樹的子樹有左右之分。

二叉樹有五種基本形態(tài)：⑴空二叉樹⑵只有根結(jié)點(diǎn)⑶根結(jié)點(diǎn)只有左子樹⑷根結(jié)點(diǎn)只有右子樹⑸根結(jié)點(diǎn)

左右子樹都有。

二叉樹和度為2的有序樹的本質(zhì)區(qū)別在于有序樹上結(jié)點(diǎn)若只有一個(gè)孩子，則孩子無次序之分。

4-003滿二叉樹和完全二叉樹

滿二叉樹是深度為k且有2k-l個(gè)結(jié)點(diǎn)的二叉樹。若含n個(gè)結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)位置與同深度的滿二

叉樹按層序的前n個(gè)結(jié)點(diǎn)位置相對，則稱完全二叉樹,滿二叉樹一定是完全二叉樹，反之未必。若完全二

叉樹上有n個(gè)結(jié)點(diǎn)按層序從1開始編號，則第|_〃2」個(gè)結(jié)點(diǎn)是最后一個(gè)有孩子的結(jié)點(diǎn)；若n是偶數(shù)，則該

完全二叉樹上有一個(gè)度為1的結(jié)點(diǎn)，若n是奇數(shù)，則該完全二叉樹上沒有度為1的結(jié)點(diǎn)。

4-004森林

森林為m(m2。)棵互不相交的樹的集合。

4-101二叉樹性質(zhì)一

在二叉樹的第i層上最多有2皿個(gè)結(jié)點(diǎn)(i21)。

【證明】

⑴當(dāng)i=l時(shí)，只有一個(gè)根結(jié)點(diǎn)。2皿=2°=1,結(jié)論成立。

⑵假設(shè)第k層上最多有2kd個(gè)結(jié)點(diǎn)

???二叉樹中每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子

，第k層結(jié)點(diǎn)的孩子總數(shù)最多為2卜|><2=2卜個(gè)

??,第k+1層上的結(jié)點(diǎn)均為第k層結(jié)點(diǎn)的孩子

工第k+1層上最多有2k=2（k+.個(gè)結(jié)點(diǎn)

⑶由⑴⑵可得結(jié)論成立。

4-102二叉樹性質(zhì)二

深度為k的二叉樹最多有2k.i個(gè)結(jié)點(diǎn)。（k-l）

【證明】由二叉樹性質(zhì)1可知在二叉樹的第i層上最多有2評個(gè)結(jié)點(diǎn)（i2l）,因此深度為k的二叉樹最多結(jié)

2°（T）=2J。

點(diǎn)數(shù)為：Z2'T=2°+2i+...+2J

1-2

深度為k的m叉樹最多有.（用上-l）/（/w-l）個(gè)結(jié)點(diǎn)。

4-103二叉樹性質(zhì)三

對任意二叉樹T,若其葉子結(jié)點(diǎn)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)為m，則n產(chǎn)血+1。

【證明】設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為川

???二叉樹中結(jié)點(diǎn)的度只能為0、1、2

結(jié)點(diǎn)總數(shù)n=no+n1+圖;....⑴

又.??含n個(gè)結(jié)點(diǎn)的二叉樹必有n-l條分支，這些分支是有孩子的結(jié)點(diǎn)提供的

工分支數(shù)b=n-l=2*n2+l*ni

?二結(jié)點(diǎn)總數(shù)n=2*n2+l*ni+l；..⑵

由⑴和⑵,可得no=n2+l,結(jié)論成立。

4?104二叉樹性質(zhì)四

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為［log?〃」+1。

【證明】設(shè)完全二叉樹深度為k

??,前k?l層元素個(gè)數(shù)為2k

又???第k層元素個(gè)數(shù)至少為1,最多為2k.i

???深度為k的完全二叉樹最多2<1個(gè)結(jié)點(diǎn)，最少2kd個(gè)結(jié)點(diǎn)

（另：深度為k的二叉樹最多2卜-1個(gè)結(jié)點(diǎn)，最少k個(gè)結(jié)點(diǎn)）

即（211）十1WnWQll）十即2k-YnW2k-lv2k

/.k-Klog2n<k

Iog2n<k<log2n+1

Vk是整數(shù)

.\k=|_log2/zj+l

4-105二叉樹性質(zhì)五

若對一棵含n個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)按層序進(jìn)行編號，則其中編號為i的結(jié)點(diǎn)有:

①若i=l,則結(jié)點(diǎn)i為二叉樹的根，無雙親，若IviWn,則其雙親為結(jié)點(diǎn)匕/2」；

②若2i>n,則結(jié)點(diǎn)i無左孩子，否則其左孩子為結(jié)點(diǎn)2i；

③若2i+l>n,則結(jié)點(diǎn)i無右孩子，否則其右孩子為結(jié)點(diǎn)2i+l°

4-106二叉樹的順序存儲結(jié)構(gòu)

用一段地址連續(xù)的存儲空間，從下標(biāo)為1的存儲單元開始按層序依次保存完全（滿）二叉樹中的數(shù)據(jù)

元素，以結(jié)點(diǎn)間存儲地址上的聯(lián)系(按層序編號為i的結(jié)點(diǎn)保存在下標(biāo)為i的存儲單元，其雙親若存在則

保存在下標(biāo)為i/2的存儲單元，其左孩子若存在則保存在下標(biāo)為2*i的存儲單元，其右孩子若存在則保存在

下標(biāo)為2巧+1的存儲單元)，體現(xiàn)結(jié)點(diǎn)間雙親與孩子的關(guān)系。

二叉樹順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)包括：(1)便于由一個(gè)結(jié)點(diǎn)找其雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)；(2)存儲密度大。缺點(diǎn)

包括：(1)需預(yù)測二叉樹上可能的最多結(jié)點(diǎn)數(shù)。適用：完全二叉樹、滿二叉樹，若用于保存一般二叉樹，則

最壞情況下，深度為k的二叉樹只含k個(gè)結(jié)點(diǎn)卻需使用長度為2k-l的一維數(shù)組保存。

4-107二叉樹的二叉鏈表存儲結(jié)構(gòu)

每個(gè)結(jié)點(diǎn)含三個(gè)域，即數(shù)據(jù)域、指向左孩子的指針域和指向右孩子的指針域。設(shè)置頭指針，指向根結(jié)

點(diǎn)。含n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。

typedefstructBiTreeNode{

TElcmTypcdata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

}BiTreeNode,*BiTree;

4-108二叉樹的三叉鏈表存儲結(jié)構(gòu)

在二叉鏈表的基礎(chǔ)上，每個(gè)結(jié)點(diǎn)再增加一個(gè)指向雙親的指針域。

typcdcfstructBiTreeNode{

TElemTypedata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

structBiTreeNode"parent;

)BiTreeNode,*BiTree;

4-109二叉樹的中序遍歷

【方法】(D中序遍歷左子樹；⑵訪問根結(jié)點(diǎn)；(初中序遍歷右子樹。

【遞歸算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!IiiOrderTraverse(T->luhild,visit))return0;〃中序遍歷左子樹

if(!visit(T->data))return0;〃訪問根結(jié)點(diǎn)

if(!lnOrdcrTraversc(T->rchild,visit))return0;〃中序遍歷右子樹

}

return1;

)//InOrderTraverse

【非遞歸算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P)(

Push(S,p);

p=p->lchild;

else{

Pop(S,p);

if(!visit(p->data))return0;

p=p->rchild;

)//else

(//while

return1;

}//InOrderTraverse

輔助棧的最大容量等于二叉樹的深度，最壞情況下為n。

二叉樹遍歷算法中的基本操作是訪問結(jié)點(diǎn)，無論按何種次序，對含n個(gè)結(jié)點(diǎn)的二叉樹，時(shí)間復(fù)雜度均

為O(n)。

4410二叉樹的先序遍歷

【方法】⑴訪問根結(jié)點(diǎn)；⑵先序遍歷左子樹；⑶先序遍歷右子樹。

【遞歸算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!visit(T->data))return0;〃訪問根結(jié)點(diǎn)

if(!PreOrderTraverse(T->lchild,visit))return0;〃先序遍歷左子樹

if(!PreOrderTraverse(T->rchild,visit))return0;〃先序遍歷右子樹

)

return1;

}//PreOrderTraverse

【非遞歸算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!SlackEniply(S)){

if(!visit(p->data))return0;

if(p->rchild)Push(S,p->rchild);

p=p->lchild;

)

else{

Pop(S,p);

}//else

}//while

return1;

(//PreOrderTraverse

4-111二叉樹的后序遍歷

【方法】⑴后序遍歷左了樹；⑵后序遍歷右了樹；⑶訪問根結(jié)點(diǎn)。

【遞歸算法】

intPostOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍歷成功則返回1,否則返回0

if(!T){

if(!PostOrderTraverse(T->lchild,visit))return0;〃后序遍歷左子樹

if(!PoslOrderTraverse(T->rchild,visit))return0;〃后序遍歷右子樹

if(!visit(T->data))return0;〃訪問根結(jié)點(diǎn)

)

return1;

}//PostOrderTraverse

【非遞歸算法】

typedefstruct{

BiTreeNodenode;

intflag;//0表示結(jié)點(diǎn)node的右子樹尚未被訪問，I表示結(jié)點(diǎn)node的右子樹已被訪問

(SElemType;

iniPostOrderTraverse(BiTreeT,int(*vi$it)(TElemTypee)){

//若遍歷成功則返回1,否則返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

temp.node=p;

temp.flag=0;

Push(S,temp);

p=p->lchild;

)

else{

Pop(S,temp);

if(temp.flag){〃出棧結(jié)點(diǎn)的左、右子樹均已被訪問

if(!visit(temp.node->data))return0;

)

else{〃出棧結(jié)點(diǎn)的右子樹尚未被訪問

temp.flag=l;

Push(S,temp);//修改標(biāo)志位后重新入棧

p=temp.node->rchild;〃處理右子樹

)

}//if

(//while

(//PostOrderTraverse

4-112二叉樹的層序遍歷

【方法】⑴按結(jié)點(diǎn)所在層次，由低層向高層依次遍歷；⑵同層中按自左向右次序遍歷。

【算法】

intLeveIOrderTraverse(BiTreeT.int(*visit)(TEIemTypee)){

〃若遍歷成功則返回1，否則返回0

if(IT)return1;〃空二叉樹

InitQueue(Q);//初始化輔助隊(duì)列

if(!visit(T->data))return0;〃訪問根結(jié)點(diǎn)

EnQueue(Q,T);〃指向根結(jié)點(diǎn)的指針入隊(duì)

while(!QueueEmpty(Q)){〃若隊(duì)列非空

DeQueue(Q,p);〃隊(duì)頭指針出隊(duì)

if(p->Ichild){〃先訪問p所指結(jié)點(diǎn)的左孩子，再訪問其右孩子

if(!visit(p->lchild->data))return0;

EnQueue(Q,p->lchild);

)//if

if(p->rchild){

if(!visit(p->rchild->data))return0;

EnQucuc(Q,p->rchild);

}//if

(//while

return1;

)//LevelOrderTraverse

4-201線索二叉樹

二叉樹的任何一種遍歷，其實(shí)質(zhì)均為對非線性結(jié)構(gòu)的線性化。若將遍歷序列中所體現(xiàn)的結(jié)點(diǎn)間的線性

關(guān)系保存在二叉樹的存儲結(jié)構(gòu)中，這樣的二叉樹稱線索二叉樹，存儲結(jié)構(gòu)稱線索鏈表。線索鏈表中指向結(jié)

點(diǎn)的前驅(qū)、后繼的指針稱線索。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。

一棵二叉樹在中序線索化后，其中空的鏈域的個(gè)數(shù)是2。一棵左子樹為空的二叉樹在先序線索化后，

其中空的鏈域的個(gè)數(shù)是2；一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是lo一

棵右子樹為空的二叉樹在后序線索化后，其中空的鏈域的個(gè)數(shù)是2；一棵左右子樹均不空的二叉樹在后序

線索化后，其中空的鏈域的個(gè)數(shù)是1。

4-202線索鏈表

【方法一】在二叉鏈表中每個(gè)結(jié)點(diǎn)上增加兩個(gè)指針域，分別用以指向該結(jié)點(diǎn)在遍歷序列中的直接前驅(qū)

和直接后繼。

【方法二】利用二叉鏈表中的空鏈域保存結(jié)點(diǎn)間的線性關(guān)系。規(guī)定：若結(jié)點(diǎn)的Ichild域?yàn)榭眨瑒t在其

中保存指向其直接前驅(qū)的指針；若結(jié)點(diǎn)的「child域?yàn)榭眨瑒t在其中保存指向其宜接后繼的指針；每個(gè)結(jié)點(diǎn)

再設(shè)兩個(gè)標(biāo)志域Itag和rtag,當(dāng)指針域指向孩子時(shí)標(biāo)志域取值為0,否則取值為1。

在線索鏈表中還可添加頭結(jié)點(diǎn)：頭結(jié)點(diǎn)的data域不使用，其Ichiki域指向根，llag域?yàn)?,rchild域指

向遍歷序列中的尾結(jié)點(diǎn)，rtag域?yàn)?。同時(shí)，令遍歷序列中首結(jié)點(diǎn)的Ichild域和尾結(jié)點(diǎn)的rchild域均指向頭

結(jié)點(diǎn)。

typedefenum{Link,Thread}PointerTag,//Link值為0,Thread值為1

typedefstructBiThrNode{

TElemTypedata;

structBiThrNode*lchild;

structBiThrNode*rchild;

PointcrTagItag;

PointerTagrtag;

(BiThrNode,*BiThrTree;

4-203中序線索化

【方法】

對二叉鏈表T進(jìn)行中序線索化，生成二叉中序線索鏈表Thr1。

⑴生成頭結(jié)點(diǎn)，其data域不用，ltag=Link,rtag=Thread；

⑵若二叉樹為空，則頭結(jié)點(diǎn)的Ichild和rchild均指向自己；

⑶若二叉樹非空，則頭結(jié)點(diǎn)的Ichild指向根，rchild需指向遍歷序列中的尾結(jié)點(diǎn)，應(yīng)在遍歷完成后處理；

⑷對二叉鏈表進(jìn)行中序遍歷，對于在遍歷過程中遇到的每個(gè)結(jié)點(diǎn)：

若Ichild域非空

則令I(lǐng)lag=Link

否則令lchild=指向其直接前驅(qū)的指針且令Mg=Thread(在遍歷中設(shè)指針pre指向剛訪問過的結(jié)點(diǎn))

若rchild域非空

則令rtag=Link

否則令rchild=指向其直接后繼的指針且令rtag=Thread(此操作需在訪問到下一結(jié)點(diǎn)時(shí)處理，即訪問當(dāng)

前結(jié)點(diǎn)時(shí)，處理其直接前驅(qū)的rchild、rtag域)。

【遞歸算法】

voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

〃由二叉鏈表T生成二叉中序線索鏈表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成頭結(jié)點(diǎn)

if(!Thrt)exit(-2);

if(!T){〃二叉樹為空樹

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchild=Thrt;

Thrt->rtag=Thread;

)//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃頭結(jié)點(diǎn)的Ichiki指向二叉鏈表根結(jié)點(diǎn)

pre=Thrt;//pre為指向前驅(qū)的指針，在InThreading中需使用，此處用全局變量實(shí)現(xiàn)，也可設(shè)置為參數(shù)

InThreading(T);〃調(diào)用中序線索化函數(shù)處理二叉鏈表T

pre->rchild=Thrt;

pre->rtag=Thread;〃中序遍歷完成，pre指向遍歷序列中的尾結(jié)點(diǎn)，該結(jié)點(diǎn)一定無右子樹

Thrt->rchild=pre;

Thrt->rtag=Thread;〃頭結(jié)點(diǎn)的rchild指向遍歷序列中的尾結(jié)點(diǎn)

}//else

}//InOrderThreading

voidInThreading(BiThrTrccp){

if(P){

InThreading(p->lchild);〃左子樹線索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

InThrcading(p->rchild);〃右子樹線索化

)//if

(InThreading

【非遞歸算法】

voidInOrdcrThrcading(BiThiTrcc&Thrt,BiThrTreeT){

〃由二叉鏈表T生成二叉中序線索鏈表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成頭結(jié)點(diǎn)

if(!Thrt)exit(-2);

if(!T)(〃二叉樹為空樹

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchiId=Thrl;

Thrt->rtag=Thread;

(//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃頭結(jié)點(diǎn)的Ichiki指向二叉鏈表根結(jié)點(diǎn)

pre=Thrt;//pre為指向前驅(qū)的指針

InitSlack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

Push(S,p);

p=p->lchild;

)

else{

Pop(S,p);

if(!p->lchild){p->lchild=pre;p->ltag=Thread;(

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

p=p->rchild;

}//e!se

}//while

pre->rchild=Thrt;

pre->rtag=Thread;〃遍歷序列中的尾結(jié)點(diǎn)的rchild域指向頭結(jié)點(diǎn)

Thrt->rchild=pre;

Thrt->rtag=Thread;〃頭結(jié)點(diǎn)的rchild域指向遍歷序列中的尾結(jié)點(diǎn)

}//IriOrderThreading

4-204中序線索二叉樹的遍歷

【方法】

對中序線索二叉樹進(jìn)行遍歷，可從頭結(jié)點(diǎn)開始，沿前驅(qū)或后繼進(jìn)行遍歷。

若對中序線索二叉樹從首結(jié)點(diǎn)起沿后繼進(jìn)行遍歷，則遍歷序列中首結(jié)點(diǎn)是二叉樹中最左下的結(jié)點(diǎn)。若

結(jié)點(diǎn)無右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其右子樹中最左下的結(jié)點(diǎn)。

若對中序線索二叉樹從尾結(jié)點(diǎn)起沿前驅(qū)進(jìn)行遍歷，則遍歷序列中尾結(jié)點(diǎn)由頭結(jié)點(diǎn)的右指針指向(二叉

樹中最右下的結(jié)點(diǎn))。若結(jié)點(diǎn)無左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其左子樹中最

右下的結(jié)點(diǎn)。

【算法】

StatusIOT_Thr(BiThrTreeT,Status(*visit)(TElemTypee)){

〃對中序線索鏈表T從首結(jié)點(diǎn)起，沿后繼進(jìn)行遍歷，遍歷成功則返回1,否則返回0

p=T->lchiid;〃p指向根結(jié)點(diǎn)

while(p!=T){

〃第一次判定時(shí)若p等于T,則二叉樹為空，以后判定時(shí)若p等于T,則遍歷完成

while（p->ltag==Link）p=p->lchild;

〃找p的最左下孩子，第一次p指向根，所找結(jié)點(diǎn)即遍歷序列首結(jié)點(diǎn)，

//以后p指向剛訪問過的結(jié)點(diǎn)的右孩子，此時(shí)剛訪問過的結(jié)點(diǎn)，其rtag應(yīng)為Link

if（!visit（p->data））return0;

while（p->rtag==Thread&&p->rchild!=T）{

〃若p所指結(jié)點(diǎn)的rchild指向其直接后繼，且該直接后繼不是頭結(jié)點(diǎn)，即p所指結(jié)點(diǎn)不是遍歷序列尾

結(jié)點(diǎn)

p=p->rchild;

if（!visit（p->data））return0;

}//while

}while

}//IOT_Thr

4-205先序線索化及其遍歷

若對先序線索二叉樹從首結(jié)點(diǎn)起沿后繼進(jìn)行遍歷，則遍歷序列中首結(jié)點(diǎn)是二叉樹的根結(jié)點(diǎn)。若結(jié)點(diǎn)無

右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其左孩子（即左子樹的根結(jié)點(diǎn)），若左孩子不

存在，則為其右孩子。

若對先序線索二叉樹從尾結(jié)點(diǎn)起沿前驅(qū)進(jìn)行遍歷，則遍歷序列中尾結(jié)點(diǎn)是二叉樹中最右下的結(jié)點(diǎn)。若

結(jié)點(diǎn)無左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其雙親（當(dāng)該結(jié)點(diǎn)是其雙親的左孩子或

該結(jié)點(diǎn)雖是其雙親的右孩子但其雙親并無左孩子時(shí)）或?yàn)槠潆p親的左子樹中最右下的結(jié)點(diǎn)（當(dāng)該結(jié)點(diǎn)是其

雙親的右孩子且其雙親有左孩子時(shí)），若該結(jié)點(diǎn)無雙親（即根結(jié)點(diǎn)）則無直接前驅(qū)。

4-206后序線索化及其遍歷

若對后序線索二叉樹從首結(jié)點(diǎn)起沿后繼進(jìn)行遍歷，則遍歷序列中首結(jié)點(diǎn)是二叉樹中最左下的結(jié)點(diǎn)。若

結(jié)點(diǎn)無右子樹，則其直接后繼由其右指針指向，否則其直接后繼為其雙親（當(dāng)該結(jié)點(diǎn)是其雙親的右孩子或

該結(jié)點(diǎn)雖是其雙親的左孩子但其雙親并無右孩子時(shí)）或?yàn)槠潆p親的右子樹中第一個(gè)被訪問的結(jié)點(diǎn)（所以仍

需棧的支持）（當(dāng)該結(jié)點(diǎn)是其雙親的左孩子且其雙親有右孩子時(shí)）。

若對后序線索二叉樹從尾結(jié)點(diǎn)起沿前驅(qū)進(jìn)行遍歷，則遍歷序列中尾結(jié)點(diǎn)是二叉樹的根結(jié)點(diǎn),若結(jié)點(diǎn)無

左子樹，則其直接前驅(qū)由其左指針指向，否則其直接前驅(qū)為其右子樹的根，若該結(jié)點(diǎn)無右子樹，則其直接

前驅(qū)為其左子樹的根。

4-301哈夫曼二叉樹（最優(yōu)二叉樹）

哈夫曼（二叉）樹是帶權(quán)路徑長度最短的（二叉）樹，又稱最優(yōu)（二叉）樹’樹的帶權(quán)路徑長度指樹

中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和；結(jié)點(diǎn)的帶權(quán)路徑長度指從根到結(jié)點(diǎn)的路徑長度與結(jié)點(diǎn)上權(quán)的乘積；

結(jié)點(diǎn)間的路徑長度指從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)的路徑上的分支數(shù)。

完全二叉樹是路徑長度最短的二叉樹。樹的路徑長度指根到每個(gè)結(jié)點(diǎn)的路徑長度之和。

4?302哈夫曼二叉樹（最優(yōu)二叉樹）

由給定的n個(gè)權(quán)值構(gòu)造哈夫曼二叉樹的方法（哈夫曼算法）如下：

⑴根據(jù)給定的n個(gè)權(quán)值{wi,W2,…,wj構(gòu)成n棵二叉樹的集合F={TI,T2,…,T”,其中每棵二叉樹只含一

個(gè)帶權(quán)的根結(jié)點(diǎn)，其左右子樹均空；

⑵在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且置新的二叉樹的根

結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和；

⑶在F中刪除這兩棵二叉樹，同時(shí)將新得到的二叉樹加入F；

⑷重復(fù)⑵和（3）,直到F只含一棵二叉樹，此即哈夫曼二叉樹。

4-303哈夫曼編碼

【方法】⑴以字符出現(xiàn)頻率為權(quán)值，構(gòu)造哈夫曼二叉樹；⑵約定以左分支表示0,右分支表示1,把從根

到葉子的路徑上所有分支構(gòu)成的01串作為葉子的二進(jìn)制編碼，即為哈夫曼編碼。

4-401樹的雙親表示法存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元，按一定次序保存樹中數(shù)據(jù)元素，每個(gè)結(jié)點(diǎn)中設(shè)置指針，指示具雙親位置。

此法易查找結(jié)點(diǎn)的雙親，而找結(jié)點(diǎn)的孩子則需掃描整張表。

#defineMAXSIZE1000

typedefstructPTNode{

ElemTypedata;

intparent;

JPTNode;

typedefstruct{

PTNodenodes[MAXSIZE];

intn;

（ParentTree;

4-402樹的孩子表示法存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元，按一定次序保存樹中數(shù)據(jù)元索，每個(gè)結(jié)點(diǎn)中設(shè)置指針，指向其孩子鏈表。

此法易查找結(jié)點(diǎn)的孩子，而查找結(jié)點(diǎn)的雙親則需掃描整張表。

#defineMAXSIZE1000

typedefstructChildNode{

intchild;

structChildNode*next;

JChildNodc,*ChildPtr;〃孩子鏈表中的結(jié)點(diǎn)

typedefstruct{

ElemTypedata;

ChildPtrfirstchild;

}CTNode;

typedefstruct{

CTNodenodes[MAXSIZEl;

intii;〃樹中結(jié)點(diǎn)數(shù)

intr;〃根的位置

JChildTrcc;

4-403樹的雙親一孩子表示法存儲結(jié)構(gòu)

雙親表示法與孩子表示法的組合。結(jié)點(diǎn)間邏輯關(guān)系的存儲冗余。

4-404樹的孩子.兄弟表示法存儲結(jié)構(gòu)

用二叉鏈表保存與樹對應(yīng)的二叉樹。

4-405樹與二叉樹的相互轉(zhuǎn)化

樹與二叉樹可相互轉(zhuǎn)化。由樹轉(zhuǎn)化而來的二叉樹中，結(jié)點(diǎn)的左指針指向它在樹中的第一個(gè)孩子結(jié)點(diǎn)，

右指針指向它在樹中的右兄弟結(jié)點(diǎn)。

由一棵非空樹轉(zhuǎn)化而得的二叉樹，其根結(jié)點(diǎn)無右子樹（若樹中只有一個(gè)結(jié)點(diǎn)，則轉(zhuǎn)化而得的二叉樹也

沒有左了樹）。

若二叉樹的根結(jié)點(diǎn)無右子樹，則可將它轉(zhuǎn)化為樹。

對樹的操作也可轉(zhuǎn)化為對相應(yīng)二叉樹的操作。樹的先序遍歷相當(dāng)于對相應(yīng)二叉樹的先序遍歷。樹的后

序遍歷相當(dāng)于對相應(yīng)二叉樹的中序遍歷。

4-406樹的遍歷

⑴先序遍歷：①訪問樹的根結(jié)點(diǎn)；②從左至右，依次先序遍歷根的每棵子樹。

⑵后序遍歷：①從左至右，依次后序遍歷根的每棵子樹；②訪問樹的根結(jié)點(diǎn)。

4-407森林與二叉樹的相互轉(zhuǎn)化

將森林中各棵樹的樹根看作互為兄弟。

若森林中有多棵樹，則轉(zhuǎn)化而得的二叉樹，其根結(jié)點(diǎn)有右子樹。若二叉樹的根結(jié)點(diǎn)有右子樹，則轉(zhuǎn)化

而得的必為森林。

森林的先序遍歷相當(dāng)于對相應(yīng)二叉樹的先序遍歷。森林的中（后）序遍歷相當(dāng)于對相應(yīng)二叉樹的中序

遍歷。

4-408森林的遍歷

⑴森林的先序遍歷

若森林非空，則：

①訪問森林中第一棵樹的根結(jié)點(diǎn)；

②先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；

③先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

⑵森林的中（后）序遍歷

若森林非空，則：

①中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；

②訪問第一棵樹的根結(jié)點(diǎn)；

③中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

第五課圖

覆蓋的知識點(diǎn)最小集：

I.圖的基本概念

2.圖的存儲及基本操作

(1)鄰接矩陣法

⑵鄰接表法

3.圖的遍歷

(1)深度優(yōu)先搜索

⑵廣度優(yōu)先搜索

4.圖的基本應(yīng)用

(1)最小(代價(jià))生成樹

(2)最短路徑

(3)拓?fù)渑判?/p>

(4)關(guān)鍵路徑

知識點(diǎn)細(xì)化：

5-001圖

圖G=(V,{VR}),其中V為頂點(diǎn)的非空有限集合，VR為頂點(diǎn)間關(guān)系的集合，即圖中邊的集合(注意：

離散數(shù)學(xué)中將樹定義為一個(gè)連通且無回路的無向圖)。

圖中的邊若為頂點(diǎn)的無序序偶，則稱無向邊(簡稱邊)，若為頂點(diǎn)的有序序偶，則稱有向邊(簡稱弧)。

若圖中的邊均為無向邊，則稱無向圖；含n個(gè)頂點(diǎn)n(n-l)/2條邊的無向圖稱無向完全圖;若圖中的邊均為

有向邊，則稱有向圖；含n個(gè)結(jié)點(diǎn)n(n-l)條弧的有向圖稱有向完全圖。網(wǎng)是邊/弧上帶權(quán)的圖。權(quán)是與圖

的邊/弧相關(guān)的數(shù)。

5-002頂點(diǎn)的度

無向圖中依附于頂點(diǎn)v的邊的數(shù)目，稱頂點(diǎn)v的度，記TD(v).

有向圖中以頂點(diǎn)v為弧頭頂點(diǎn)的弧的數(shù)目稱頂點(diǎn)v的入度，記ID(v)；以頂點(diǎn)v為弧尾頂點(diǎn)的弧的數(shù)

目稱頂點(diǎn)v的出度，記OD(v)；入度與出度之和稱頂點(diǎn)v的度.記TD(v),

若圖G中有n個(gè)頂點(diǎn)，e條邊/弧，必有€之

5-003頂點(diǎn)間路徑

無向圖G=(V,{E})中頂點(diǎn)V和頂點(diǎn)W間的路徑為頂點(diǎn)序列Vo,Vl/-,Vn?其中Vo=V為起點(diǎn)，Vn=W為終點(diǎn)，

voJ:VnWV,ei=(Vj.i,Vj)￡E,i=l,,,no

有向圖G=(V,{A})中從頂點(diǎn)V到頂點(diǎn)W的路徑為頂點(diǎn)序列Vo,Vi,…,Vn，其中Vo=V為起點(diǎn)，Vn=W為終點(diǎn)，

V。,…,Vn^V，ai=<Vj.|,Vj>^A,

路徑上邊/弧的數(shù)目稱路徑長度，，沒有重復(fù)頂點(diǎn)的路徑稱簡單路徑.，起點(diǎn)與終點(diǎn)相同的路徑稱回路,,

除起點(diǎn)和終點(diǎn)相同外，別無重復(fù)頂點(diǎn)的路徑稱簡單回路。

5?004子圖

設(shè)圖G=<V,{VR}>,若有圖G=vV：{VR}>,滿足▽包含于V,VR包含于VR,則稱G為G的子圖。

5?005無向圖的連通性

無向圖中，若兩頂點(diǎn)間存在路徑，則稱兩頂點(diǎn)連通。若圖中任意兩頂點(diǎn)都是連通的，則稱該圖為連通

圖，否則稱非連通圖，

無向圖的極大連通了圖稱其連通分量，連通圖只有?個(gè)連通分量，就是它本身，非連通圖則有多個(gè)連

通分量。

連通圖的極小連通子圖（含原圖中全部頂點(diǎn)）稱其生成樹。若連通圖有n個(gè)頂點(diǎn)，則其生成樹有n個(gè)

頂點(diǎn)，并有且僅有n-1條邊，但該圖的含n個(gè)頂點(diǎn)及n-1條邊的子圖不一定是其生成樹。生成樹上任意兩

頂點(diǎn)間有且僅有一條路徑。

非連通圖的各連通分量的生成樹構(gòu)成該圖的生成森林。

5-006有向圖的連通性

有向圖中，任意一對結(jié)點(diǎn)間，若兩者相互可達(dá)，則稱該圖為強(qiáng)連通圖；若至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)

點(diǎn)是可達(dá)的，則稱該圖為單側(cè)連通圖，若略去弧的方向（即把該圖看作無向圖），該圖為一連通圖，則稱

該圖為弱連通圖，以上三者均不符，則為非連通圖。有向圖若強(qiáng)連通，則必單側(cè)連通；若單側(cè)連通，則必

弱連通；反之不然。

有向圖的極大強(qiáng)連通子圖稱其強(qiáng)連通分量

只有一個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1的有向圖稱有向樹。一個(gè)有向圖的生成森林由若干

棵有向樹組成，該森林含有圖中全部頂點(diǎn)以及足以構(gòu)成若干棵不相交的有向樹的弧。

含n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少含n條弧，至多含n（n?l）條弧。

5-101圖的鄰接矩陣存儲結(jié)構(gòu)

設(shè)圖G含n個(gè)頂點(diǎn)，則G的鄰接矩陣是記錄這些頂點(diǎn)間邏輯關(guān)系的n階方陣，不妨記為A=（aRxn，

1<v.,v.>eVRw<V,,V>eVR

則對（有向/無向）圖有：八對（有向/無向）網(wǎng)有：Ujj7

J

[（）<vPvy>^VRoo<>^VR

其中W為權(quán)值。

無向圖（網(wǎng)）的鄰接矩陣是對稱陣；有向圖（網(wǎng)）的鄰接矩陣可以對稱，也可以不對稱（后者更為常見）。

鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度為0（1?）。

在鄰接矩陣存儲結(jié)構(gòu)中，添加新頂點(diǎn)V：若頂點(diǎn)數(shù)未滿，貝1J（1）將頂點(diǎn)V保存在vexs[vexnum]中；（2）

必要時(shí)將adjmaxlrix[vexnum][O..vexnum]及adjmaxtrix[O..vexnum][vexnum]清為0或8；（3）vexnum力口1。

在鄰接矩陣存儲結(jié)構(gòu)中，設(shè)頂點(diǎn)V保存在vexs國中，刪除頂點(diǎn)V（注意：刪除頂點(diǎn)時(shí)，依附于該頂點(diǎn)

的邊/弧也一并刪除）：（1）求依附于該頂點(diǎn)的邊數(shù)，依此修改arcnum的值；（2）若V不是頂點(diǎn)向量中最后一

個(gè)結(jié)點(diǎn)，即i!=vexnum-l,貝令vexs[i]=vexs[vexnum-l],并令

adjmaxtrix[i][O..vexnum]=adjmaxtrix[vexnum][O..vexnum],令

adjmaxtrix[O..vexnuml[i]=adjmaxtrix[O..vexnum][vexnumb令adjmaxtrix[i][i]=OB￡°°；（3）vexnum減1。

在鄰接矩陣存儲結(jié)構(gòu)中，設(shè)頂點(diǎn)V保存在vexs國中，頂點(diǎn)W保存在vexslj]中，添加邊（V,W）/弧

vV,W>（注意：添加邊/弧時(shí)，要求相關(guān)頂點(diǎn)已存儲）：（1）對于無向圖，則令adjmaxtrix[il[jl=adjmaxtrix[jl[il=l,

并使arcnuni加1；（2）對丁有向圖，令adjiiiaxtrix[i]（j]=l,并使arcnuni加1；（3）對丁網(wǎng),則令相應(yīng)位置的值

為輸入的權(quán)值，并使arcnum加1。

在鄰接矩陣存儲結(jié)構(gòu)中，設(shè)頂點(diǎn)V保存在vexs[i]中，頂點(diǎn)W保存在vexsfj]中，刪除邊（V,W）/弧

<V,W>（注意:刪除邊/弧時(shí)，不刪除相關(guān)頂點(diǎn)）:⑴對于無向圖，則令adjmaxtrix[i][j]=adjmaxtrix皿"=0,

并使arcnum減1；（2）對于有向圖,令adjmaxtrix[i][j]=O,并使arcnum減1；（3）對于網(wǎng)，則令相應(yīng)位置的值

為8,并使arcnum減1。

在鄰接矩陣存儲結(jié)構(gòu)中，設(shè)頂點(diǎn)V保存在vexs[i]中，頂點(diǎn)W保存在vexs[j]中，判斷邊（V,W）/弧

<V,W>是否存在：（1）對于無向圖，若adjmaxtrix[i][j]=l或adjmaxtrix[j][i]=l,則邊（V,W）存在，時(shí)間

復(fù)雜度0（1）;（2）對于有向圖，若adjmaxtrix[i皿=1,則?。╒,W）存在，時(shí)間復(fù)雜度0（1）