【正文】 insert_btree_onenode(k,prchild else insert_btree_onenode(k,plchild }}typedef struct node{ int data。} BSTNODE插入算法：void insert_btree_onenode(KEYTYPE k, BSTNODE *p){ if(p == NULL) // 如果二叉排序樹空 {p = malloc(sizeof(BSTNODE))。}ASL 最大 最小 兩者之間表結(jié)構(gòu) 有序表、無(wú)序表 有序表 分塊有序表存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)線性鏈表查找方法比較順序查找 折半查找 分塊查找　動(dòng)態(tài)查找表　　　 動(dòng)態(tài)查找表的特點(diǎn)：表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成的，即對(duì)給定值 key，若表中存在則查找成功，否則插入關(guān)鍵字等于 key的記錄 ．定義：二叉排序樹或是一棵空樹，或 是具有下列性質(zhì)的二叉樹 ：–若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值–若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值–它的左、右子樹也分別為二叉排序樹 二叉排序樹生成和插入二叉排序樹的插入：–插入原則： 若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，繼續(xù)在其左、右子樹上查找，直至某個(gè)葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子–二叉排序樹生成 ：從空樹出發(fā)，經(jīng)過(guò)一系列的查找、插入操作之后，可生成一棵二叉排序樹? 插入算法例 {10， 18， 3， 8， 12， 2， 7， 3}10 101810183101838101838 12101838 122101838 1227101838 12273中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列數(shù)據(jù)結(jié)點(diǎn)類型：define KEYTYPE int。(r[j].key=nd[i].key)) j++。 while((jn)amp。(i=b) i++。}JD。 int 　 link。 ［ 0］ .key = k。 int len。第八章 查找 基本概念 靜態(tài)查找表 動(dòng)態(tài)查找表 哈希表 ? 查找 —— 也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素? 關(guān)鍵字 —— 是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素? 查找方法評(píng)價(jià)– 查找速度– 占用存儲(chǔ)空間多少– 算法本身復(fù)雜程度– 平均查找長(zhǎng)度 ASL(Average Search Length)： 為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值叫查找算法的 ~ 順序表的查找 查找過(guò)程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 18 21 37 56 64 75 80 88 92找 6464監(jiān)視哨i i i i比較次數(shù) =5比較次數(shù)：查找第 n個(gè)元素： 1查找第 n1個(gè)元素： 2……….查找第 1個(gè)元素： n查找第 i個(gè)元素： n+1i查找失敗 ： n+1define MAXSIZE 100define KEYTYPE inttypedef struct{KEYTYPE key。typedef struct{ SSELEMENT r［ MAXSIZE］ 。 j = 。}順序查找算法：?順序查找方法的 ASL? 查找過(guò)程 ： 每次將待查記錄所在區(qū)間縮小一半? 適用條件 ：采用順序存儲(chǔ)結(jié)構(gòu)的 有序 表? 算法實(shí)現(xiàn) :– 設(shè)表長(zhǎng)為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn) ,k為給定值– 初始時(shí)，令 low=1,high=n,mid=?(low+high)/2?– 讓 k與 mid指向的記錄比較? 若 k==r[mid].key， 查找成功? 若 kr[mid].key， 則 high=mid1? 若 kr[mid].key， 則 low=mid+1– 重復(fù)上述操作，直至 lowhigh時(shí)，查找失敗 有序表查找（折半查找）? 算法描述：low highmid例 1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92找 211 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid例 1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid找 701 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhigh1185210741936判定樹：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法評(píng)價(jià) :判定樹：描述查找過(guò)程的二叉樹叫 ~有 n個(gè)結(jié)點(diǎn)的判定樹的深度為 ?log2n?+1折半查找法在查找過(guò)程中進(jìn)行的比較次數(shù)最多不超過(guò)其判定樹的深度折半查找的 ASL： 索引順序表查找（分塊查找）– 查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找– 適用條件：分塊有序表– 算法實(shí)現(xiàn)?用數(shù)組存放待查記錄 ,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域?建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針1 2 3 4 5 6 7 8 8 10 11 12 13 14 15 16 17 1822 12 13 8 8 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查 38–算法描述 :typedef struct{ int 　 key。 float 　 info。amp。 } j=nd[i].link。amp。 } return(j)。 // 結(jié)點(diǎn)的其余數(shù)據(jù)部分struct node *lchild, *rchild。 pkey = k。JD *insertbst(JD *r,int x){ JD *p,*q,*s。 q=NULL。 while(p!=NULL) { q=p。 else qrchild=s。 if(plchild==NULL) s=prchild。 while(srchild!=NULL) { q=s。 else qrchild=slchild。 else if(flchild==p) flchild=s。}查找性能的分析： 對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長(zhǎng)度的定義來(lái)求它的ASL值，顯然，由值相同的 n個(gè)關(guān)鍵字構(gòu)造所得的，不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng)度的值不同，甚至可能差別很大例如： 由關(guān)鍵字序列 1， 2， 3， 4， 5構(gòu)造而得的二叉排序樹 ASL =（ 1+2+3+4+5） / 5 = 3 由關(guān)鍵字序列 3， 1， 2， 5， 4構(gòu)造而得的二叉排序樹 ASL =（ 1+2+3+2+3） / 5 = 一般情況下，考慮含有 n個(gè)關(guān)鍵字可能出現(xiàn)的 n!種序列出現(xiàn)的可能性相等。 DGEDABCFEGBAC F? 平衡因子（平衡度）： 結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度。 插入之后仍應(yīng)保持平衡二叉排序樹的性質(zhì)不變。?新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（如左圖結(jié)點(diǎn) ）即可。 插入之后仍應(yīng)保持平衡二叉排序樹的性質(zhì)不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)關(guān)鍵：將導(dǎo)致出現(xiàn) 危機(jī)結(jié)點(diǎn)的情況 全部分析清除，就可以使得平衡二叉排序樹的性質(zhì)保持不變??！149325 2863536050