【正文】 平衡二叉樹 平衡二叉樹 (也稱 AVL樹 )，它或者是一棵 空樹 ,或者是具有以下性質(zhì)的二叉樹 :它的左子樹和右子樹也都是 平衡二叉樹 ，并且左子樹和右子樹的 深度之差 的 絕對值不超過 1。 free(s)。 if( q == p ) qrchild = srchild。 s = srchild。 s = plchild。 free(p)。 free(p)。 free(p)。amp。 free(s)。 if( q == p ) qrchild = srchild。 s = srchild。 s = plchild。 free(p)。 free(p)。 free(p)。amp。 free(s)。 if( q == bt ) qrchild = srchild。 s = srchild。 s = btlchild。 free( r )。 //空樹 else if( !btlchild) bt = btrchild。amp。 exit(0)。 else r = rrchild。 rdata != pdata ) //在 bt中查找結(jié)點 p { f = r 。 while( r amp。bt, BiTree p) {//在二叉排序樹 bt中刪除結(jié)點 p，使 bt仍然保持其有序性 if(bt) { r = bt。 free(s)。 if (q != p) qrchild = slchild。 s = srchild。 s=plchild。 free(p)。 } flchild = plchild。 while( srchild ) { q=s。如圖所示： 算法的執(zhí)行過程如下： q=p。 41132173019中序遍歷序列： 2, 3, 4, 11, 17, 19, 30 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 （ 4）二叉排序樹的刪除 對一般的二叉樹而言，刪去樹中一個結(jié)點是無意義的（因為刪除該結(jié)點后，二叉樹就變成了森林），而對于二叉排序樹，刪除一個結(jié)點相當(dāng)于刪去有序序列中的一個記錄，只要在刪除某個結(jié)點后依舊保持二叉排序樹的特性即可。 相當(dāng)于在一個有序序列上插入一個記錄而不需要移動其他記錄。 41132173019數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 由構(gòu)造的二叉排序樹可以看出： 1) 中序遍歷二叉排序樹可得到一個結(jié)點值的有序序列。 else prchild = s。 if ( !p ) //空二叉樹 T = s。 sdata = e。 else return (SearchBST(Trchild, key, T, p)。 return TRUE。 return FALSE。因此很容易寫出如下算法： (1) 調(diào)用查找過程 SearchBST (T， key， f， p)； (2) 若查找不成功時做： ① 動態(tài)生成一具有關(guān)鍵字值為 Key的新結(jié)點 s； ② 若 root為 NULL，則 root=s； ③ 若 Key＜ p，則 plchild = s； ④ 若 Key＞ p，則 prchild = s； 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 Status SearchBST( BiTree T, KeyType key, BiTree f, BiTree amp。 else return ( SearchBST( T rchild, key )。 else if( key == T ) return T。 2)如果給定值小于根結(jié)點的關(guān)鍵字，遞歸查找根結(jié)點的左子樹； 3)否則 ,遞歸查找根結(jié)點的右子樹。 3) 它的左、右子樹也分別為二叉排序樹。它或是一棵 空樹 ，或是具有下列性質(zhì)的二叉樹： 4 51 23 3 72 45 31 0 06 19 07 8二 叉 排 序 樹 示 例空 樹 1) 若它的左子樹不空，則左子樹上所有結(jié)點 的值 均小于 它的根結(jié)點的值 。即對于給定值 key，若表中存在其關(guān)鍵字等于 key的記錄，則查找成功返回，否則 插入 關(guān)鍵字等于 key的記錄。 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 3. 索引順序表的查找（分塊查找） 查找表的特點： 查找表可分成若干塊，塊內(nèi)元素?zé)o序，但塊與塊之間有序； 查找過程： 先確定待查記錄所在塊（可用順序查找或折半查找），再在塊內(nèi)查找 。 } 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 查找成功示例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 21 low high mid 查找成功 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 查找失敗示例 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high 找 70 mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high Highlow，查找失敗 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 判定樹：描述折半查找過程的二叉樹 11 8 5 2 10 7 4 1 9 3 6 判定樹 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 性能分析： 結(jié)論： ?查找到一個記錄與給定值比較的關(guān)鍵字個數(shù)恰好等于該結(jié)點在判定樹上的深度； ?有 n個結(jié)點的判定樹的深度為 ?log2n?+1； ?折半查找法在查找過程中進行的比較次數(shù)最多不超過其判定樹的深度。 else low = mid+1。 if ( key == [mid].key) return mid。 high = 。 若 keyr[mid].key，則 low=mid+1。 3) 讓 key與 mid指向的記錄比較 若 key==r[mid].key，查找成功 。 (2)假定各記錄的查找機會均等，即 Pi＝ 1/n（ 等概率 ），由于查找第 i個記錄需要比較 ni+1次，即 Ci＝ ni+1，于是有： ?????????? niniiininnPCA S L 11 21)1(1數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 2. 有序表的查找 查找方法： 折半查找 斐波那契查找 插值查找 折半查找： 查找過程 ：每次將待查記錄所在區(qū)間縮小一半 算法實現(xiàn) ： 1) 設(shè)表長為 n， low、 high和 mid分別指向待查元素所在區(qū)間的下界、上界和中點 , key為給定值 。 對 n個記錄進行查找時