【正文】 的；當(dāng)二叉排序樹的樹型為只有一個端結(jié)點(diǎn)的所謂“退化樹”時，其高度等于 n，最壞情況下查找時間為O(n)，與順序查找屬于同一數(shù)量級。 else prflchild=prrchild。} pelem = prelem。 while(prlchild) /*查找 *p結(jié)點(diǎn)的直接后繼 pr, prf指向 *pr結(jié)點(diǎn)的雙親 */ { prf=pr。 ? } 第 8章 查找 ? /*第 3種情況：被刪除結(jié)點(diǎn)左右子樹都非空 */ prf=p。 /*被刪除的結(jié)點(diǎn)是雙親結(jié)點(diǎn)的右孩子 */ free(p)。 } if(p ==pflchild) pflchild=plchild。 free(p)。 return 1。 /*被刪除的結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子 */ else pfrchild=prchild。 return 1。 ? } 第 8章 查找 /*第 2種情況：被刪除的結(jié)點(diǎn)的左子樹為空或右子樹為空 */ if( !plchild) /*被刪除的結(jié)點(diǎn)左子樹為空 */ { if(pf == NULL) {*bt=prchild。 free(p)。} /*被刪除的結(jié)點(diǎn)是根結(jié)點(diǎn) */ if(p == pflchild) pflchild=NULL。 !prchild) { if(pf == NULL) {*bt=NULL 。 /*查找失敗，刪除失敗 */ /*第 1種情況：被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn) */ if (!plchild amp。pf)。 find=Search_BinTree1(*bt, kx, amp。 int find。 ? } 第 8章 查找 ? int Delete_BinTree(BinTree *bt, KeyType kx) /*刪除二叉排序樹中關(guān)鍵碼值為 kx的結(jié)點(diǎn)，如果有多個，只刪除第一次遇到的結(jié)點(diǎn)。*p=(*p)rchild 。*p=(*p)lchild 。 while(*p) { if((*p)==kx) return 1 。 ? 如何保證呢，如何檢驗(yàn)?zāi)兀? 刪除后保持所有節(jié)點(diǎn)的中序遍歷順序不變 第 8章 查找 要刪除二叉排序樹中的 p結(jié)點(diǎn)，分三種情況： ? p為葉子結(jié)點(diǎn)，只需修改 p雙親 f的指針 flchild=NULL frchild=NULL ? p只有左子樹或右子樹 ? p只有左子樹，用 p的左孩子代替 p (1)(2) ? p只有右子樹，用 p的右孩子代替 p (3)(4) ? p左、右子樹均非空 ? 沿 p左子樹的根 C的右子樹分支找到 S， S的右子樹為空，將 S的左子樹成為 S的雙親 Q的右子樹，用 S取代 p (5) ? 若 C無右子樹，用 C取代 p (6) 第 8章 查找 S Q PL P 中序遍歷： Q S PL P S Q PL 中序遍歷： Q S PL (2) S P PL Q 中序遍歷： PL P S Q S PL Q 中序遍歷： PL S Q (1) 第 8章 查找 中序遍歷： P PR S Q S PR Q 中序遍歷： PR S Q (3) S P PR Q 中序遍歷： Q S P PR S Q PR 中序遍歷： Q S PR (4) S Q PR P 第 8章 查找 F P C PR CL Q QL S SL 中序遍歷： CL C ……Q L Q SL S P PR F F S C PR CL Q QL SL 中序遍歷： CL C ……Q L Q SL S PR F (5) F P C PR CL 中序遍歷： CL C P PR F F C PR CL 中序遍歷： CL C PR F (6) 第 8章 查找 例 80 50 120 60 110 150 55 70 53 刪除 50 80 60 120 110 150 55 70 53 刪除 60 80 55 120 110 150 53 70 10 4 25 8 13 5 4 刪除 10 8 4 25 5 13 4 刪除 5 8 4 25 4 13 第 8章 查找 算法 88 二叉排序樹的刪除算法 ? 查找算法的另一版本 , 不僅返回指向待查找結(jié)點(diǎn)的指針 ,還返回指向它的雙親的指針 ? int Search_BinTree1(BinTree bt , KeyType kx , BitNode **p, BitNode **pf) /*查找二叉排序樹中關(guān)鍵碼值為 kx的結(jié)點(diǎn)， *p指向待查找的結(jié)點(diǎn) ， *pf指向待查找的結(jié)點(diǎn)的雙親結(jié)點(diǎn) ，如果如果查找成功，返回 1，否則返回 0*/ { *p=bt。 /*在右子樹查找 */ } 可以計(jì)算二叉排序樹的 ASL(計(jì)算方法與計(jì)算折半查找的判定樹的 ASL相同 )。 /*查找成功 */ if(bt kx) return Search_BinTree(btlchild, kx)。 第 8章 查找 算法 85 二叉排序樹的查找算法 BitNode *Search_BinTree(BinTree bt , KeyType kx) {/*在二叉排序樹 bt上查找關(guān)鍵碼為 kx的元素，若找到，返回指向該元素的指針，否則，返回空指針 */ if (bt == NULL) return NULL。 } 第 8章 查找 3．二叉排序樹的查找 ? 從其定義可見，二叉排序樹的查找過程如下： ① 若查找樹為空，說明查找失敗，返回 查找失敗 信息。kx)。 while(kx != ENDFLAG) { bt=Insert_BinTree(bt, kx)。 scanf(“%d”,amp。 } 第 8章 查找 算法 87 構(gòu)造二叉排序樹的算法 define ENDFLAG 1 /* ENDFLAG為輸入數(shù)據(jù)的結(jié)束標(biāo)志 */、BinTree Creat_BinTree( ) { /*從空樹開始構(gòu)造二叉排序樹，返回指向根結(jié)點(diǎn)指針 */ BinTree bt=NULL。 /*插入到左子樹 */ else btrchild=Insert_BinTree(btrchild, kx)。 return bt。 btlchild=NULL。 第 8章 查找 –舉例 ： 例 設(shè)有 {10， 18， 3， 8， 12， 2， 7， 3} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 3 二叉排序樹的特點(diǎn)：中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列 如果是其它排列，樹會是什么樣？ 第 8章 查找 算法 86 二叉排序樹的插入算法 BinTree Insert_BinTree(BinTree bt , KeyType kx) { /*在二叉排序樹 bt上插入關(guān)鍵碼為 kx的元素，返回指向根結(jié)點(diǎn)指針 */ if (bt == NULL) /*如果是空樹，則插入后成為根結(jié)點(diǎn) */ { bt = (BitNode *)malloc(sizeof(BitNode)) 。 ? 同樣的關(guān)鍵字，如果給出的順序不同，生成的樹也不同。 二叉排序樹插入實(shí)際上也是在二叉排序樹中查找一個結(jié)點(diǎn)的過程。 struct node *lchild,*rchild 。 10 18 3 8 12 2 7 第 8章 查找 本節(jié)采用二叉鏈表實(shí)現(xiàn)二叉排序樹的存儲。 1)21)1(21)121 ?????? mnmmnmA SLA SLA SL （＝＋（＝子表索引表n1?? nA S L第 8章 查找 靜態(tài)查找表三種查找方法比較 順序查找 折半查找 分塊查找 ASL 最大 最小 兩者之間 表中數(shù)據(jù)元素 按關(guān)鍵碼值有序或無序 按關(guān)鍵碼值有序 按關(guān)鍵碼值分塊有序 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)或線性鏈表 順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)或線性鏈表 索引存儲 第 8章 查找 ? 小結(jié)或下次課前回顧提問 ? 什么是查找表？ ? 關(guān)鍵碼是什么？ ? 如何衡量一個查找方法的時間性能？ ? 什么是靜態(tài)查找表，它可以怎樣存儲？ ? 靜態(tài)查找表（可以以線性表的方式組織）和一般的線性表有什么不同？ ? 靜態(tài)查找的方法。 ? } 第 8章 查找 算法性能分析 ? 分塊查找由索引表查找和塊內(nèi)查找兩步完成。enpos) == 0) return 0 。 if( index_search( si , st , amp。 return i。 [i] != kx) i++ 。 while(i = enpos amp。 ? } 第 8章 查找 ? int table_search(Sq_Table st , int stpos , int enpos , KeyType kx) /*塊內(nèi)查找： st為查找表， stpos存儲所在塊內(nèi)第一個數(shù)據(jù)元素在查找表中的位置， enpos存儲所在塊內(nèi)最后一個數(shù)據(jù)元素在查找表中的位置， kx為給定關(guān)鍵碼值。 else *enpos = [i+1].link1。 *stpos = [i].link。 [i].key kx) i++。 while(i amp。 第 8章 查找 算法 84 分塊查找的算法 ? int index_search(Sq_Index si , Sq_Table st , KeyType kx , int *stpos , int *enpos) /*在索引表中順序查找： kx為給定關(guān)鍵碼值， si為索引表， st為查找表， *stpos存儲所在塊內(nèi)第一個數(shù)據(jù)元素在查找表中的位置， *enpos存儲所在塊內(nèi)最后一個數(shù)據(jù)元素在