數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容.ppt課件

1、8.1 8.1 根本概念根本概念8.2 8.2 靜態(tài)查找表靜態(tài)查找表8.3 8.3 動態(tài)查找表動態(tài)查找表8.4 8.4 哈希表哈希表教材第教材第8 8、1111和和1212章省略，因章省略，因 課程會涉及。課程會涉及。假設(shè)表中存在特定元素，稱查找勝利，應(yīng)輸出假設(shè)表中存在特定元素，稱查找勝利，應(yīng)輸出該記錄；該記錄；否那么，稱查找不勝利也應(yīng)輸出失敗標(biāo)志或否那么，稱查找不勝利也應(yīng)輸出失敗標(biāo)志或失敗位置失敗位置查找表查找表 查查 找找查找勝利查找勝利查找不勝利查找不勝利靜態(tài)查找靜態(tài)查找動態(tài)查找動態(tài)查找關(guān)鍵字關(guān)鍵字主關(guān)鍵字主關(guān)鍵字次關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合。由同一類型的數(shù)據(jù)元素

2、或記錄構(gòu)成的集合。查詢查詢(Searching)特定元素能否在表中。特定元素能否在表中。只查找，不改動集合內(nèi)的數(shù)據(jù)元素。只查找，不改動集合內(nèi)的數(shù)據(jù)元素。既查找，又改動集合內(nèi)的數(shù)據(jù)元素。既查找，又改動集合內(nèi)的數(shù)據(jù)元素。記錄中某個數(shù)據(jù)項(xiàng)的值，可用來識別一個記錄記錄中某個數(shù)據(jù)項(xiàng)的值，可用來識別一個記錄 ( 預(yù)先確定的記錄的某種標(biāo)志預(yù)先確定的記錄的某種標(biāo)志 ) 可以獨(dú)一標(biāo)識一個記錄的關(guān)鍵字可以獨(dú)一標(biāo)識一個記錄的關(guān)鍵字例如例如“學(xué)號學(xué)號例如例如“女女是一種數(shù)據(jù)構(gòu)造是一種數(shù)據(jù)構(gòu)造識別假設(shè)干記錄的關(guān)鍵識別假設(shè)干記錄的關(guān)鍵字字2對查找表常用的操作有哪些？對查找表常用的操作有哪些？ 查詢某個查詢某個“特定的數(shù)據(jù)

3、元素能否在表中；特定的數(shù)據(jù)元素能否在表中；查詢某個查詢某個“特定的數(shù)據(jù)元素的各種屬性；特定的數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；在查找表中插入一元素；從查找表中刪除一元素。從查找表中刪除一元素。 3) 有哪些查找方法？有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的陳列方式查找方法取決于表中數(shù)據(jù)的陳列方式;1查找的過程是怎樣的？查找的過程是怎樣的？ 給定一個值給定一個值K，在含有，在含有n個記錄的文件中進(jìn)展搜索，個記錄的文件中進(jìn)展搜索，尋覓一個關(guān)鍵字值等于尋覓一個關(guān)鍵字值等于K的記錄，如找到那么輸出的記錄，如找到那么輸出該記錄，否那么輸出查找不勝利的信息。該記錄，否那么輸出查找不勝利的信息。例

4、如查字典例如查字典針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同。針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同。“特定的特定的=關(guān)鍵關(guān)鍵字字明確：查找的過程就是將給定的明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)展比較的過程。所以用比較次數(shù)的平均值來評價算法的優(yōu)項(xiàng)進(jìn)展比較的過程。所以用比較次數(shù)的平均值來評價算法的優(yōu)劣。稱為平均查找長度劣。稱為平均查找長度ASL：average search length。其中：其中：n是文件記錄個數(shù)；是文件記錄個數(shù)；Pi是查找第是查找第i個記錄的查找概率通常取等概率個記錄的查找概率通常取等概率,即即Pi =1/n;Ci是

5、找到第是找到第i個記錄時所閱歷的比較次數(shù)。個記錄時所閱歷的比較次數(shù)。統(tǒng)計意義上的統(tǒng)計意義上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率一樣，那么查找物理意義：假設(shè)每一元素被查找的概率一樣，那么查找每一元素所需的比較次數(shù)之總和再取平均，即為每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，顯然，ASLASL值越小，時間效率越高。值越小，時間效率越高。 針對靜態(tài)查找表的查找算法主要有：針對靜態(tài)查找表的查找算法主要有： 靜態(tài)查找表的籠統(tǒng)數(shù)據(jù)類型參見教材靜態(tài)查找表的籠統(tǒng)數(shù)據(jù)類型參見教材P216。一、順序查找線性查找一、順序查找線性查找二、折半查找二分或?qū)Ψ植檎叶?、折半查找二分或?qū)Ψ植?/p>

6、找三、靜態(tài)樹表的查找三、靜態(tài)樹表的查找四、分塊查找索引順序查找四、分塊查找索引順序查找1順序表的機(jī)內(nèi)存儲構(gòu)造：順序表的機(jī)內(nèi)存儲構(gòu)造：typedef struct ElemType *elem; /表基址，表基址，0號單元留空。表容量為全號單元留空。表容量為全部元素部元素 int length; /表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTable;順序查找：即用逐一比較的方法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的方法順序查找關(guān)鍵字，這顯然是最直接的方法。直接的方法。 對順序構(gòu)造如何線性查找？見下頁之例或教材對順序構(gòu)造如何線性查找？見下頁之例或教材P216；對單鏈表構(gòu)造如

7、何線性查找？函數(shù)雖未給出，但也很容易編寫；對單鏈表構(gòu)造如何線性查找？函數(shù)雖未給出，但也很容易編寫；只需知道頭指針只需知道頭指針head就可以就可以“順藤摸瓜；順藤摸瓜；對非線性樹構(gòu)造如何順序查找對非線性樹構(gòu)造如何順序查找?可借助各種遍歷操作！可借助各種遍歷操作！技巧：把待查關(guān)鍵字技巧：把待查關(guān)鍵字key存入表頭或表尾俗稱存入表頭或表尾俗稱“哨兵，哨兵，這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度。例：例：假設(shè)將待查找的特定值假設(shè)將待查找的特定值keykey存入順序表的首部如存入順序表的首部如0 0號單號單元，那么順序查找的實(shí)現(xiàn)方案為：從后向前逐個比較！元，那么順序查找的實(shí)現(xiàn)方案為：從后向前逐個比

8、較！int Search_Seq( SSTable ST , KeyType key ) /在順序表在順序表ST中，查找關(guān)鍵字與中，查找關(guān)鍵字與key一樣的元素；一樣的元素；假設(shè)勝利，前往其位置信息，否那么前往假設(shè)勝利，前往其位置信息，否那么前往0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過設(shè)立哨兵，可免去查找過程中每一步都要檢測能否查找終了。當(dāng)程中每一步都要檢測能否查找終了。當(dāng)n1000時，查找時間將減少一半。時，查找時間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; -

9、 -i) 或或 for(i=1; i=n; i+) return i; /假設(shè)到達(dá)假設(shè)到達(dá)0號單元才終了循環(huán)，闡明不號單元才終了循環(huán)，闡明不勝利，前往勝利，前往0值值(i=0)。勝利時那么前往找到的那。勝利時那么前往找到的那個元素的位置個元素的位置i。 / Search_Seq前往特殊標(biāo)志，例如前往空記錄或空指針。前例中設(shè)立前往特殊標(biāo)志，例如前往空記錄或空指針。前例中設(shè)立了了“哨兵，就是將關(guān)鍵字送入末地址哨兵，就是將關(guān)鍵字送入末地址ST.elem0.key使之終了使之終了并前往并前往 i=0。討論討論 查找效率怎樣計算？查找效率怎樣計算？用平均查找長度用平均查找長度ASL衡量。衡量。討論討論

10、如何計算如何計算ASL？分析：分析：查找第查找第1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為1；查找第查找第2個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為2；查找第查找第n個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：總計全部比較次數(shù)為：12n = (1+n)n/2未思索查找不勝利的未思索查找不勝利的情況：查找哨兵所需情況：查找哨兵所需的比較次數(shù)為的比較次數(shù)為n+1n+1這是查找勝利的情況這是查找勝利的情況假設(shè)求某一個元素的平均查找次數(shù)，還該當(dāng)除以假設(shè)求某一個元素的平均查找次數(shù)，還該當(dāng)除以n等概等概率，率，即：即： ASL1n/2 ，時間效率為，時間效率為 O(n)思索

11、不勝利的計算思索不勝利的計算優(yōu)點(diǎn)：算法簡單，且對順序構(gòu)造或鏈表構(gòu)造均適用。優(yōu)點(diǎn)：算法簡單，且對順序構(gòu)造或鏈表構(gòu)造均適用。缺陷：缺陷： ASL 太長，時間效率太低。太長，時間效率太低。這是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序例如按升序排好，構(gòu)成有序表，然后再將先給數(shù)據(jù)排序例如按升序排好，構(gòu)成有序表，然后再將key與正中元素相比，假設(shè)與正中元素相比，假設(shè)key小，那么減少至左半部內(nèi)查找；再取小，那么減少至左半部內(nèi)查找；再取其中值比較，每次減少其中值比較，每次減少1/2的范圍，直到查找勝利或失敗為止。的范圍，直到查找勝利或失敗為止。v 對順序表構(gòu)造如何編程實(shí)現(xiàn)折半查找算法

12、？對順序表構(gòu)造如何編程實(shí)現(xiàn)折半查找算法？ v 見下頁之例，或見教材見下頁之例，或見教材P219v 對單鏈表構(gòu)造如何折半查找？對單鏈表構(gòu)造如何折半查找？v 無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針head開場開場v 對非線性對非線性(樹樹)構(gòu)造如何折半查找？構(gòu)造如何折半查找？v 可借助二叉排序樹來查找屬動態(tài)查找表方式?？山柚媾判驑鋪聿檎覍賱討B(tài)查找表方式。 如何改良？如何改良？討論討論 順序查找的特點(diǎn)：順序查找的特點(diǎn)： 運(yùn)算步驟：運(yùn)算步驟：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范

13、圍是，待查范圍是 1,11 1,11；(2) (2) 假設(shè)假設(shè) ST.elemmid.key key ST.elemmid.key key ST.elemmid.key key，闡明，闡明keykeylow ,mid-low ,mid-11， 那么令：那么令：high =mid1;high =mid1;重算重算 mid mid ；(4)(4)假設(shè)假設(shè) ST.elem mid .key = key ST.elem mid .key = key，闡明查找勝利，元素，闡明查找勝利，元素序號序號=mid;=mid;終了條件：終了條件： 1 1查找勝利查找勝利 ： ST.elemmid.key = ke

14、y ST.elemmid.key = key 2 2查找不勝利查找不勝利 ： highlow highlow 意即區(qū)間長意即區(qū)間長度小于度小于0 0解：解： 先設(shè)定先設(shè)定3個輔助標(biāo)志個輔助標(biāo)志: low,high,mid，LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 知如下知如下11個元素的有序表：個元素的有序表：05 13 19 21 37 56 64 75 80 88 92, 請查找關(guān)鍵字為請查找關(guān)鍵字為21 和和85的數(shù)據(jù)元素。的

15、數(shù)據(jù)元素。顯然有：顯然有：mid= mid= (low+high)/2(low+high)/2 mjjj112典型標(biāo)志是：當(dāng)查找范圍的上界典型標(biāo)志是：當(dāng)查找范圍的上界下界時停頓查找。下界時停頓查找。討論討論 二分查找的效率二分查找的效率ASLASL1次比較就查找勝利的元素有次比較就查找勝利的元素有1個個20，即中間值；，即中間值；2次比較就查找勝利的元素有次比較就查找勝利的元素有2個個21，即，即1/4處或處或3/4處；處；3次比較就查找勝利的元素有次比較就查找勝利的元素有4個個22，即，即1/8處或處或3/8處處 4次比較就查找勝利的元素有次比較就查找勝利的元素有8個個23，即，即1/16處

16、或處或3/16處處 那么第那么第m次比較時查找勝利的元素會有次比較時查找勝利的元素會有2m-1個；個；為方便起見，假設(shè)表中全部為方便起見，假設(shè)表中全部n個元素個元素 2m-1個，此時就不討論第個，此時就不討論第m次比較后還有剩余元素的情況了。次比較后還有剩余元素的情況了。全部比較總次數(shù)為全部比較總次數(shù)為120221322423m2m1 推推導(dǎo)導(dǎo)過過程程詳細(xì)推導(dǎo)過程見教材詳細(xì)推導(dǎo)過程見教材P221的附錄的附錄課堂練習(xí)多項(xiàng)選擇：課堂練習(xí)多項(xiàng)選擇：采用鏈?zhǔn)酱尜A構(gòu)造采用鏈?zhǔn)酱尜A構(gòu)造 記錄的長度記錄的長度128 采用順序存貯構(gòu)造采用順序存貯構(gòu)造 記錄按關(guān)鍵字遞增有序記錄按關(guān)鍵字遞增有序nnnnjnASL

17、mjj2211log1) 1(log121運(yùn)用折半查找算法時，要求被查文件：運(yùn)用折半查找算法時，要求被查文件：思索：假設(shè)在有序線性表思索：假設(shè)在有序線性表a20上進(jìn)展折半查上進(jìn)展折半查找，那么平均查找長度為找，那么平均查找長度為 。查找過程可用二叉樹描畫：每個記錄用一個結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為查找過程可用二叉樹描畫：每個記錄用一個結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個描畫查找過程的二叉樹稱為斷定樹。該記錄在表中位置，這個描畫查找過程的二叉樹稱為斷定樹。n個個元素的表的折半查找的斷定樹是獨(dú)一的，即：斷定樹由表中元素個元素的表的折半查找的斷定樹是獨(dú)一的，即：斷定樹由表中元素個數(shù)決議。數(shù)決議。 找到

18、有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)到與該記錄找到有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的途徑。相應(yīng)的結(jié)點(diǎn)的途徑。 比較的關(guān)鍵字個數(shù)：為該結(jié)點(diǎn)在斷定樹上的層次數(shù)。比較的關(guān)鍵字個數(shù)：為該結(jié)點(diǎn)在斷定樹上的層次數(shù)。 查找勝利時比較的關(guān)鍵字個數(shù)最多不超越樹的深度查找勝利時比較的關(guān)鍵字個數(shù)最多不超越樹的深度 d : d = log2 n + 1 假設(shè)一切結(jié)點(diǎn)的空指針域設(shè)置為一個指向一個方形結(jié)點(diǎn)的指針，假設(shè)一切結(jié)點(diǎn)的空指針域設(shè)置為一個指向一個方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為斷定樹的外部結(jié)點(diǎn)；對應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。稱方形結(jié)點(diǎn)為斷定樹的外部結(jié)點(diǎn)；對應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。

19、 查找不勝利的過程查找不勝利的過程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途徑。就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途徑。做習(xí)題新建做習(xí)題新建 Microsoft Word 文檔文檔.doc討論討論2：當(dāng)有序表中各記錄的查找概率不相等時，該如何查？：當(dāng)有序表中各記錄的查找概率不相等時，該如何查？首先要明確，此時用折半查找法未必最優(yōu)！參見教材首先要明確，此時用折半查找法未必最優(yōu)！參見教材P222例例改良：假設(shè)將各記錄概率看作是二叉樹之權(quán)值，那么轉(zhuǎn)為研改良：假設(shè)將各記錄概率看作是二叉樹之權(quán)值，那么轉(zhuǎn)為研討帶權(quán)途徑長度最小的二叉樹類似最優(yōu)二叉樹。討帶權(quán)途徑長度最小的二叉樹類似最優(yōu)二叉樹。討論討論1：對有序表還

20、有其他查找算法嗎？：對有序表還有其他查找算法嗎？靜態(tài)最優(yōu)查找樹算法靜態(tài)最優(yōu)查找樹算法時間代價高；時間代價高；適用算法：近似最優(yōu)查找樹次優(yōu)查找樹適用算法：近似最優(yōu)查找樹次優(yōu)查找樹 參見教材參見教材P222225有，如斐波那契查找和插值查找等參見教材有，如斐波那契查找和插值查找等參見教材P221222這是一種順序查找的另一種改良方法。這是一種順序查找的另一種改良方法。先讓數(shù)據(jù)分塊有序，即分成假設(shè)干子表，要求每個子表中的先讓數(shù)據(jù)分塊有序，即分成假設(shè)干子表，要求每個子表中的數(shù)值用關(guān)鍵字更準(zhǔn)確都比后一塊中數(shù)值小但子表內(nèi)部未數(shù)值用關(guān)鍵字更準(zhǔn)確都比后一塊中數(shù)值小但子表內(nèi)部未必有序。必有序。然后將各子表中的最

21、大關(guān)鍵字構(gòu)成一個索引表，表中還要包然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址即頭指針。含每個子表的起始地址即頭指針。索引表索引表最大關(guān)鍵字起始地址第第1 1塊塊第第2 2塊塊第第3 3塊塊224886例：例：特點(diǎn)：塊間有特點(diǎn)：塊間有序，塊內(nèi)無序序，塊內(nèi)無序 對索引表運(yùn)用折半查找法由于索引表是有序表；對索引表運(yùn)用折半查找法由于索引表是有序表； 確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法由于各子表內(nèi)部是無序表；查找法由于各子表內(nèi)部是無序表；查找效率：查找效率：ASL=Lb+LwASL=Lb+Lw對索引表查找的對索

22、引表查找的ASL對塊內(nèi)查找的對塊內(nèi)查找的ASL)21(log2) 1(log22nASLnssnASLbsbsS為每塊內(nèi)部的記錄個數(shù)，為每塊內(nèi)部的記錄個數(shù)，n/s即塊的數(shù)目即塊的數(shù)目例如當(dāng)例如當(dāng)n=9n=9，s=3s=3時，時，ASLbs=3.5,ASLbs=3.5,而折半法為而折半法為3.1,3.1,順序法為順序法為5 5特點(diǎn)：特點(diǎn)：一、二叉排序樹的定義一、二叉排序樹的定義二、二叉排序樹的插入與刪除二、二叉排序樹的插入與刪除三、二叉排序樹的查找分析三、二叉排序樹的查找分析四、平衡二叉樹四、平衡二叉樹表構(gòu)造在查找過程中動態(tài)生成。表構(gòu)造在查找過程中動態(tài)生成。要求：要求： 對于給定值對于給定值ke

23、y,key,假設(shè)表中存在其關(guān)鍵字等于假設(shè)表中存在其關(guān)鍵字等于keykey的記錄，那么查找勝利的記錄，那么查找勝利前往；前往；否那么插入關(guān)鍵字等于否那么插入關(guān)鍵字等于key key 的記錄。的記錄。典型的動態(tài)表典型的動態(tài)表二叉排序樹二叉排序樹ab練：以下練：以下2種圖形中，哪個不是二叉排序樹種圖形中，哪個不是二叉排序樹 ？-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： 1 1左子樹的一切結(jié)點(diǎn)均小于根的值；左子樹的一切結(jié)點(diǎn)均小于根的值； 2 2右子樹的一切結(jié)點(diǎn)均大于根的值；右子樹的一切結(jié)點(diǎn)均大于根的值； 3 3它的左右子樹也分別為二叉排序樹。它的左右

24、子樹也分別為二叉排序樹。將數(shù)據(jù)元素構(gòu)呵斥二叉排序樹的優(yōu)點(diǎn)：將數(shù)據(jù)元素構(gòu)呵斥二叉排序樹的優(yōu)點(diǎn)： 查找過程與順序構(gòu)造有序表中的折半查找類似，查找效率高；查找過程與順序構(gòu)造有序表中的折半查找類似，查找效率高； 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列即實(shí)現(xiàn)中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列即實(shí)現(xiàn)了排序運(yùn)算；了排序運(yùn)算； 假設(shè)查找不勝利，可以方便地將被查元素插入到二叉樹的葉子假設(shè)查找不勝利，可以方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時只需修正指針而不需挪動元素。結(jié)點(diǎn)上，而且插入或刪除時只需修正指針而不需挪動元素。注：假設(shè)數(shù)據(jù)元素的輸入順序不同，那么得到的二叉排序樹注

25、：假設(shè)數(shù)據(jù)元素的輸入順序不同，那么得到的二叉排序樹形狀也不同！形狀也不同！這種既查找又插入的過程稱為動態(tài)查找。這種既查找又插入的過程稱為動態(tài)查找。二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。它是動態(tài)查找表的一種適宜表示。45452424535312129090假設(shè)待查找的關(guān)鍵字序列輸入順序?yàn)椋杭僭O(shè)待查找的關(guān)鍵字序列輸入順序?yàn)椋?424，5353， 45 45，4545，1212，2424，9090，24245353454512129090查查找找勝勝利，利，前前往往查查找找勝勝利，利，前前往往那么生成

26、二叉排那么生成二叉排序樹的過程為：序樹的過程為：例：輸入待查找的關(guān)鍵字序列例：輸入待查找的關(guān)鍵字序列= =4545，2424，5353，4545，1212，2424，9090那么生成的二叉那么生成的二叉排序樹形狀不同：排序樹形狀不同：查查找找勝勝利，利，前前往往查查找找勝勝利，利，前前往往查找算法參見教材查找算法參見教材P228算法算法9.5a,b;插入算法參見教材插入算法參見教材P228算法算法9.6;對于二叉排序樹，刪除樹上一個結(jié)點(diǎn)相當(dāng)于刪除有序序列中對于二叉排序樹，刪除樹上一個結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個記錄，刪除后仍需堅持二叉排序樹的特性。的一個記錄，刪除后仍需堅持二叉排序樹的特性。

27、對鏈表進(jìn)展刪除操作是很方便的對鏈表進(jìn)展刪除操作是很方便的如何刪除一個結(jié)點(diǎn)？如何刪除一個結(jié)點(diǎn)？假設(shè)：假設(shè)：* *p p表示被刪結(jié)點(diǎn)的指針；表示被刪結(jié)點(diǎn)的指針； PLPL和和PR PR 分別表示分別表示* *P P的左、的左、右孩子指針；右孩子指針；* *f f表示表示* *p p的雙親結(jié)點(diǎn)指針；并假定的雙親結(jié)點(diǎn)指針；并假定* *p p是是* *f f的左孩子；那么能的左孩子；那么能夠有三種情況：夠有三種情況：PR PR 為為 * * S S 的右子樹；的右子樹； SL SL 為為 Q Q * * S S的雙親結(jié)點(diǎn)右孩子的雙親結(jié)點(diǎn)右孩子* *p p為葉子：為葉子： 刪除此結(jié)點(diǎn)時，直接修正刪除此結(jié)點(diǎn)時，直接修正* *f f指針域即可；指針域即可；* *p p只需一棵子樹或左或右：令只需一棵子樹或左或右：令PLPL或或PRPR為為* *f f的左孩子即可；的左孩子即可；* *p p有兩棵子樹：情況最復(fù)雜有兩棵子樹：情況最復(fù)雜 分析：分析：設(shè)刪除前的中序遍歷序列為：設(shè)刪除前的中序遍歷序列為：. s p PR . /. s p PR . /顯然顯然p p的直接前驅(qū)是的直接前驅(qū)是s s希望刪除希望刪除p p后，其它元素的相對位置不變。有兩種處理方法：后，其它元素的相對位置不變。有兩種處理方法：法法1 1：令：令* *p p的左子樹為的左子