【文章內(nèi)容簡(jiǎn)介】 ↑ ② 表空測(cè)試 ， 非空； mid=5 ③ 得到中點(diǎn) ， 比較測(cè)試為 a情形 ↑↑ low=4 high=4 high=mid1， 調(diào)整到左半?yún)^(qū) ──────────────────────────── ↑ ② 表空測(cè)試 ， 非空； mid=4 ③ 得到中點(diǎn) ， 比較測(cè)試為 b情形 ↑ ↑ high=4 low=5 low=mid+1， 調(diào)整到右半?yún)^(qū) ──────────────────────────── ② 表空測(cè)試 ， 為空；查找失敗 ， 返回查找失敗信息為 0 ──────────────────────────── 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 27 【 算法 】 int Binary_Search(S_TBL tbl， KEY kx) { /* 在表 tbl中查找關(guān)鍵碼為 kx的數(shù)據(jù)元素 ， 若找到返回該元素在表中的位置 ， 否則 ，返回 0 */ int mid， flag=0； low=1； high=length； /* ① 設(shè)置初始區(qū)間 */ while(low=high) /* ② 表空測(cè)試 */ { /* 非空 ， 進(jìn)行比較測(cè)試 */ mid=(low+high)/2； /* ③ 得到中點(diǎn) */ if (kx[mid].key) high=mid1； /* 調(diào)整到左半?yún)^(qū) */ else if(kx[mid].key) low=mid+1； /* 調(diào)整到右半?yún)^(qū) */ else { flag=mid； break； } /* 查找成功 ， 元素位置設(shè)置到 flag中 */ } return flag。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 28 【 性能分析 】 從折半查找過程看 ， 以表的中點(diǎn)為比較對(duì)象 ， 并以中點(diǎn)將表分割為兩個(gè)子表 ， 對(duì)定位到的子表繼續(xù)這種操作 。 所以 ，對(duì)表中每個(gè)數(shù)據(jù)元素的查找過程 ， 可用二叉樹來描述 ， 稱這個(gè)描述查找過程的二叉樹為判定樹 。 49 38 29 18 7 42 52 31 23 46 35 14 21 圖 例 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 29 可以看到 ， 查找表中任一元素的過程 ， 即是判定樹中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵碼的比較次數(shù) ，也即該元素結(jié)點(diǎn)在樹中的層次數(shù) 。 對(duì)于 n個(gè)結(jié)點(diǎn)的判定樹 ，樹高為 k， 則有 2k11n≤2k1， 即 k1log2(n+1)≤k， 所以k= 。 因此 ， 折半查找在查找成功時(shí) ， 所進(jìn)行的關(guān)鍵碼比較次數(shù)至多為 。 接下來討論折半查找的平均查找長(zhǎng)度 。 為便于討論 ，以樹高為 k的滿二叉樹 (n=2k1)為例 。 假設(shè)表中每個(gè)元素的查找是等概率的 ， 則樹的第 i層有 2i1個(gè)結(jié)點(diǎn) ， 因此 ， 折半查找的平均查找長(zhǎng)度為： ? ?)1(lo g 2 ?n2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 30 ASL= PiC i n ∑ i=1 =(1/n)[1 20+2 21+… ＋ k 2k1] =((n+1)/n) log2(n+1)1≈ log2(n+1)1 所以 ， 折半查找的時(shí)間效率為 O(log2n)。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 31 動(dòng)態(tài)查找表 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 32 一 .二叉排序樹定義 二叉排序樹 （ Binary Sort Tree） 或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： ⑴ 若左子樹不空 ， 則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹不空 ， 則 右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值 。 ⑵ 左右子樹也都是二叉排序樹 。 二叉排序樹 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 33 由圖 中 可以看出 ， 對(duì)二叉排序樹進(jìn)行中序遍歷 ， 便可得到一個(gè)按關(guān)鍵碼有序的序列 ， 因此 ，一個(gè)無序序列 ， 可通過構(gòu)一棵二叉排序樹而成為有序序列 。 58 42 98 70 90 63 45 55 83 67 10 二 .二叉排序樹查找過程 從其定義可見 ， 二叉排序樹的查找過程為： ① 若查找樹為空 ， 查找失敗 。 ② 查找樹非空 ， 將給定值 kx與查找樹的根結(jié)點(diǎn)關(guān)鍵碼比較 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 34 ③ 若相等 ， 查找成功 ， 結(jié)束查找過程 ， 否則 ， a． 當(dāng)給 kx小于根結(jié)點(diǎn)關(guān)鍵碼 ， 查找將在以左子女為根的子樹上繼續(xù)進(jìn)行 ， 轉(zhuǎn) ① b． 當(dāng)給 kx大于根結(jié)點(diǎn)關(guān)鍵碼 ， 查找將在以右子女為根的子樹上繼續(xù)進(jìn)行 ， 轉(zhuǎn) ① 以二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu) ， 則查找過程算法程序描述如下： typedef struct NODE { ElemType elem。 /*數(shù)據(jù)元素字段 */ struct NODE *lc,*rc。 /*左 、 右指針字段 */ }NodeType。 /*二叉樹結(jié)點(diǎn)類型 */ 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 35 【 算法 】 Int SearchElem(NodeType *t,NodeType *p,NodeType *q,KeyType kx) { /*在二叉排序樹 t上查找關(guān)鍵碼為 kx的元素 ， 若找到 ， 返回 1， 且 q指向該結(jié)點(diǎn) ，p指向其父結(jié)點(diǎn)；否則 ， 返回 0， 且 p指向查找失敗的最后一個(gè)結(jié)點(diǎn) */ int flag=0。 *q=t。 while(*q) /*從根結(jié)點(diǎn)開始查找 */ if(kx(*q)) /*kx大于當(dāng)前結(jié)點(diǎn) *q的元素關(guān)鍵碼 */ { *p=*q。*q=(*q)rc。}/*將當(dāng)前結(jié)點(diǎn) *q的右子女置為新根 */ else if(kx(*q)) /*kx小于當(dāng)前結(jié)點(diǎn) *q的關(guān)鍵碼 */ {*p=*q。*q=(*q)lc。} /*將當(dāng)前結(jié)點(diǎn) *q的左子女置為新根 */ else {flag=1。break。} /*查找成功 ， 返回 */ return flag。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 36 三 .二叉排序樹插入操作和構(gòu)造一棵二叉排序樹 先討論向二叉排序樹中插入一個(gè)結(jié)點(diǎn)的過程：設(shè)待插入結(jié)點(diǎn)的關(guān)鍵碼為 kx， 為將其插入 ， 先要在二叉排序樹中進(jìn)行查找 ， 若查找成功 ， 按二叉排序樹定義 ， 待插入結(jié)點(diǎn)已存在 ， 不用插入；查找不成功時(shí) ， 則插入之 。 因此 ， 新插入結(jié)點(diǎn)一定是作為葉子結(jié)點(diǎn)添加上去的 。 構(gòu)造一棵二叉排序樹則是逐個(gè)插入結(jié)點(diǎn)的過程 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 37 【 算法 】 int InsertNode (NodeType *t,KeyType kx) { /*在二叉排序樹 *t上插入關(guān)鍵碼為 kx的結(jié)點(diǎn) */ NodeType *p=t,*q,*s。 int flag=0。 if (!SearchElem(t,amp。p,amp。q,kx))。 /*在 *t為根的子樹上查找 */ { s=(NodeType *)malloc(sizeof(NodeType))。 /*申請(qǐng)結(jié)點(diǎn) ， 并賦值 */ s=kx。 slc=NULL。 src=NULL。 flag=1。 /*設(shè)置插入成功標(biāo)志 */ if (!p) t=s。 /*向空樹中插入時(shí) */ else if (kxp) prc=s。 /*插入結(jié)點(diǎn)為 p的右子女 */ else plc=s。 /*插入結(jié)點(diǎn)為 p的左子女 */ } return flag。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 38 【 例