BST舉例存儲結(jié)構(gòu)typedefstructnodeKeyTypekeyInfoType

1、BST舉例存儲結(jié)構(gòu)typedefstructnodeKeyTypekeyInfoType9.1 根本概念效率：與存儲構(gòu)造、文件狀態(tài)有序、無序有關(guān) 平均查找長度(ASL)，即平均的比較次數(shù)，作為衡量查找效率的標(biāo)準(zhǔn)： Pi：查找第i個結(jié)點(diǎn)的概率 Ci：查找第i個結(jié)點(diǎn)的比較次數(shù) 設(shè)Pi1/n, 1in約定：typedef int KeyType; 2 9.2 線性表的查找對象：用線性表作為表的組織形式。分類：靜態(tài)查找、內(nèi)部查找方式：順序查找、二分查找、分塊查找 define n 100/ 9.2.1 順序查找根本思想 從表的一端開場，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)的Key與給定值K進(jìn)展比較，假設(shè)

2、當(dāng)前掃描到結(jié)點(diǎn)KeyK，那么查找成功返回；假設(shè)掃描完好個表后，仍未找到，那么查找失敗。適用范圍：順序表、鏈表算法：39.2.1 順序查找 typedef struct KeyType key; InfoType otherinfo; /應(yīng)用相關(guān) NodeType, SeqListn+1; /0號單元作為哨兵 int SeqSearch( SeqList R, KeyType K) /在R1.n中查找，成功時返回結(jié)點(diǎn)位置，失敗時返回0 int n; R0.key=K; /設(shè)置哨兵 for ( i=n; Ri.key != K; i- ); /從后往前找 return i; /假設(shè)i為0，那么失敗

3、 4 9.2.1 順序查找 哨兵的作用 for中省略了下標(biāo)越界i=1斷定,節(jié)約了約一半時間時間分析 成功：ASLss=(n+1)/2，key的平均比較次數(shù)約為表長的一半 失敗：n+1次比較優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：簡單，對存儲構(gòu)造、Key之間的關(guān)系均無特殊要求 缺點(diǎn)：效率低，當(dāng)n較大時不宜用5 9.2.2 二分折半查找適用范圍：順序表、有序根本思想分治法 1設(shè)Rlow.high 是當(dāng)前查找區(qū)間，首先確定該區(qū)間的中點(diǎn) 位置：mid= (low+high)/2 /整除 2將待查的K值與Rmid比較， KRmid.key：查找成功，返回位置mid KRmid.key：那么左子表Rlow.mid-1是新的查找區(qū)間

4、 KRmid,key：那么右子表Rmid+1.high是新的查找區(qū)間 初始的查找區(qū)間是R1.n，每次查找比較K和中間點(diǎn)元素，假設(shè)查找成功那么返回；否那么當(dāng)前查找區(qū)間縮小一半，直至當(dāng)前查找區(qū)間為空時查找失敗。6 9.2.2 二分折半查找算法： int BinSearch( SeqList R, KeyType K ) int mid, low=1, high=n; while ( low key ) return T; /假設(shè)T為空，查找失??；否那么成功 if ( key key ) return SearchBST ( T-lchild, key ); /查找左子樹 else return S

5、earchBST ( T-rchild, key ); /查找右子樹 537294根本思想 從根結(jié)點(diǎn)開場比較，假設(shè)當(dāng)前結(jié)點(diǎn)的key與待查的key相等，那么查找成功，返回該結(jié)點(diǎn)的指針；否那么在左子樹或右子樹中繼續(xù)查找。假設(shè)樹中沒有待查結(jié)點(diǎn)，那么失敗于某個空指針上。15 9.3.1 二叉查找樹BST1.查找續(xù)時間 假設(shè)成功，那么走了一條從根到待查節(jié)點(diǎn)的途徑 假設(shè)失敗，那么走了一條從根到葉子的途徑？不一定上界：O(h)分析：與樹高相關(guān) 最壞情況：單支樹，ASL=(n+1)/2,與順序查找一樣 最好情況：ASLlgn，形態(tài)與折半查找的斷定樹相似 平均情況：假定n個keys所形成的n!種排列是等概率的，

6、那么可證明由這n!個序列產(chǎn)生的n!棵BST其中有的形態(tài)一樣的平均高度為O(lgn)，故查找時間仍為O(lgn)537294162、BST的插入和生成插入算法思想 保證新結(jié)點(diǎn)插入后滿足BST性質(zhì)，根本思想如下：假設(shè)T為空，那么為待插入的Key申請一個新結(jié)點(diǎn)，并令其為根；否那么，從根開場向下查找插入位置，直到發(fā)現(xiàn)樹中已有Key，或找到一個空指針為止；將新結(jié)點(diǎn)作為葉子插入空指針的位置。 查找過程是一個關(guān)鍵字的比較過程，易于寫出遞歸或非遞歸算法，也可以調(diào)用查找操作。 算法實(shí)現(xiàn)17void InsertBST( BSTree *T, KeyType key ) /*T是根 BSTNode *f, *p=

7、*T; /p指向根結(jié)點(diǎn) while( p ) /當(dāng)樹非空時，查找插入位置if ( p-key=key ) return; /樹中已有key，不允許重復(fù)插入fp；/ f和p為父子關(guān)系， 循環(huán)不變量：*parent為*p的雙親p( key key ) ? p-lchild; p-rchild; /注意：樹為空時，無須查找p = (BSTNode *) malloc(sizeof(BSTNode);p-key=key; p-lchild=p-rchild=NULL; /生成新結(jié)點(diǎn)if ( *T =NULL ) * T=p; /原樹為空,新結(jié)點(diǎn)為根else /原樹非空, 新結(jié)點(diǎn)作為*f的左或右孩子插入

8、 if ( key key ) f-lchild=p; else f-rchild=p; /時間為Oh182、BST的插入和生成生成算法： 從空樹開場，每輸入一個數(shù)據(jù)就調(diào)用一次插入算法。 BSTree CreateBST( void ) BSTree TNULL; /初始時T為空 KeyType key; scanf( “%d, &key ); while( key ) /假設(shè)key0表示輸入完畢 InsertBST ( &T, key ) ; /將key插入樹T中 scanf( “%d, &key )；/ 讀入下一個關(guān)鍵字 return T；/ 返回根指針 192、BST的插入和生成舉例10

9、10181018310183810183812101838122101838122710183812273輸入實(shí)例 10， 18， 3， 8， 12， 2， 7， 3202、BST的插入和生成一般情況 不同的輸入實(shí)例數(shù)據(jù)集不同、或排列不同，生成的樹的形態(tài)一般不同。對n個結(jié)點(diǎn)的同一數(shù)據(jù)集，可生成n！棵BST。例外情況 但有時不同的實(shí)例可能生成一樣的BST，例如：2，3，7，8，5，4和2，3，7，5，8，4可構(gòu)造同一棵BST。排序樹名稱的由來 因?yàn)锽ST的中序序列有序，所以對任意關(guān)鍵字序列，構(gòu)造BST的過程，實(shí)際上是對其排序。 生成n個結(jié)點(diǎn)的BST的平均時間是O(nlgn), 但它約為堆排序的2

10、3倍，因此它并不適宜排序。 213、BST的刪除 保證刪一結(jié)點(diǎn)不能將以該結(jié)點(diǎn)為根的子樹刪去，且仍須滿足BST性質(zhì)。即：刪一結(jié)點(diǎn)相當(dāng)于刪有序序列中的一個結(jié)點(diǎn)。根本思想查找待刪結(jié)點(diǎn)*p，令parent指向其雙親初值NULL；假設(shè)找不到那么返回，否那么進(jìn)入下一步。在刪除*p時處理其子樹的連接問題，同時保持BST性質(zhì)不變。 case1:*p是葉子，無須連接子樹，只需將*parent中指向*p的指針置空 case2:*p只有1個孩子，只須連接唯一的1棵子樹，故可令此孩子取代*p與 其雙親連接4種狀態(tài) parentpchildchildparentpparentpchildparentpchild *p只

11、有左孩子 *p只有右孩子22case3: *p有2個孩子，有2種處理方式找到*p 的中序后繼(或前驅(qū))*s，用*p的右(或左)子樹取代*p與其雙親*parent連接； 而*p的左(或右)子樹PL那么作為*s的左(或右)子樹與*s連接。缺點(diǎn)：樹高可能增大。PLsRsprparentPLsRpparentspr23 令q=p，找*q的中序后繼*p，并令parent指向*p的雙親，將*p的右子樹取代*p與其雙親*parent連接。將*p的內(nèi)容copy到*q中，相當(dāng)于刪去了*q，將刪*q的操作轉(zhuǎn)換為刪*p的操作。對稱地，也可找*q的中序前驅(qū) 因?yàn)?p最多只有1棵非空的子樹，屬于case2。實(shí)際上cas

12、e1也是case2的特例。因此，case3采用該方式時，3種情況可以統(tǒng)一處理為case2。q=pparentpchildq=ppchild*q的中序后繼就是其右孩子243、BST的刪除算法void DelBSTNode( BSTree *T, KeyType key) /*T是根BSTree *q, *child, *parent=NULL, *p=*T;while ( p ) /找待刪結(jié)點(diǎn) if ( p-key =key ) break; /已找到 parent=p; /循環(huán)不變式是*parent為*p的雙親 p( key key ) ? p-lchild; p-rchild;if ( !p

13、 ) return; /找不到被刪結(jié)點(diǎn)，返回q=p; /q記住被刪結(jié)點(diǎn)*pif (q-lchild & q-rchild ) /case3，找*q的中序后繼 for(parent=q,p=q-rchild; p-lchild; parent=p, p=p-lchild);25 /如今3種情況已統(tǒng)一到情況2，被刪結(jié)點(diǎn)*p最多只有1個非空的孩子child=(p-lchild)？p-lchild; p-rchild; /令child指向*p非空的孩子，僅case1時child為空If ( !parent ) /*p的雙親為空，說明 *p是根，即刪根結(jié)點(diǎn) *T=child; /假設(shè)是情況1，那么樹為空；否那么*child取代*p成為根else /*p非根，它的孩子取代它與*p的雙親連接，即刪 *p if ( p=parent-lchild ) parent-lchild=child; else parent-rchild=child; if ( p != q ) /情況3，將*p的數(shù)據(jù)copy到*q中 q-key=p-key; /假設(shè)有其