考研數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)121130

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試卷類(lèi)型及比例試卷類(lèi)型及比例數(shù)據(jù)結(jié)構(gòu)（40分）：選擇題：10分，簡(jiǎn)答題：10分，算法題：20分。內(nèi)容：內(nèi)容：1、線性表基本概念，順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、相應(yīng)操作。2、棧和隊(duì)列的特點(diǎn)，棧的應(yīng)用、遞歸算法的設(shè)計(jì)。3、樹(shù)的基本概念，二叉樹(shù)的性質(zhì)、存儲(chǔ)結(jié)構(gòu)，樹(shù)與森林，樹(shù)的遍歷及應(yīng)用。4、圖的基本概念，圖的存貯結(jié)構(gòu)，圖的遍歷和拓?fù)渑判颉?5、查找的基本概念、查找性能分析、順序查找、折半查找和二叉排序樹(shù)查找。6、直接插入排序、希爾排序、快速排序、簡(jiǎn)單選擇排序和歸并排序。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容：數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容： 研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合。研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和

2、運(yùn)算集合。 邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)的二種類(lèi)型存儲(chǔ)結(jié)構(gòu)的二種類(lèi)型: 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)通過(guò)在存儲(chǔ)器中的相對(duì)位置，通過(guò)在存儲(chǔ)器中的相對(duì)位置， 表示數(shù)據(jù)的邏輯結(jié)構(gòu)。表示數(shù)據(jù)的邏輯結(jié)構(gòu)。 非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） -由指針表示數(shù)據(jù)間的邏輯關(guān)系。由指針表示數(shù)據(jù)間的邏輯關(guān)系。常用的數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu) (1) 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。線性表、棧、隊(duì)、字符串、數(shù)組的線性關(guān)系。線性表、棧、隊(duì)、字符串、數(shù)組 (2

3、) 樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系。的層次關(guān)系。-非線性結(jié)構(gòu)非線性結(jié)構(gòu) (3) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。在著多對(duì)多的任意關(guān)系。- 非線性結(jié)構(gòu)非線性結(jié)構(gòu)一一 線性表線性表 線性表是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。 棧、隊(duì)列、串是特殊的線性表，數(shù)組和廣棧、隊(duì)列、串是特殊的線性表，數(shù)組和廣義表是線性表的擴(kuò)展義表是線性表的擴(kuò)展-線性結(jié)構(gòu)線性結(jié)構(gòu) 線性表的概念線性表的概念設(shè)設(shè) A=（a1, a2, . , ai -1, ai , a

4、i+1, , an ）是一線性表，）是一線性表，1） 同一線性表中的元素必須是同一類(lèi)型的；同一線性表中的元素必須是同一類(lèi)型的；2） 在表中在表中 ai-1 領(lǐng)先于領(lǐng)先于ai ，ai 領(lǐng)先于領(lǐng)先于ai+1 ，稱，稱ai-1 是是ai 的前件，的前件，ai+1 是是ai 的后件；的后件；3） 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)前件，有且僅有一個(gè)后件；元素都有且僅有一個(gè)前件，有且僅有一個(gè)后件；4） 線性表中元素的個(gè)數(shù)線性表中元素的個(gè)數(shù)n 稱為線性表的長(zhǎng)度，稱為線性表的長(zhǎng)度，n=0 時(shí)稱為空時(shí)稱為空表；表；用一組連續(xù)的內(nèi)存

5、單元依次存放一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n 線性表（線性表（a1,a2, a3, . an ） 的順序存儲(chǔ)結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表線性表的順序存儲(chǔ)和實(shí)現(xiàn)線性表的順序存儲(chǔ)和實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。儲(chǔ)單元存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。 為了表示線性表中元素的先后關(guān)系，每個(gè)為了表示線性表中元素的先后關(guān)系，每個(gè)

6、元素除需要存儲(chǔ)自身的信息外，還要保存直元素除需要存儲(chǔ)自身的信息外，還要保存直接前趨元素或直接后繼元素的存儲(chǔ)位置。接前趨元素或直接后繼元素的存儲(chǔ)位置。a ai i+1a a1a ai-i-1a a2 2a ai ia an n頭指針：頭指針：存放線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址存放線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址;頭結(jié)點(diǎn)：頭結(jié)點(diǎn)：鏈表的第一個(gè)元素結(jié)點(diǎn)前的附加結(jié)點(diǎn)；鏈表的第一個(gè)元素結(jié)點(diǎn)前的附加結(jié)點(diǎn)；帶頭結(jié)點(diǎn)的線性鏈表帶頭結(jié)點(diǎn)的線性鏈表：第一個(gè)元素結(jié)點(diǎn)前增加一個(gè)附加：第一個(gè)元素結(jié)點(diǎn)前增加一個(gè)附加結(jié)點(diǎn)的線性鏈表稱為結(jié)點(diǎn)的線性鏈表稱為 帶頭結(jié)點(diǎn)的線性鏈表；帶頭結(jié)點(diǎn)的線性鏈表； headhead是頭指針是頭指

7、針ai-1aia2a1ai+1nan 頭結(jié)點(diǎn)頭結(jié)點(diǎn) 空指針空指針headhead線性鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指針域故也稱為單鏈表單鏈表例1、設(shè)一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類(lèi)型的key域,試設(shè)計(jì)算法,將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序。（不允許使用數(shù)組做輔助存儲(chǔ)）例2、將單鏈表L1拆成二個(gè)鏈表，其中以L1為頭的鏈表保持原來(lái)向后的鏈接，另一個(gè)鏈表的頭為L(zhǎng)2，其鏈接方向與L1相反，L1包含原鏈表的奇數(shù)序號(hào)的節(jié)點(diǎn)，L2包含原鏈表的偶數(shù)序號(hào)的節(jié)點(diǎn)。例3、線性表合并：二個(gè)有序線性表LA、LB合并為一個(gè)有序線性表,合并后不另設(shè)新表存儲(chǔ)。線性表的順序存儲(chǔ)和實(shí)現(xiàn) 順序表是線性

8、表最簡(jiǎn)單的一種存儲(chǔ)結(jié)構(gòu) 小結(jié)順序表的特點(diǎn)：1 通過(guò)元素的存儲(chǔ)順序反映 線性表中 數(shù)據(jù)元素之間的邏輯關(guān)系；2 可隨機(jī)存取順序表的元素；3 順序表的插入、刪除操作要通過(guò)移動(dòng)元素實(shí)現(xiàn)；線性鏈表小結(jié)線性鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性鏈表的特點(diǎn) 1 通過(guò)保存直接后繼元素的存儲(chǔ)位置來(lái)表示 數(shù)據(jù)元素之間的邏輯關(guān)系； 2 插入、刪除操作通過(guò)修改結(jié)點(diǎn)的指針實(shí)現(xiàn)； 3 不能隨機(jī)存取元素；二二 棧與隊(duì)列棧與隊(duì)列棧是限定僅能在表尾一端進(jìn)行插入、刪除操棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表作的線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入刪除棧的概念棧的概念棧棧棧的

9、示意圖棧的示意圖出棧出棧進(jìn)棧進(jìn)棧棧的特點(diǎn)棧的特點(diǎn)后進(jìn)先出后進(jìn)先出第一個(gè)進(jìn)棧的元素在棧底，第一個(gè)進(jìn)棧的元素在棧底，最后一個(gè)進(jìn)棧的元素在棧頂，最后一個(gè)進(jìn)棧的元素在棧頂，第一個(gè)出棧的元素為棧頂元素，第一個(gè)出棧的元素為棧頂元素，最后一個(gè)出棧的元素為棧底元素最后一個(gè)出棧的元素為棧底元素棧棧頂頂棧棧底底ana2a1例:一個(gè)棧的輸入序列為a,b,c,d，若在入棧的過(guò)程中允許出棧，則可能得到的出棧序列是什么？一個(gè)棧的輸入序列為1,2,3,4n,? 小小 結(jié)結(jié) 1 棧是限定僅能在表尾一端進(jìn)行插入、棧是限定僅能在表尾一端進(jìn)行插入、 刪除操作的線性表；刪除操作的線性表； 2 棧的元素具有后進(jìn)先出的特點(diǎn)；棧的元素具有

10、后進(jìn)先出的特點(diǎn)； 3 棧頂元素的位置由一個(gè)稱為棧頂指針的棧頂元素的位置由一個(gè)稱為棧頂指針的 變量指示，變量指示， 進(jìn)棧、出棧操作要修改棧頂指針；進(jìn)棧、出棧操作要修改棧頂指針； 棧棧隊(duì)列隊(duì)列隊(duì)列的概念隊(duì)列的概念一一 什么是隊(duì)列什么是隊(duì)列隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除隊(duì)列隊(duì)列 a a1 1 a a2 2 a a3 3 a an n入隊(duì)列入隊(duì)列隊(duì)隊(duì)頭頭隊(duì)隊(duì)尾尾出隊(duì)列出隊(duì)列隊(duì)隊(duì) 列列 的的 示示 意意 圖圖隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)先進(jìn)先出先進(jìn)先出第

11、一個(gè)入隊(duì)的元素在隊(duì)頭，第一個(gè)入隊(duì)的元素在隊(duì)頭，最后一個(gè)入隊(duì)的元素在隊(duì)尾，最后一個(gè)入隊(duì)的元素在隊(duì)尾，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，最后一個(gè)出隊(duì)的元素為隊(duì)尾元素最后一個(gè)出隊(duì)的元素為隊(duì)尾元素循環(huán)隊(duì)列循環(huán)隊(duì)列判分隊(duì)空、隊(duì)滿有兩種方法：判分隊(duì)空、隊(duì)滿有兩種方法：1）另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。）另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。2）少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件：）少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件： rear+1=front;隊(duì)空：隊(duì)空： front=rear隊(duì)列中元素的個(gè)數(shù)隊(duì)列中元素的個(gè)數(shù)（rear front+ MAXQSIZE ）% MAXQSIZEfrontfront54 03

12、 12J6J6J7J7J8J8J4J4J5J5rearrear入隊(duì)時(shí)的操作為入隊(duì)時(shí)的操作為 rear=(rear+1) mod MAXQSIZE 小小 結(jié)結(jié) 1 隊(duì)列是限定僅能在表尾一端進(jìn)行插入，表頭隊(duì)列是限定僅能在表尾一端進(jìn)行插入，表頭一端刪除一端刪除 操作的線性表；操作的線性表； 2 隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn)；隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn)； 3 隊(duì)頭、隊(duì)尾元素的位置分別由稱為隊(duì)頭指針隊(duì)頭、隊(duì)尾元素的位置分別由稱為隊(duì)頭指針和隊(duì)尾指針的變量指示，和隊(duì)尾指針的變量指示， 4 入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要修改入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要修改隊(duì)頭指針；隊(duì)頭指針； 樹(shù)的樹(shù)的 基本術(shù)

13、語(yǔ)基本術(shù)語(yǔ)結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次定義為結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次定義為1；根的孩子為第；根的孩子為第二層，依此類(lèi)推；二層，依此類(lèi)推；樹(shù)的深度：樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的層次的最大值樹(shù)中所有結(jié)點(diǎn)的層次的最大值結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)樹(shù)的度：樹(shù)的度： 樹(shù)中結(jié)點(diǎn)度的最大值。樹(shù)中結(jié)點(diǎn)度的最大值。葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：度為：度為 0 的結(jié)點(diǎn)；的結(jié)點(diǎn)；分枝結(jié)點(diǎn)：度不為分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；J JI IA AC CB BD DH HG GF FE EK KL LM M三、樹(shù)三、樹(shù)與二叉樹(shù)與二叉樹(shù) 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)性質(zhì)1: 在二叉樹(shù)的第在二叉樹(shù)的第i層上至多有層上至

14、多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)。 因二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為因二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，則第，則第k+1層的結(jié)點(diǎn)總數(shù)最多層的結(jié)點(diǎn)總數(shù)最多為第為第k層上結(jié)點(diǎn)最大數(shù)的層上結(jié)點(diǎn)最大數(shù)的2倍，即倍，即22k-1=2(k+1)-1，故結(jié)論成立，故結(jié)論成立。 性質(zhì)性質(zhì)2: 深度為深度為k的二叉樹(shù)至多有的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k1）。 證明證明：深度為深度為k的二叉樹(shù)，其結(jié)點(diǎn)總數(shù)的最大值是二叉樹(shù)中的二叉樹(shù)，其結(jié)點(diǎn)總數(shù)的最大值是二叉樹(shù)中每層結(jié)點(diǎn)的最大值相加每層結(jié)點(diǎn)的最大值相加.深度為深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)至多為的二叉樹(shù)的結(jié)點(diǎn)總數(shù)至多為 ：kikikii111122層上的最大結(jié)點(diǎn)個(gè)數(shù)第

15、故結(jié)論成立故結(jié)論成立。 性質(zhì)性質(zhì)3: 對(duì)任意一棵二叉樹(shù)對(duì)任意一棵二叉樹(shù)T，若葉結(jié)點(diǎn)數(shù)為，若葉結(jié)點(diǎn)數(shù)為n0，而其度為，而其度為2的的結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n2，則，則n0=n2+1。證明：設(shè)證明：設(shè)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為二叉樹(shù)中結(jié)點(diǎn)總數(shù)為n， n1為度為為度為1的結(jié)點(diǎn)總數(shù)的結(jié)點(diǎn)總數(shù)。二叉樹(shù)中所有結(jié)點(diǎn)的度小于等于二叉樹(shù)中所有結(jié)點(diǎn)的度小于等于2，所以有：，所以有：n=n0+n1+n2設(shè)二叉樹(shù)中分支數(shù)目為設(shè)二叉樹(shù)中分支數(shù)目為B， 因除根結(jié)點(diǎn)外，因除根結(jié)點(diǎn)外， 每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有：進(jìn)入它的分支，所以有：n=B+1又因二叉樹(shù)中的分支都是由度為又因二叉樹(shù)中的分支都是由度為1和度為

16、和度為2的結(jié)點(diǎn)發(fā)出，的結(jié)點(diǎn)發(fā)出， 所以分支所以分支數(shù)目為數(shù)目為 B=n1+2n2整理后得整理后得n0=n2+1，故結(jié)論成立，故結(jié)論成立 二叉樹(shù)順序二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)，二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)，二叉鏈表存儲(chǔ)結(jié)構(gòu) 二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域指針域 A A F F E E D D C C B B二叉鏈表圖示二叉鏈表圖示 D D A A B B C C E E F F 先序遍歷（T L L R R） 若二叉樹(shù)非空 （1）訪問(wèn)根結(jié)點(diǎn)； （2）先序遍歷左子樹(shù)； （3）先序遍歷右子樹(shù)； 先序遍歷序列：A, ,B,D,B,D,E

17、E,G,G,C C, ,F F例：先序遍歷右圖所示的二叉樹(shù) （1）訪問(wèn)根結(jié)點(diǎn)A （2）先序遍歷左子樹(shù)：即按 T L L R R 的順序遍歷左子樹(shù) （3）先序遍歷右子樹(shù)：即按 T L L R R 的順序遍歷右子樹(shù) A A F F G G E E D D C C B B中序遍歷（L L T R R）若二叉樹(shù)非空（1）中序遍歷左子樹(shù)（2）訪問(wèn)根結(jié)點(diǎn)（3）中序遍歷右子樹(shù) 中序遍歷序列： D,B,G,D,B,G,E E, ,A, ,C,FC,F例：中序遍歷右圖所示的二叉樹(shù) （1）中序遍歷左子樹(shù)：即按 L L T R R 的順序遍歷左子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn)A （3）中序遍歷右子樹(shù)：即按 L L T R R

18、 的順序遍歷右子樹(shù) A A F F G G E E D D C C B B后序遍歷（L L R R T）若二叉樹(shù)非空（1）后序遍歷左子樹(shù)（2）后序遍歷右子樹(shù)（3）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列： D,G,D,G,E E,B,B,F,CF,C, ,A例：后序遍歷右圖所示的二叉樹(shù) （1）后序遍歷左子樹(shù)：即按 L L R R T 的順序遍歷左子樹(shù) （2）后序遍歷右子樹(shù)：即按 L L R R T 的順序遍歷右子樹(shù) （3）訪問(wèn)根結(jié)點(diǎn)A A A F F G G E E D D C C B B例1 、 求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)。 D A B C E F root例3、將二叉樹(shù)bt中每一個(gè)結(jié)點(diǎn)的左右子樹(shù)互換。例2、試

19、寫(xiě)出一遞歸函數(shù)，判別兩棵樹(shù)是否相等。例4、求二叉樹(shù)的高度。int PostTreeDepth(struct bitnode *root) /求二叉樹(shù)的高度求二叉樹(shù)的高度 int hl, hr, max; if(bt! =NULL) hl=PostTreeDepth(bt-LChild); /求左子樹(shù)的深度 hr=PostTreeDepth(bt-RChild); /求右子樹(shù)的深度 max=hlhr?hl: hr; /得到左、 右子樹(shù)深度較大者 return(max+1); / 返回樹(shù)的深度 else return(0); /如果是空樹(shù)， 則返回0 二叉樹(shù)1 1 二叉樹(shù)：二叉樹(shù)： 或?yàn)榭諛?shù)，或由

20、根及兩顆互不相交或?yàn)榭諛?shù)，或由根及兩顆互不相交的左子樹(shù)、右子樹(shù)構(gòu)成，并且左、右子樹(shù)本身的左子樹(shù)、右子樹(shù)構(gòu)成，并且左、右子樹(shù)本身也是二叉樹(shù)；也是二叉樹(shù)； 2 2 二叉樹(shù)可以用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；二叉樹(shù)可以用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；3遍歷：按某種搜索路徑訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)遍歷：按某種搜索路徑訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。，每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。 4 4二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子左子樹(shù)和樹(shù)和遍歷遍歷右子樹(shù)，常用的三種遍歷算法：右子樹(shù)，常用的三種遍歷算法：先序先序遍歷、中序遍歷、后序遍歷；遍歷、中序遍歷、后序遍歷；樹(shù)根結(jié)點(diǎn) X 的第一個(gè)孩子結(jié)點(diǎn) X 緊

21、鄰的右兄弟二叉樹(shù)根結(jié)點(diǎn) X 的左孩子結(jié)點(diǎn) X 的右孩子IACBDHGFEFIABDHGCE樹(shù)樹(shù)森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程 ABCDEFGHIJ(a) 森林ABCDEFGHIJ(b) 森林中每棵樹(shù)對(duì)應(yīng)的二叉樹(shù)ABEFGHIHCD(c) 森林對(duì)應(yīng)的二叉樹(shù)森林森林哈夫曼樹(shù)及應(yīng)用1 哈夫曼樹(shù)哈夫曼樹(shù)-帶權(quán)帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)路徑長(zhǎng)度最短的二叉樹(shù)(最優(yōu)樹(shù)）。最優(yōu)樹(shù)）。路徑：路徑：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的若干個(gè)分支序列；從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的若干個(gè)分支序列；路徑長(zhǎng)度：路徑長(zhǎng)度：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)路徑上的分支數(shù)目；從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)路徑上的分支數(shù)目；結(jié)點(diǎn)的路徑長(zhǎng)度：結(jié)點(diǎn)的路徑長(zhǎng)度：從根到該

22、結(jié)點(diǎn)的路徑長(zhǎng)度；從根到該結(jié)點(diǎn)的路徑長(zhǎng)度；樹(shù)的路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和；記為樹(shù)中所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和；記為PL.在結(jié)點(diǎn)數(shù)相同的條件下，完全二叉樹(shù)是路徑最短的二叉樹(shù)在結(jié)點(diǎn)數(shù)相同的條件下，完全二叉樹(shù)是路徑最短的二叉樹(shù)7 71 13 32 25 56 64 48 88 81 13 32 25 57 74 46 6非完全二叉樹(shù)非完全二叉樹(shù) PL=10完全二叉樹(shù)完全二叉樹(shù)PL=9（路徑最短的二叉樹(shù)不唯一，不是完全二叉樹(shù)，也可能路徑長(zhǎng)度最短）（路徑最短的二叉樹(shù)不唯一，不是完全二叉樹(shù)，也可能路徑長(zhǎng)度最短）1 哈夫曼樹(shù)哈夫曼樹(shù)的概念（續(xù)）的概念（續(xù)）結(jié)點(diǎn)的權(quán)結(jié)點(diǎn)的權(quán)：根據(jù)應(yīng)用

23、的需要給樹(shù)的結(jié)點(diǎn)賦的權(quán)值；：根據(jù)應(yīng)用的需要給樹(shù)的結(jié)點(diǎn)賦的權(quán)值；結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積；：從根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積；樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度=樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和；樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和；記作記作 ： WPL= wi Li 哈夫曼樹(shù)：設(shè)有哈夫曼樹(shù)：設(shè)有n個(gè)權(quán)值個(gè)權(quán)值(w1 , w2 , , wn )，構(gòu)造有，構(gòu)造有n個(gè)葉結(jié)點(diǎn)的二個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉結(jié)點(diǎn)以叉樹(shù)，每個(gè)葉結(jié)點(diǎn)以 wi 為它的權(quán)值。則帶權(quán)路徑長(zhǎng)度最小的二叉為它的權(quán)值。則帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)為哈夫曼樹(shù)。樹(shù)為哈夫曼樹(shù)。B BD DA A

24、C CA AC C D DB B7 5 2 47 5 2 44 47 75 52 2WPL?WPL?WPL?WPL?哈夫曼樹(shù)哈夫曼樹(shù)? ?哈夫曼樹(shù)哈夫曼樹(shù)? ?構(gòu)造哈夫曼樹(shù)的算法：構(gòu)造哈夫曼樹(shù)的算法：1根據(jù)給定的n個(gè)權(quán)值 ，構(gòu)造n棵帶權(quán)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù) F=T1、T2Tn2在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左、右子二叉樹(shù)，構(gòu)造一顆新的二叉樹(shù)， 且新二叉樹(shù)根的權(quán)值=左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；3從F中刪除這兩棵二叉樹(shù)，并將新二叉樹(shù)加入F；4重復(fù) 2、3，直到F中只含一棵二叉樹(shù)為止；403060155 101530例：構(gòu)造以W=（5，15，40，30，10）為權(quán)的哈夫曼樹(shù)。305 10154

25、04030155 1015403030155 1015哈夫曼樹(shù)中權(quán)值小的離根遠(yuǎn)，權(quán)值大的離根近401003060155 1015301234WPL=5*4+10*4+15*3+30*2+40*1=205 四、四、 圖圖 圖的定義： 圖G由兩個(gè)集合V,E構(gòu)成，記作G= 其中V是頂點(diǎn)的非空有限集合，E是邊的有限集合（邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)希?。G1=G1=V1=vV1=v0 0 ,v ,v1 1,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v)

26、,(v2 2,v,v3 3)(v)(v2 2,v,v4 4)G1G1圖示圖示無(wú)序?qū)?vi,vj)：用連接頂點(diǎn)vi、vj的線段表示，稱為無(wú)向邊；例例 V0V0 V4V4 V3V3 V1V1 V2V2G2 G2 圖示圖示有序?qū)?：用以vi為起點(diǎn)、vj為終點(diǎn)的有向線段表示，稱為有向邊或??；無(wú)向圖：在圖G中，若所有邊是無(wú)向邊，則稱G為無(wú)向圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖； V0V0 V1V1 V2V2 V3V3G2=G2=V2=vV2=v0 0 v v1 1,v,v2 2,v,v3 3 E2=vE2= , v, , , ,圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)-鄰接矩陣鄰接矩陣 若圖若圖G是一

27、個(gè)具有是一個(gè)具有n個(gè)頂點(diǎn)的無(wú)權(quán)圖，個(gè)頂點(diǎn)的無(wú)權(quán)圖，G的鄰接矩陣是的鄰接矩陣是nn矩陣矩陣A： 01, jiA若若或或(vi, vj) E E 反之 鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣： Ai，j=1 若(vi,vi+1)E 或 E0 否則0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0鄰接矩陣表示用鄰接矩陣表示頂點(diǎn)間的關(guān)系 5.2 5.2 圖的存儲(chǔ)

28、結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 若圖若圖G是一個(gè)有是一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的陣是具有如下性質(zhì)的nn矩陣矩陣A： ijwjiA, 若若或或(vi, vj)E 反之反之 例如：一個(gè)有向網(wǎng)例如：一個(gè)有向網(wǎng)N,其鄰接矩陣其鄰接矩陣?圖7.7v1v2v6v5v4v35485579612 5 7 5 7 4 4 8 98 9 5 6 5 6 5 5 2 1 2 1 圖的遍歷：圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問(wèn)圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問(wèn)一次。 為保證每一個(gè)頂點(diǎn)只被訪問(wèn)一次，必須對(duì)

29、頂點(diǎn)進(jìn)行標(biāo)記，當(dāng)頂點(diǎn)vi未被訪問(wèn)，值為0；當(dāng)vi已被訪問(wèn)，則值為1。 圖的遍歷有兩種遍歷方法圖的遍歷有兩種遍歷方法（對(duì)無(wú)向圖，有向圖都適用）對(duì)無(wú)向圖，有向圖都適用） 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1從圖中某頂點(diǎn)v出發(fā)： 1）訪問(wèn)頂點(diǎn)v；2）依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷； （1 1） V0,V1,V3,V7,V4,V2,V5,V6,V0,V1,V3,V7,V4,V2,V5,V6, 由于沒(méi)有規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的這是序列（這

30、是序列（1 1）在遍歷過(guò)程中在遍歷過(guò)程中所經(jīng)過(guò)的路徑所經(jīng)過(guò)的路徑例例 深度優(yōu)先遍歷深度優(yōu)先遍歷求圖G以V0為起點(diǎn)的的深度優(yōu)先遍歷序列： V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4 （2）V0,V1,V4,V7,V3,V2,V5,V6 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1從圖中某個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)從圖中某個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)vivi出發(fā)：出發(fā)：1 1）訪問(wèn)頂點(diǎn)）訪問(wèn)頂點(diǎn)vi vi ；2 2）訪問(wèn)）訪問(wèn) vi vi 的所有未被訪問(wèn)的鄰接點(diǎn)的所有未被訪問(wèn)的鄰接點(diǎn)w w1 1 ,w ,w2 2 , , w wk k ；3 3）

31、依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn)）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn); ; 依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)； 廣度優(yōu)先遍歷廣度優(yōu)先遍歷（類(lèi)似于樹(shù)的按層遍歷）（類(lèi)似于樹(shù)的按層遍歷）V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4這是序列（這是序列（1 1）在遍歷過(guò)程中在遍歷過(guò)程中所經(jīng)過(guò)的路徑所經(jīng)過(guò)的路徑由于沒(méi)有規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，廣度優(yōu)先序列不是唯一的廣度優(yōu)先序列不是唯一的例例求圖求圖G G的以的以V0V0起點(diǎn)的的廣度優(yōu)先序列

32、起點(diǎn)的的廣度優(yōu)先序列 V0,V1,V2,V3,V4,V5,V6,V7V0,V1,V2,V3,V4,V5,V6,V7拓?fù)湫蛄校河邢驁D拓?fù)湫蛄校河邢驁DD的一個(gè)頂點(diǎn)序列稱作一個(gè)拓?fù)湫蛄械囊粋€(gè)頂點(diǎn)序列稱作一個(gè)拓?fù)湫蛄?如果該序列中任兩頂點(diǎn)如果該序列中任兩頂點(diǎn)v 、u ，若在，若在D中中v是是u前趨，則在序列中前趨，則在序列中v也是也是u前趨。前趨。拓?fù)渑判颍和負(fù)渑判颍?將有向圖中頂點(diǎn)排成拓?fù)湫蛄?。將有向圖中頂點(diǎn)排成拓?fù)湫蛄小Ｍ負(fù)渑判虻膽?yīng)用拓?fù)渑判虻膽?yīng)用 安排施工計(jì)劃（如上）安排施工計(jì)劃（如上） 判斷工程流程的是否合理判斷工程流程的是否合理 AOV網(wǎng)（有向圖）網(wǎng)（有向圖）不存在有向回路不存在有向回路當(dāng)且

33、僅當(dāng)能對(duì)當(dāng)且僅當(dāng)能對(duì)AOV網(wǎng)網(wǎng)進(jìn)行拓?fù)渑判蜻M(jìn)行拓?fù)渑判?V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V62 拓?fù)渑判蚍椒ǎ和負(fù)渑判蚍椒ǎ?）在有向圖選一無(wú)前趨的頂點(diǎn)）在有向圖選一無(wú)前趨的頂點(diǎn)v，輸出；，輸出；2）從有向圖中刪除）從有向圖中刪除v及以及以v為尾的孤；為尾的孤；3）重復(fù)）重復(fù)1、2、直接全部輸出全部頂點(diǎn)或有向圖中不存在無(wú)前趨頂點(diǎn)；例：、直接全部輸出全部頂點(diǎn)或有向圖中不存在無(wú)前趨頂點(diǎn)；例：V0,V1,V2,V3,V4,V5,V6 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6 五五 查找查找平均查找長(zhǎng)度平均查找長(zhǎng)度ASL：為確定數(shù)據(jù)元素在列表

34、中的位置，：為確定數(shù)據(jù)元素在列表中的位置， 需需和給和給定值進(jìn)行比較的平均次數(shù)定值進(jìn)行比較的平均次數(shù)，稱為查找算法在查找成功時(shí)的平均，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。對(duì)于長(zhǎng)度為查找長(zhǎng)度。對(duì)于長(zhǎng)度為n的列表，的列表， 查找成功時(shí)的平均查找長(zhǎng)度查找成功時(shí)的平均查找長(zhǎng)度為：為： niiinnCPCPCPCPASL12211Pi為查找第為查找第i個(gè)元素的概率，個(gè)元素的概率，Ci為找到列表中第為找到列表中第i個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過(guò)的關(guān)鍵字比較次數(shù)。元素時(shí)，已經(jīng)進(jìn)行過(guò)的關(guān)鍵字比較次數(shù)。查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平均查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平

35、均查找長(zhǎng)度來(lái)衡量查找算法的性能。查找長(zhǎng)度來(lái)衡量查找算法的性能。 線性表的查找線性表的查找順序查找順序查找-最簡(jiǎn)單的查找方法順序查找的基本思想順序查找的基本思想 從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值相比較，若相等，則查找成功，若結(jié)點(diǎn)關(guān)鍵字和待找的值相比較，若相等，則查找成功，若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于的元素，則查找失整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于的元素，則查找失敗。敗。 順序查找既適用于順序表，也適用于鏈表。若用順序表，順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，

36、但若采用單鏈表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無(wú)則只能從前往后掃描。另外，順序查找的表中元素可以是無(wú)序的。序的。niniiniiininnCnCPASL111) 1(21) 1(11二分二分查找（折半查找）查找（折半查找）1.二分查找的基本思想二分查找的基本思想高效率的查找方法。要求表中元素按關(guān)鍵字有序高效率的查找方法。要求表中元素按關(guān)鍵字有序(升序或降序升序或降序)。假設(shè)表中元素為升序排列。假設(shè)表中元素為升序排列。二分查找的基本思想是：二分查找的基本思想是：首先將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，首先將表中間位置

37、記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，否則利用中間位置記錄將表分成前、后兩個(gè)子表， 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。成功，或直到子表不存在為止，此時(shí)查找不成功。例如，假設(shè)給定有序表中關(guān)鍵字為：例如，假設(shè)給定有序表中關(guān)鍵字為：05,13,19

38、,21,37,56,64,74,80,88,92，查找，查找K=21的情況：的情況： 05 13 19 21 37 56 64 74 80 88 92 low hig (a) 初初始始情情形形 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 low hig mid (b) 經(jīng)過(guò)一次比較后的情形經(jīng)過(guò)一次比較后的情形 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 (c ) 經(jīng)過(guò)二次比較后的情形經(jīng)過(guò)二次比較后的情形 (arra

39、ymid.key=19) low mid hig 圖圖 6-1 查找查找 K=21 的示意圖的示意圖 05 13 19 21 37 56 64 74 80 88 92 (d ) 經(jīng)過(guò)三次比較后的情形經(jīng)過(guò)三次比較后的情形 (arraymid.key=21) mid low hig 圖圖 6-1 查找查找 K=21 的示意圖的示意圖 (查找成功查找成功) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 103.二分查找的性能分析 二分查找的過(guò)程可以用二叉樹(shù)來(lái)描述。把當(dāng)前查找區(qū)間的二分查找的過(guò)程可以用二叉樹(shù)來(lái)描述。把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右子區(qū)

40、間分別作為根的左子中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右子區(qū)間分別作為根的左子樹(shù)和右子樹(shù)，左子區(qū)間和右子區(qū)間再按類(lèi)似的方法，由此樹(shù)和右子樹(shù)，左子區(qū)間和右子區(qū)間再按類(lèi)似的方法，由此得到的二叉樹(shù)稱為二分查找的判定樹(shù)。得到的二叉樹(shù)稱為二分查找的判定樹(shù)。例如，給定的關(guān)鍵字序列例如，給定的關(guān)鍵字序列05,13,19,21,37,56,64,74,80,88,92，的判定樹(shù)。的判定樹(shù)。 0 1 2 3 4 5 6 7 8 9 10 4 0 3 2 7 6 5 8 9 1 0 圖圖6 -3 具具 有有11 個(gè)個(gè) 關(guān)關(guān) 鍵鍵 字字 序序 列列 的的 二二 分分 查查 找找 判判 定定 樹(shù)樹(shù) 1 查找查找21的過(guò)程是從根

41、到結(jié)點(diǎn)的過(guò)程是從根到結(jié)點(diǎn)3的路徑，查找的路徑，查找85,應(yīng)在結(jié)點(diǎn)應(yīng)在結(jié)點(diǎn)9的左的左子樹(shù)上子樹(shù)上,但其左子樹(shù)為空但其左子樹(shù)為空,故失敗。故失敗。所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。因此，折所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。因此，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過(guò)判定樹(shù)的深度。半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過(guò)判定樹(shù)的深度。ASL=(1+2*2+3*4+4*4)/11=3 4 0 3 2 7 6 5 8 9 10 圖圖 6-3 具具有有 11 個(gè)個(gè)關(guān)關(guān)鍵鍵字字序序列列的的二二分分查查找找判判定定樹(shù)樹(shù) 1 樹(shù)表的查找樹(shù)表的查找 二叉排序樹(shù)查找二叉排序樹(shù)查找1什么是二叉排序

42、樹(shù)什么是二叉排序樹(shù)二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是一棵具有如下二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是一棵具有如下特征的非空二叉樹(shù)：特征的非空二叉樹(shù)：(1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；小于根結(jié)點(diǎn)的關(guān)鍵字；(2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字；大于等于根結(jié)點(diǎn)的關(guān)鍵字； (3)左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。二叉排序樹(shù)二叉排序樹(shù) 526148973CAOZHAODINGCHENWANG(a)

43、二叉排序樹(shù)示例1(b) 二叉排序樹(shù)示例2(根據(jù)字符 ASC 碼的大小 ) 4二叉排序二叉排序 樹(shù)上的查找樹(shù)上的查找 （1）二叉排序）二叉排序 樹(shù)的查找思想樹(shù)的查找思想若二叉排樹(shù)為空，則查找若二叉排樹(shù)為空，則查找 失敗，否則，先拿根結(jié)點(diǎn)值與失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子樹(shù)重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹(shù)的葉子樹(shù)重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹(shù)的葉子結(jié)點(diǎn)時(shí)，還沒(méi)有找到待找結(jié)點(diǎn)，則查找不成功。結(jié)點(diǎn)時(shí)

44、，還沒(méi)有找到待找結(jié)點(diǎn)，則查找不成功。（2）二叉排序樹(shù)查找的算法實(shí)現(xiàn)）二叉排序樹(shù)查找的算法實(shí)現(xiàn)NODE * search(int k, NODE *root) /在以root為根的二叉排序樹(shù)中查找關(guān)鍵值為x的結(jié)點(diǎn) p=root; while(p!= =NULL) if (p-key= =k) return(p); /查找成功 else if (p-keyk) p=p-lch ; /進(jìn)入左子樹(shù)查找 else p=p-rch ; /進(jìn)入右子樹(shù)查找 return(NULL); 5二叉排序樹(shù)查找的性能分析二叉排序樹(shù)查找的性能分析 在二叉排序樹(shù)查找中，成功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)的深在二叉排序樹(shù)查找中，成

45、功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)的深度，而具有度，而具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度，最好為個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度，最好為log2n，最壞，最壞為為n。因此，二叉排序樹(shù)查找的最好時(shí)間復(fù)雜度為。因此，二叉排序樹(shù)查找的最好時(shí)間復(fù)雜度為O(log2n)，最壞的時(shí)間復(fù)雜度為最壞的時(shí)間復(fù)雜度為O(n)，一般情形下，其時(shí)間復(fù)雜度大致可，一般情形下，其時(shí)間復(fù)雜度大致可看成看成O(log2n)，比順序查找效率要好，但比二分查找要差。，比順序查找效率要好，但比二分查找要差。 1. 二叉排序樹(shù)的插入和生成二叉排序樹(shù)的插入和生成 已知一個(gè)關(guān)鍵字值為已知一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)的結(jié)點(diǎn)s， 若將其插入到二叉排序若將其插入到

46、二叉排序樹(shù)中，只要保證插入后仍符合二叉排序樹(shù)的定義即可。樹(shù)中，只要保證插入后仍符合二叉排序樹(shù)的定義即可。插入方法：插入方法： 若二叉排序樹(shù)是空樹(shù)，則若二叉排序樹(shù)是空樹(shù)，則key成為二叉排序樹(shù)的成為二叉排序樹(shù)的根；根； 若二叉排序樹(shù)非空，若二叉排序樹(shù)非空， 則將則將key與二叉排序樹(shù)的根進(jìn)行比與二叉排序樹(shù)的根進(jìn)行比較，如果較，如果key的值等于根結(jié)點(diǎn)的值，則停止插入；如果的值等于根結(jié)點(diǎn)的值，則停止插入；如果key的值的值小于根結(jié)點(diǎn)的值，則將小于根結(jié)點(diǎn)的值，則將key插入左子樹(shù)；如果插入左子樹(shù)；如果key的值大于根結(jié)的值大于根結(jié)點(diǎn)的值，則將點(diǎn)的值，則將key插入右子樹(shù)。插入右子樹(shù)。二叉排序樹(shù)的建立

47、過(guò)程二叉排序樹(shù)的建立過(guò)程 902812245345( g ) 插入902812245345( f ) 插入2812245345( e ) 插入12245345( d) 插入532445( c) 插入2445( b) 插入45( a) 空樹(shù)順序輸入:45、24、53、12、28、90輸入順序不同所建立的不同二叉排序樹(shù) 902845125324順序輸入:24、53、12、28、 45、 90排序排序?qū)⑴判虼a寫(xiě)成一個(gè)一維數(shù)組的形式，并且在沒(méi)有聲明的情形下，所有排序都按排序碼的值遞增排列。 排序排序 插入排序（直插排序、二分排序、希爾排序） 交換排序（冒泡排序、快速排序） 選擇排序 （直選排序） 歸并

48、排序（二路歸并排序） 插入排序1直接插入排序基本思想：把基本思想：把n個(gè)待排序的元素看成一個(gè)有序表和一個(gè)無(wú)序表，個(gè)待排序的元素看成一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有n-1個(gè)元素，個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。的適當(dāng)位置，使之成為新的有序表。2.折半插入排序例如，n=6，數(shù)組R的六個(gè)排序碼分別為：17，3

49、，25，14，20，9。它的直接插入排序的執(zhí)行過(guò)程如圖7-1所示。 0 1 2 3 4 5 初始狀態(tài) (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14 20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9 第五次插入 (3 9 14 17 20 25) 圖 7-1 直接插入排序示例 3. 希爾排序希爾排序希爾排序希爾排序(縮小增量排序縮小增量排序):1959年由年由D.L.Shell提出來(lái)的。提出來(lái)的。基本思想：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由基本思想

50、：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由 “增量增量”確定）分別進(jìn)行直接插入排序，待整個(gè)序列中的元素確定）分別進(jìn)行直接插入排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的。情況），效率是很高的。例如，n=8，數(shù)組array 的八個(gè)元素分別為：91，67，35，62，29，72，46，57。下面用圖7-2給出希爾排序算法的執(zhí)行過(guò)程。 91 67 35 62 29 72 46 57 初

51、始狀態(tài)， setp=4 29 57 35 62 46 67 91 72 第二趟結(jié)果，step=1 29 35 46 57 62 67 72 91 第三趟結(jié)果 29 67 35 57 91 72 46 62 第一趟結(jié)果,step=2 圖 7-2 希爾排序算法的執(zhí)行過(guò)程 交換排序交換排序冒泡排序冒泡排序基本思想:對(duì)待排序序列從后向前（從下標(biāo)較大的元素開(kāi)始），對(duì)待排序序列從后向前（從下標(biāo)較大的元素開(kāi)始），依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較小的元素逐漸從后部移向前部，就象水底下的氣泡一樣逐較小的元素逐漸從后部移向前部，就象水底下的

52、氣泡一樣逐漸向上冒。漸向上冒。例如，例如，n=6，數(shù)組，數(shù)組R的六個(gè)排序碼分別為：的六個(gè)排序碼分別為：17，3，25，14，20，9。下面用圖。下面用圖7-3給出冒泡排序算法的執(zhí)行過(guò)程。給出冒泡排序算法的執(zhí)行過(guò)程。 圖 7-3 冒泡排序示例 0 1 2 3 4 5 第一趟排序 3 (17 9 25 14 20) 第二趟排序 3 9 (17 14 25 20) 第三趟排序 3 9 14 (17 20 25) 第四趟排序 3 9 14 17 20 25 初始狀態(tài) （17 3 25 14 20 9) 快速排序快速排序基本思想是：取待排序序列中的某個(gè)元素（一般第一個(gè)元素）基本思想是：取待排序序列中的某個(gè)元