【正文】 “存儲不足 endl。 遞歸的二叉搜索樹插入算法 void Insert ( DataType x, BstNode * amp。 ? 搜索成功 : 樹中已有這個元素 ,不再插入 。 ? 為了向二叉搜索樹 中插入一個新元素， 必須先檢查這個 元 素是否在樹中已經(jīng) 存在 。 //左子樹 } } return NULL。 if ( pdata x ) p = prightChild。 35 15 45 50 25 10 20 30 搜索 22 搜索 45 46 BstNode * Find ( BstNode *ptr, DataType x ) { //二叉搜索樹的迭代的搜索算法 if ( ptr != NULL ) { BstNode * p = ptr。 45 ? 搜索成功時檢測指針停留在樹中某個結(jié)點(diǎn)。 ? 如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼 ， 則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹； ? 否則 。 二叉搜索樹上的搜索 35 15 45 50 40 25 10 20 30 搜索 45 搜索成功 搜索 28 搜索失敗 44 ? 假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x的元素 ， 搜索過程從根結(jié)點(diǎn)開始 。 43 在二叉搜索樹上進(jìn)行搜索， 是一個從根結(jié)點(diǎn)開始，沿某一個分支逐層向下進(jìn)行比較判等的過程 。 typedef BstNode *BST。 struct node *leftChild, *rightChild。 41 n 個結(jié)點(diǎn)的二叉搜索樹的數(shù)目 【例】 3 個結(jié)點(diǎn)的二叉搜索樹 51*2*34*5*6*41C131 33*2 ???1 2 2 1 3 3 1 3 2 1 2 3 1 2 3 {123} {132} {213} {231} {312} {321} 42 二叉搜索樹的結(jié)構(gòu)定義 typedef char DataType。 ? 左子樹和右子樹也是二叉搜索樹。 ? 左子樹 (如果存在 )上 所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼 。 …, 第 i (0 ? i ? h) 層結(jié)點(diǎn)有 2i 個 , 搜索第 i 層結(jié)點(diǎn)要比較 i+1次 ， … 。 ? 第 0層結(jié)點(diǎn)有 1個 , 搜索第 0層結(jié)點(diǎn)要比較 1次 。 //搜索失敗 } 基于有序順序表的折半搜索迭代算法 36 ? 有序順序表的折半搜索的判定樹 ( 10, 20, 30, 40, 50, 60 ) 10 50 = = = = = = 30 20 40 60 ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 37 折半搜索性能分析 ? 若設(shè) n = 2h1， 則描述折半搜索的判定樹是高度為 h1 的滿二叉樹 。 //左縮搜索區(qū)間 else return mid。 if ( [mid].key x ) low = mid + 1。 } 基于有序順序表的折半搜索遞歸算法 35 int BinarySearch ( dataList A, DataType x ) { int high = , low = 0, mid。 else if ( [mid].key x ) mid = BinarySearch ( A, x, low, mid 1 )。 if ( low = high ) { mid = ( low + high ) / 2。 ? 如果搜索區(qū)間已縮小到一個對象 ， 仍未找到想要搜索的對象 ， 則搜索失敗 。 //順序搜索失敗 , 返回失敗信息 } 基于有序順序表的順序搜索算法 30 ? 有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 ? ?27161 50??? ??is u c c iA SL? ?7276171 50?????????????iu n s u c ciA SL31 基于有序順序表的折半搜索 ? 設(shè) n個對象存放在一個按其關(guān)鍵碼從小到大排好了序的有序順序表中 。 //成功 else if ( [i].key x ) break。 i 。 //搜索成功 else return SequentSearch ( A, x, loc+1 )。 //參數(shù) loc 是在表中開始搜索位置 if ( loc = ) return 1。 在搜索不成功情形， ASLunsucc = n+1. 28 順序搜索的遞歸算法 int SequentSearch ( dataList A, dataType x, intamp。 //從后向前順序搜索 return i。 int i = 。 給出失敗信息 。 給出該對象在表中的位置 。 24 順序搜索 (Sequential Search) ? 所謂順序搜索 , 又稱線性搜索 , 主要用于在線性結(jié)構(gòu)中進(jìn)行搜索 。 直到 找到 x在數(shù)組中的位置或可確定在數(shù)組中 找不到 x為止 。 ? 在靜態(tài)搜索表中 , 利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)對象的存放地址 。 //數(shù)據(jù)存儲數(shù)組 int n。 //其他數(shù)據(jù)域 } ListNode。 //搜索數(shù)據(jù)的類型 typedef struct { //搜索表結(jié)點(diǎn)定義 DataType key。 ? 靜態(tài)搜索表 ? 動態(tài)環(huán)境 ，為保持較高的搜索效率 , 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 21 ? 實(shí)施搜索時有兩種不同的環(huán)境。 使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。 ? 在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標(biāo)識這個對象。作為結(jié)果 , 應(yīng)報告一些信息 , 如失敗標(biāo)志、位置等。 ? 搜索的結(jié)果通常有兩種可能： ? 搜索成功 ，即找到滿足條件的數(shù)據(jù)對象 這時 ,作為結(jié)果 , 可報告該對象在結(jié)構(gòu)中 的位置 , 還可給出該對象中的具體信息。 } return j。 Sparent[i] = j。 while ( Sparent[j] = 0 ) j = Sparent[j]。 即： 如果 j 是從 i 到根 root 的 路 徑 上 的 一 個 結(jié) 點(diǎn) ， 且 Sparent[j] != root[j]， 則把 Sparent[j] 置為 root[i]。 //Root1中結(jié)點(diǎn)多 Sparent[Rt1] = temp。 //Root2中結(jié)點(diǎn)多 Sparent[Rt2] = temp。 ? 若再執(zhí)行 Find(0), Find(1), …, Find(n1), 若被搜索的元素為 i，完成 Find(i) 操作需要時間為 O(i)， 完成 n 次搜索需要的總時間將達(dá)到 ? 改進(jìn)的方法 ? 按樹的結(jié)點(diǎn)個數(shù)合并 ? 按樹的高度合并 ? 壓縮元素的路徑長度 ???nini12OO )()(14 ? 按樹結(jié)點(diǎn)個數(shù)合并 ?結(jié)點(diǎn)個數(shù)多的樹的根結(jié)點(diǎn)作根 1 1 1 1 1 0 1 2 3 4 1 1 0 7 2 5 6 5 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) 15 void WeightedUnion (UFSets *S, int Rt1, int Rt2 )