靜態(tài)查找表2、動(dòng)態(tài)查找表3、哈希查找表-資料下載頁(yè)
2025-07-21 17:23本頁(yè)面
【正文】 12 24 37 40 55 40， 24， 12， 37， 55 12， 24， 37， 40， 55 顯然，第 i 層結(jié)點(diǎn)需比較 i 次。在等概率的 前提下，上述兩圖的平均查找長(zhǎng)度為： )(35/)54321()()23221(11右圖左圖????????????????niiiniiicpcp查找運(yùn)算 由上例分析易知： 在二叉排序樹中進(jìn)行查找的平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)，即， 最壞 : （ n+1)/2（單支樹） 最好： log2n（形態(tài)勻稱，與二分查找的判定樹相似） 查找運(yùn)算 Status SearchBST ( BiTree T， KeyType key， BiTree f， BiTree amp。p ) // 在二叉分類樹查找關(guān)鍵字之值為 key 的結(jié)點(diǎn)。初始時(shí) f 為 NULL。 如樹空，返回 p 為 NULL及 FALSE。 如樹非空且查找成功，返回 p = T 及 TRUE。 如樹非空且查不成功，返回 p = f 及 FALSE。 f 為待插入結(jié)點(diǎn)的的父親結(jié)點(diǎn)的地址。 { if ( ( !T) { p = f。 return FALSE。 } else if ( EQ( key, T data. key ) ) { p = T。 return TRUE。 } else if ( LT( key , T data. key ) ) return (SearchBST ( T lchild, key, T, p ))。 else return (SearchBST ( T rchild, key , T, p ))。 } // SearchBST 程序?qū)崿F(xiàn) 查找運(yùn)算 在一棵給定的二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，必須保證刪除后仍符合二叉排序樹的定義。關(guān)鍵是要找出替換結(jié)點(diǎn)。 遞歸描述： 當(dāng) r（根）為空時(shí)返回，否則： 當(dāng) rkey大于 k，在 r的左子樹中刪除之， 當(dāng) rkey小于 k，在 r的右子樹中刪除之， 當(dāng) r的左子樹為空時(shí)，用 r的右子樹代替， 當(dāng) r的右子樹為空時(shí)，用 r的左子樹代替， 當(dāng) r的左、右子樹不空時(shí)，找出 r的左子樹的 “ 最右下 ”（最大結(jié)點(diǎn)）代替 r。 刪除運(yùn)算 非遞歸描述： (1) 若被刪結(jié)點(diǎn)無(wú)右孩子，則用它的左孩子代替該結(jié)點(diǎn)； f p s (2) 若被刪結(jié)點(diǎn)無(wú)左孩子，則用它的右孩子代替該結(jié)點(diǎn)； f rc p s lc p為被刪結(jié)點(diǎn) p為被刪結(jié)點(diǎn) S為替換結(jié)點(diǎn) S為替換結(jié)點(diǎn) 刪除運(yùn)算 非遞歸描述： (3) 若被刪結(jié)點(diǎn)有左、右孩子，則用它的前驅(qū)結(jié)點(diǎn) s（被刪結(jié)點(diǎn)的左子樹中數(shù)據(jù)域值最大的結(jié)點(diǎn)，即左子樹“最右下”的結(jié)點(diǎn)）代替被子刪結(jié)點(diǎn)，此時(shí)，由于 s結(jié)點(diǎn)無(wú)右孩子（參見下圖），可按上述第（ 1）種情況刪除 s結(jié)點(diǎn)。 f prc p s p為被刪結(jié)點(diǎn) S為替換結(jié)點(diǎn) q為替換結(jié)點(diǎn)的雙親。 plc slc q 刪除運(yùn)算 在一棵給定的二叉排序樹中刪除一個(gè)結(jié)點(diǎn)示例： 10 3 6 2 4 18 12 15 6 3 4 2 18 12 15 刪除 10 刪除運(yùn)算 在一棵給定的二叉排序樹中刪除一個(gè)結(jié)點(diǎn)示例： 6 3 4 2 18 12 15 刪除 12 6 3 4 2 18 15 刪除運(yùn)算 在一棵給定的二叉排序樹中刪除一個(gè)結(jié)點(diǎn)示例： 6 3 4 2 18 15 6 3 4 2 15 刪除 18 刪除運(yùn)算 刪除運(yùn)算 Status DeleteBST ( BiTree amp。T， KeyType key ) // 若二叉分類樹 T 中存在 關(guān)鍵字為 key 的結(jié)點(diǎn)時(shí)，則刪除該結(jié)點(diǎn)，并返回 TRUE； 否則返回 FALSE。 { if ( ( !T) return FALSE。 // 二叉分類樹 T 中不存在 關(guān)鍵字為 key 的結(jié)點(diǎn) else if ( EQ( key, T data. key ) ) Delete (T)。 // 存在 關(guān)鍵字為 key 的結(jié)點(diǎn)，進(jìn)行刪除 else if ( LT( key , T data. key ) ) DeleteBST ( T lchild, key )。 else DeleteBST ( T rchild, key )。 return TRUE。 } // DeleteBST
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1