【文章內(nèi)容簡介】 40 bool Remove (const K x) { return Remove(x, root)。} //刪除含 x的結(jié)點(diǎn) private: BSTNodeE, K *root。 //根指針 K RefValue。 //輸入停止標(biāo)志 BSTNodeE, K * //遞歸：搜索 Search (const K x, BSTNodeE, K *ptr)。 void makeEmpty (BSTNodeE, K *amp。 ptr)。 //遞歸：置空 void PrintTree (BSTNodeE, K *ptr) const。 //遞歸：打印 BSTNodeE, K * //遞歸：復(fù)制 Copy (const BSTNodeE, K *ptr)。 41 BSTNodeE, K* Min (BSTNodeE, K* ptr)。 //遞歸：求最小 BSTNodeE, K* Max (BSTNodeE, K* ptr)。 //遞歸：求最大 bool Insert (const Eamp。 e1, BSTNodeE, K*amp。 ptr)。 //遞歸：插入 bool Remove (const K x, BSTNodeE, K*amp。 ptr)。 //遞歸：刪除 }。 ? 二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實(shí)現(xiàn)與二叉樹類似。 42 二叉搜索樹的搜索算法 ? 在二叉搜索樹上進(jìn)行搜索，是一個(gè) 從根結(jié)點(diǎn)開始 ， 沿某一個(gè)分支逐層向下 進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。 ? 假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x 的元素，搜索過程從根結(jié)點(diǎn)開始。 ? 如果 根指針為 NULL，則 搜索不成功 ；否則用給定值 x 與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較： ?若 給定值等于根結(jié)點(diǎn)關(guān)鍵碼 ，則 搜索成功 ，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。 43 ? 若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼 ， 則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹； ? 否則 。 遞歸搜索根結(jié)點(diǎn)的右子樹 。 搜索 45 搜索成功 搜索 28 搜索失敗 35 15 45 50 40 25 10 20 30 44 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //私有遞歸函數(shù)：在以 ptr為根的二叉搜索樹中搜 //索含 x的結(jié)點(diǎn)。若找到，則函數(shù)返回該結(jié)點(diǎn)的 //地址，否則函數(shù)返回 NULL值。 if (ptr == NULL) return NULL。 else if (x ptrdata) return Search(x, ptrleft)。 else if (x ptrdata) return Search(x, ptrright)。 else return ptr。 //搜索成功 }。 45 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //非遞歸函數(shù)：作為對比，在當(dāng)前以 ptr為根的二 //叉搜索樹中搜索含 x的結(jié)點(diǎn)。若找到，則函數(shù)返 //回該結(jié)點(diǎn)的地址，否則函數(shù)返回 NULL值。 if (ptr == NULL) return NULL。 BSTNodeE, K* temp = ptr。 while (temp != NULL) { if (x == tempdata) return temp。 if (x tempdata) temp = templeft。 46 else temp = tempright。 } return NULL。 }。 ? 搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自上而下逐層比較判等的過程。 ? 搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。 ? 設(shè)樹的高度為 h，最多比較次數(shù)不超過 h。 47 二叉搜索樹的插入算法 ? 為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在 。 ? 在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。 ? 如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入； ? 如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。 48 35 15 45 50 40 25 10 20 30 28 插入新結(jié)點(diǎn) 28 二叉搜索樹的插入 ? 每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。 49 二叉搜索樹的插入算法 template class E, class K bool BSTE, K::Insert (const Eamp。 e1, BSTNodeE, K *amp。 ptr) { //私有函數(shù)：在以 ptr為根的二叉搜索樹中插入值為 //e1的結(jié)點(diǎn)。若在樹中已有含 e1的結(jié)點(diǎn)則不插入 if (ptr == NULL) { //新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入 ptr = new BstNodeE, K(e1)。 //創(chuàng)建新結(jié)點(diǎn) if (ptr == NULL) { cerr Out of space endl。 exit(1)。 } return true。 50 } else if (e1 ptrdata) Insert (e1, ptrleft)。 //左子樹插入 else if (e1 ptrdata) Insert (e1, ptrright)。 //右子樹插入 else return false。 //x已在樹中 ,不再插入 }。 ? 注意參數(shù)表中引用型指針參數(shù) ptr的使用。 ? 利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。 51 輸入數(shù)據(jù) { 53, 78, 65, 17, 87, 09, 81, 15 } 53 53 78 53 78 65 53 78 65 17 53 78 65 87 17 53 78 65 09 17 87 53 78 65 81 17 87 09 53 78 65 15 17 87 09 81 52 template class E, class K BSTE, K::BST (K value) { //輸入一個(gè)元素序列 , 建立一棵二叉搜索樹 E x。 root = NULL。 RefValue = value。 //置空樹 cin x。 //輸入數(shù)據(jù) while ( != RefValue) { //RefValue是一個(gè)輸入結(jié)束標(biāo)志 Insert (x, root)。 cin x。 //插入，再輸入數(shù)據(jù) } }。 53 二叉搜索樹的刪除算法 ? 在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí) ， 必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來 ，同時(shí)確保二叉搜索樹的性質(zhì)不會失去 。 ? 為保證在刪除后樹的搜索性能不至于降低 ，還需要防止重新鏈接后樹的高度增加 。 ?刪除葉結(jié)點(diǎn) ， 只需將其雙親結(jié)點(diǎn)指向它的指針清零 ， 再釋放它即可 。 ?被刪結(jié)點(diǎn)右子樹為空 ， 可以拿它的左子女結(jié)點(diǎn)頂替它的位置 ， 再釋放它 。 54 ?被刪結(jié)點(diǎn)左子樹為空 ， 可以拿它的右子女結(jié)點(diǎn) 頂替它的位置 ， 再釋放它 。 ?被刪結(jié)點(diǎn)左 、 右子樹都不為空 ， 可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn) (關(guān)鍵碼最小 ),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中 ， 再來處理這個(gè)結(jié)點(diǎn)的刪除問題 。 53 78 65 17 87 09 23 45 刪除 45 右子樹空 , 用左子女頂替 53 78 65 17 87 09 23 55 88 53 78 88 17 94 09 23 刪除 78 左子樹空 , 用右子女頂替 53 94 88 17 09 23 53 78 81 17 94 09 45 刪除 78 在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ) 23 65 53 81 88 17 94 09 45 23 65 56 二叉搜索樹的刪除算法 template class E, class K bool BSTE, K::Remove (const K x, BstNodeE, K *amp。 ptr) { //在以 ptr 為根的二叉搜索樹中刪除含 x 的結(jié)點(diǎn) BstNodeE, K *temp。 if (ptr != NULL) { if (x ptrdata) Remove (x, ptrleft)。 //在左子樹中執(zhí)行刪除 else if (x ptrdata) Remove (x, ptrright)。 //在右子樹中執(zhí)行刪除 57 else if (ptrleft != NULL amp。amp。 ptrright != NULL) { //ptr指示關(guān)鍵碼為 x的結(jié)點(diǎn) ， 它有兩個(gè)子女 temp = ptrright。 //到右子樹搜尋中序下第一個(gè)結(jié)點(diǎn) while (templeft != NULL) temp = templeft。 ptrdata = tempdata。 //用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù) Remove (ptrdata, ptrright)。 } else { //ptr指示關(guān)鍵碼為 x的結(jié)點(diǎn)有一個(gè)子女 58 temp = ptr。 if (ptrleft == NULL) ptr = ptrright。 else ptr = ptrleft。 delete temp。 return true。 } } return false。 }。 ? 注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。 59 二叉搜索樹性能分析 ? 對于有 n 個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有 n! 種不同排列，可構(gòu)成不同二叉搜索樹有 (棵 ) C n nn 21 1? {2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} 1 2 3 1 1 1 1 3 2 2 2 3 3 2 3 60 ? 同樣 3 個(gè)數(shù)據(jù) { 1, 2, 3 }，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。 ? 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。 ? 用樹的搜索效率來評價(jià)這些二叉搜索樹。 ? 為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。 ? 這樣的判定樹即為 擴(kuò)充的二叉搜索樹 。 61 ? 舉例說明。已知關(guān)鍵碼集合 {a1, a2, a3} = {do, if, to}，對應(yīng)搜索概率 p1, p2, p3, 在各搜索不成功間隔內(nèi)搜索概率分別為 q0, q1, q2, q3?？赡艿亩嫠阉鳂淙缦滤?。 do if to do if to q0 q1 p1 q2 p2 q3 p3 q0 q1 q2 q3 p1 p2 p3 (a) (b)