【正文】 i = 1/n, i = 1, 2, ? , n。搜索成功的平均搜索程度為： ? 在搜索不成功情形， ASLunsucc = n+1。 .)()(1????????? nis u c cnnnninA S L 0 212111121 ? 采用遞歸方法搜索值為 x 的元素，每遞歸一層就向待查元素逼近一個位置，直到到達(dá)該元素。假設(shè)待查元素在第 i（ 1≤i≤n）個位置，則算法遞歸深度達(dá) i（ 1～ i）。 10 20 30 40 50 60 i = 1 搜索 30 10 20 30 40 50 60 i = 2 10 20 30 40 50 60 i = 3 遞 歸 順序搜索的遞歸算法 22 順序搜索的遞歸算法 template class E, class K int dataListE, K:: SeqSearch (const K x, int loc) const { //在數(shù)據(jù)表 Element[1..n] 中搜索其關(guān)鍵碼與給定值 //匹配的對象 , 函數(shù)返回其表中位置。參數(shù) loc 是在 //表中開始搜索位置 if (loc CurrentSize) return 0。 //搜索失敗 else if (Element[loc1].key == x) return loc。 //搜索成功 else return Search (x, loc+1)。 //遞歸搜索 }。 23 二叉搜索樹 ( Binary Search Tree ) ? 定義 二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： ? 每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼 (key)，所有結(jié)點的關(guān)鍵碼互不相同。 ? 左子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼。 ? 右子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。 ? 左子樹和右子樹也是二叉搜索樹。 24 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結(jié)點左子樹上所有關(guān)鍵碼小于結(jié)點關(guān)鍵碼； ? 右子樹上所有關(guān)鍵碼大于結(jié)點關(guān)鍵碼； ? 注意：若從根結(jié)點到某個葉結(jié)點有一條路徑，路徑左邊的結(jié)點的關(guān)鍵碼不一定小于路徑上的結(jié)點的關(guān)鍵碼。 25 ? 如果對一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。 ? 二叉搜索樹的類定義 include include template class E, class K struct BSTNode { //二叉樹結(jié)點類 E data。 //數(shù)據(jù)域 BSTNodeE, K *left, *right。 //左子女和右子女 26 BSTNode() { left = NULL。 right = NULL。 } //構(gòu)造函數(shù) BSTNode (const E d, BSTNodeE, K *L = NULL, BSTNodeE, K *R = NULL) { data = d。 left = L。 right = R。} //構(gòu)造函數(shù) ～ BSTNode() {} //析構(gòu)函數(shù) void setData (E d) { data = d。 } //修改 E getData() { return data。 } //提取 bool operator (const Eamp。 x) //重載：判小于 { return 。 } 27 bool operator (const Eamp。 x) //重載：判大于 { return 。 } bool operator == (const Eamp。 x) //重載：判等于 { return == 。 } }。 template class E, class K class BST { //二叉搜索樹類定義 public: BST() { root = NULL。 } //構(gòu)造函數(shù) BST(K value)。 //構(gòu)造函數(shù) ～ BST() {}。 //析構(gòu)函數(shù) 28 bool Search (const K x) const //搜索 { return Search(x,root) != NULL。 } BSTE, Kamp。 operator = (const BSTE, Kamp。 R)。 //重載：賦值 void makeEmpty() //置空 { makeEmpty (root)。 root = NULL。} void PrintTree() const { PrintTree (root)。 } //輸出 E Min() { return Min(root)data。 } //求最小 E Max() { return Max(root)data。 } //求最大 bool Insert (const Eamp。 e1) //插入新元素 { return Insert(e1, root)。} 29 bool Remove (const K x) { return Remove(x, root)。} //刪除含 x的結(jié)點 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)。 30 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)。 //遞歸：刪除 }。 ? 二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。 31 二叉搜索樹的搜索算法 ? 在二叉搜索樹上進(jìn)行搜索，是一個 從根結(jié)點開始 ， 沿某一個分支逐層向下 進(jìn)行比較判等的過程。它可以是一個遞歸的過程。 ? 假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x 的元素，搜索過程從根結(jié)點開始。 ? 如果 根指針為 NULL，則 搜索不成功 ；否則用給定值 x 與根結(jié)點的關(guān)鍵碼進(jìn)行比較： ?若 給定值等于根結(jié)點關(guān)鍵碼 ，則 搜索成功 ，返回搜索成功信息并報告搜索到結(jié)點地址。 32 ? 若給定值小于根結(jié)點的關(guān)鍵碼 ， 則繼續(xù)遞歸搜索根結(jié)點的左子樹； ? 否則 。 遞歸搜索根結(jié)點的右子樹 。 搜索 45 搜索成功 搜索 28 搜索失敗 35 15 45 50 40 25 10 20 30 33 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //私有遞歸函數(shù)：在以 ptr為根的二叉搜索樹中搜 //索含 x的結(jié)點。若找到，則函數(shù)返回該結(jié)點的 //地址，否則函數(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。 //搜索成功 }。 34 templateclass E, class K BSTNodeE, K* BSTE, K:: Search (const K x, BSTNodeE, K *ptr) { //非遞歸函數(shù)：作為對比，在當(dāng)前以 ptr為根的二 //叉搜索樹中搜索含 x的結(jié)點。若找到，則函數(shù)返 //回該結(jié)點的地址，否則函數(shù)返回 NULL值。 if (ptr == NULL) return NULL。 BSTNodeE, K* temp = ptr。 while (temp != NULL) { if (x == tempdata) return temp。 if (x tempdata) temp = templeft。 35 else temp = tempright。 } return NULL。 }。 ? 搜索過程是從根結(jié)點開始，沿某條路徑自上而下逐層比較判等的過程。 ? 搜索成功，搜索指針將停留在樹上某個結(jié)點；搜索不成功，搜索指針將走到樹上某個結(jié)點的空子樹。 ? 設(shè)樹的高度為 h，最多比較次數(shù)不超過 h。 36 二叉搜索樹的插入算法 ? 為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在 。 ? 在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。 ? 如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入； ? 如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。 37 35 15 45 50 40 25 10 20 30 28 插入新結(jié)點 28 二叉搜索樹的插入 ? 每次結(jié)點的插入，都要從根結(jié)點出發(fā)搜索插入位置，然后把新結(jié)點作為葉結(jié)點插入。 38 二叉搜索樹的插入算法 template class E, class K bool BSTE, K::Insert (const Eamp。 e1, BSTNodeE, K *amp。 ptr) { //私有函數(shù)：在以 ptr為根的二叉搜索樹中插入值為 //e1的結(jié)點。若在樹中已有含 e1的結(jié)點則不插入 if (ptr == NULL) { //新結(jié)點作為葉結(jié)點插入 ptr = new BstNodeE, K(e1)。 //創(chuàng)建新結(jié)點 if (ptr == NULL) { cerr Out of space endl。 exit(1)。 } return true。 39 } else if (e1 ptrdata) Insert (e1, ptrleft)。 //左子樹插入 else if (e1 ptrdata) Insert (e1, ptrright)。 //右子樹插入 else return false。 //x已在樹中 ,不再插入 }。 ? 注意參數(shù)表中引用型指針參數(shù) ptr的使用。 ? 利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。 40 輸入數(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 41 template class E, class K BS