【正文】 tChild = NULL。 pdata = item。 else current = currentleftChild。 parent = current。 current = *root。 } 三、插入算法 插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若 存在則返回 ；若不存在， 插入查找失敗時結(jié)點的左指針或右指針上。 else p = pleftChild。 while(p != NULL) { if(p == ) return 1。 381 12 410 9 40 394 540 35 190 146 476 760 445 600 800 下圖所示就是一棵二叉排序樹 二、二叉排序樹的查找算法 int Search(BiTreeNode *root, DataType item) { BiTreeNode *p。 struct node *rightChild。 二叉排序樹中結(jié)點的結(jié)構(gòu)體定義如下： typedef struct node { DataType data。樹結(jié)構(gòu)有 B樹、 B+樹 等。 相關(guān)術(shù)語 假設(shè)索引表的長度為 m， 主表中每個子表的長度為 s， 并假設(shè)在索引表上和在主表上均采用順序查找算法 ， 則索引順序表上查找算法的 平均查找長度 為： 122 12 1 ??????? smsmA S L算法分析 動態(tài)查找表 動態(tài)查找表主要有 二叉樹結(jié)構(gòu) 和 樹結(jié)構(gòu) 兩種類型。反之稱為 不等長索引表 。 完全索引表 :和主表項完全相同，但只包含索引關(guān)鍵字和該數(shù)據(jù)元素在主表中位置信息的索引表 二級索引表 :當(dāng)主表中的數(shù)據(jù)元素個數(shù)非常龐大時，按照建立索引表的同樣方法對索引表再建立的索引表。主表中存放著數(shù)據(jù)元素的 全部信息 ，索引表中只存放主表中要查找數(shù)據(jù)元素的 主關(guān)鍵字和索引信息 。 //查找失敗 } 算法分析 查找成功時的平均查找長度 ASL成功 為： 查找失敗時的平均查找長度 ASL失敗 為 nnnninCPA S Lnikiiii 221 11 lo g1)1(lo g112 ??????? ? ?? ??成功)1(lo g)1(lo g1 221 1????? ? ?? ?nnnCPA S Lniniii失敗 當(dāng)順序表中的數(shù)據(jù)元素個數(shù)非常大時，采用 在順序表上建立索引表 的辦法提高查找速度。 else high = mid 1。 //確定查找區(qū)間中心下標(biāo) if(a[mid].key == key) return mid。 //確定初始查找區(qū)間上下界 int mid。反之，如果 key大，則縮小至后半部內(nèi)查找。 } 算法分析 查找成功時的平均查找長度 ASL成功 為： ????????niinii ninCPA S L112/)1(1成功查找失敗時的平均查找長度 ASL失敗 為 2/)1(111???? ????ninCPA S Lniinii失敗時間效率為 O(n) 有序順序表上的查找算法主要有 順序查找 和 折半查找 兩種方法。 if(a[i].key == key) return i。amp。 查找函數(shù)設(shè)計如下： int SeqSearch(DataType a[], int n, KeyType key) //在 a[0]a[n1]中順序查找關(guān)鍵碼為 key的數(shù)據(jù)元素 //查找成功時返回該元素的下標(biāo)序號；失敗時返回 1 { int i = 0。 } DataType。 主關(guān)鍵字 :能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字 次關(guān)鍵字 :通常不能惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字 查找成功 :在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素 查找不成功 :在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素 靜態(tài)查找 :只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素 動態(tài)查找 :既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素 靜態(tài)查找表 :靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu) 動態(tài)查找表 :動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu) 平均查找長度 :查找過程所需進行的關(guān)鍵字比較次數(shù)的平均值 ,是衡量查找算法效率的最主要標(biāo)準(zhǔn) ,其數(shù)學(xué)定義為： ?? ??niii CPA S L1其中， Pi是要查找數(shù)據(jù)元素出現(xiàn)的概率， Ci是查找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。第 10章 查找 查找的基本概念 靜態(tài)查找表 動態(tài)查找表 哈希表 主要知識點 查找的基本概念 查找 :查詢 關(guān)鍵字 是否在 (數(shù)據(jù)元素集合）表中的過程。也稱作 檢索 。 定義要 查找數(shù)據(jù)元素的結(jié)構(gòu)體為： typedef struct { KeyType key。 靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表 有序順序表 索引順序表 在順序表上查找的 基本思想是： 從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回 1。 while(i n amp。 a[i].key != key) i++。 else return 1。 一 、 順序查找 有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（ 又稱 折半查找） 算法的基本思想： 先給數(shù)據(jù)排序 （例如按升序排好），形成 有序表， 然后再將 key與 正中 元素相比，若 key小，則縮小至前半部內(nèi)查找；再取其 中值 比較，每次縮小 1/2的范圍，直到查找成功或失敗為止。 二分查找算法如下： int BiSearch(DataType a[], int n, KeyType key) //在有序表 a[0]a[n1]中二分查找關(guān)鍵碼為 key的數(shù)據(jù)元素 //查找成功時返回該元素的下標(biāo)序號；失敗時返回 1 { int low = 0, high = n 1。 while(low = high) { mid = (low + high)/2。