靜態(tài)查找表2、動(dòng)態(tài)查找表3、哈希查找表(參考版)
2025-07-24 17:23本頁面
【正文】 } // DeleteBST 。 else DeleteBST ( T rchild, key )。 // 二叉分類樹 T 中不存在 關(guān)鍵字為 key 的結(jié)點(diǎn) else if ( EQ( key, T data. key ) ) Delete (T)。T， KeyType key ) // 若二叉分類樹 T 中存在 關(guān)鍵字為 key 的結(jié)點(diǎn)時(shí)，則刪除該結(jié)點(diǎn)，并返回 TRUE； 否則返回 FALSE。 f prc p s p為被刪結(jié)點(diǎn) S為替換結(jié)點(diǎn) q為替換結(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。 } // SearchBST 程序?qū)崿F(xiàn) 查找運(yùn)算 在一棵給定的二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，必須保證刪除后仍符合二叉排序樹的定義。 } else if ( LT( key , T data. key ) ) return (SearchBST ( T lchild, key, T, p ))。 } else if ( EQ( key, T data. key ) ) { p = T。 { if ( ( !T) { p = f。 如樹非空且查不成功，返回 p = f 及 FALSE。 如樹空，返回 p 為 NULL及 FALSE。p ) // 在二叉分類樹查找關(guān)鍵字之值為 key 的結(jié)點(diǎn)。 考慮如下兩種不同插入次序的序列構(gòu)成的二叉排序樹， 插入次序分別為： 40 24 55 12 37 12 24 37 40 55 40， 24， 12， 37， 55 12， 24， 37， 40， 55 查找運(yùn)算 插入次序分別為： 40 24 55 12 37 12 24 37 40 55 40， 24， 12， 37， 55 12， 24， 37， 40， 55 顯然，第 i 層結(jié)點(diǎn)需比較 i 次。 } // Insert BST 程序?qū)崿F(xiàn) 插入算法 在一棵給定的二叉排序樹中查找鍵值為 k的結(jié)點(diǎn)的方法是： 若樹為空，返回空指針，否則： 若 k rkey，在左子樹檢索 k，否則： 若 k rkey，在右子樹檢索 k，否則： k = rkey，找到，返回 k的指針；若找到某個(gè)結(jié)點(diǎn)的左子樹或右子樹是空，則查找失敗并返回空指針。 return TRUE。 else if ( LT( , p data. key ) ) p lchild = s。 slchild = srchild = NULL。 { if ( ! SearchBST ( T， ， NULL， p ) { s = ( Bitree ) malloc ( sizeof ( BitNode ) )。 45 12 53 3 37 24 100 61 90 78 20 插入運(yùn)算 Status Inset BST ( BiTree amp。而插入的結(jié)點(diǎn)作為葉子結(jié)點(diǎn)。 插入運(yùn)算 在一棵給定的二叉排序樹中插入新結(jié)點(diǎn)，只要保證插入仍符合二叉排序樹的定義即可。 結(jié)點(diǎn)類型定義 在一棵給定的二叉排序樹中插入新結(jié)點(diǎn)，只要保證插入仍符合二叉排序樹的定義即可。 }JD。 二叉排序樹 45 12 53 3 37 24 100 61 90 78 按中序遍歷： 3， 12， 24， 37， 45， 53， 61， 78， 90， 100 遞增 二叉排序樹 Typedef struct node {int key。 A、 B、 C、 D、 E 1 30 2 29 3 靜態(tài)樹表的查找 定義： 或是空樹，或是具有如下性質(zhì)的二叉樹： （ 1）若它的 lc非空，則 lc上所有結(jié)點(diǎn)的 key 根的 key（ 2）若它的 rc非空，則 rc上所有結(jié)點(diǎn)的 key 根的 key （ 3）它的 lc、 rc本身又是一棵二叉排序樹 二叉排序樹 性質(zhì)： 對(duì)二叉排序樹按中序遍歷所得到的中序序列是一個(gè)遞增的有序序列。 靜態(tài)樹表的查找 次最優(yōu)查找樹： H E G D F
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1