中法122班徐彤坤--實(shí)驗(yàn)五

1、 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)五查找算法實(shí)現(xiàn) 姓名：徐彤坤 學(xué)號(hào)：122930 班級(jí)：中法計(jì)122班【實(shí)驗(yàn)?zāi)康摹渴炀氄莆枕樞虿檎?、折半查找及二叉排序?shù)、平衡二叉樹(shù)上的查找、插入和刪除的方法，比較它們的平均查找長(zhǎng)度。【問(wèn)題描述】查找表是數(shù)據(jù)處理的重要操作， 試建立有100個(gè)結(jié)點(diǎn)的二叉排序樹(shù)進(jìn)行查找，然后用原數(shù)據(jù)建立AVL樹(shù)， 并比較兩者的平均查找長(zhǎng)度?！净疽蟆浚?） 以鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉排序樹(shù)的建立、查找和刪除。（2） 根據(jù)給定的數(shù)據(jù)建立平衡二叉樹(shù)。（3） 比較二叉排序樹(shù)和平衡二叉樹(shù)的平均查找長(zhǎng)度?！緶y(cè)試數(shù)據(jù)】隨機(jī)生成?！緦?shí)現(xiàn)提示】（1） 初始，二叉排序樹(shù)和平衡二叉樹(shù)都為空樹(shù)，操作界面給出查找、插入

2、和刪除三種操作供選擇。每種操作均要提示輸入關(guān)鍵字。每次插入或刪除一個(gè)結(jié)點(diǎn)后，應(yīng)更新平衡二叉樹(shù)或二叉排序樹(shù)的顯示。（2） 平衡二叉樹(shù)或二叉排序樹(shù)的顯示可以采用凹入表形式，也可以采用圖形界面畫(huà)出樹(shù)形?！舅惴ㄋ枷搿慷鏄?shù)的定義：二叉排序樹(shù)或者是一顆空樹(shù)，或者是一顆具有如下特性的二叉樹(shù)：1. 每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key），所有結(jié)點(diǎn)的關(guān)鍵碼互不相同；2. 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值；3. 若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值；4. 左右子樹(shù)本身又各是一棵二叉排序樹(shù)；【程序主要部分】1.插入新結(jié)點(diǎn)int InsertAVL(BSTree

3、&T,ElemType e,bool &taller) if(!T) T=(BSTree)malloc(sizeof(BSTnode); T->data=e; T->lchild=T->rchild=NULL; T->bf=0; taller=true; 2. void Leftbalance_div(BSTree &p,int &shorter)p結(jié)點(diǎn)的左子樹(shù)高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)變矮；p結(jié)點(diǎn)左、右子樹(shù)等高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)高不變p1指向p的右子樹(shù)，p1結(jié)點(diǎn)左、右子樹(shù)等高,刪除結(jié)點(diǎn)后p的bf為-2,進(jìn)行左旋處理，樹(shù)高不

4、變p1的右子樹(shù)高，左旋處理后，樹(shù)變矮3. ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter)if(LT(key.key,p->data.key) )/在p的左子樹(shù)中進(jìn)行刪除if(LQ(key.key,p->data.key) )/在p的右子樹(shù)中進(jìn)行刪除【程序源碼】#include<iostream>#include<stdlib.h>#include<string.h>#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#de

5、fine LQ(a,b) (a)>(b)using namespace std;typedef int Keytype;typedef struct Keytype key; /關(guān)鍵字域ElemType;typedef struct BSTnode ElemType data; int bf;struct BSTnode *lchild,*rchild;BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p)BSTnode *lc; lc=p->lchild; p->lc

6、hild=lc->rchild; lc->rchild=p; p=lc;void L_Rotate(BSTree &p)BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc;void Leftbalance(BSTree &T)BSTnode *lc,*rd; lc=T->lchild; switch(lc->bf) case +1: T->bf=lc->bf=0; R_Rotate(T); break; case -1: rd=lc-&

7、gt;rchild; switch(rd->bf) case 1: T->bf=-1; lc->bf=0; break; case 0: T->bf=lc->bf=0; break; case -1: T->bf=0; lc->bf=1; break; rd->bf=0; L_Rotate(T->lchild); R_Rotate(T); void Rbalance(BSTree &T)BSTnode *lc,*ld; lc=T->rchild; switch(lc->bf) case 1: ld=lc->lchi

8、ld; switch(ld->bf) case 1: T->bf=0; lc->bf=-1; break; case 0: T->bf=lc->bf=0; break; case -1: T->bf=1; lc->bf=0; break; ld->bf=0; R_Rotate(T->rchild); L_Rotate(T); case -1: T->bf=lc->bf=0; L_Rotate(T); break; int InsertAVL(BSTree &T,ElemType e,bool &taller) i

9、f(!T) T=(BSTree)malloc(sizeof(BSTnode); T->data=e; T->lchild=T->rchild=NULL; T->bf=0; taller=true; else if(EQ(e.key,T->data.key) taller=false; cout<<"結(jié)點(diǎn) "<<e.key<<" 不存在。"<<endl; return 0; if(LT(e.key,T->data.key) if(!InsertAVL(T->lchil

10、d,e,taller) return 0; if(taller) switch(T->bf) case 1: Leftbalance(T); taller=false; break; case 0: T->bf=+1; taller=true; break; case -1: T->bf=0; taller=false; break; else if(!InsertAVL(T->rchild,e,taller) return 0; if(taller) switch(T->bf) case 1: T->bf=0; taller=false; break; c

11、ase 0: T->bf=-1; taller=true; break; case -1: Rbalance(T); taller=false; break; return 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T) p=f; cout<<"結(jié)點(diǎn)不存在。"<<endl; return false; else if( EQ(key.key,T->data.key) ) p=T; cout<<"查找成功，存在結(jié)點(diǎn)"

12、cout<<p->data.key<<endl; return true; else if(LT(key.key,T->data.key) return SearchBST(T->lchild,key,T,p); else return SearchBST(T->rchild,key,T,p);void Leftbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p->bf=+1) /p結(jié)點(diǎn)的左子樹(shù)高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)變矮 p->bf=0; shorter

13、=1; else if(p->bf=0)/p結(jié)點(diǎn)左、右子樹(shù)等高，刪除結(jié)點(diǎn)后p的bf減1,樹(shù)高不變 p->bf=-1; shorter=0; else p1=p->rchild;/p1指向p的右子樹(shù) if(p1->bf=0)/p1結(jié)點(diǎn)左、右子樹(shù)等高,刪除結(jié)點(diǎn)后p的bf為-2,進(jìn)行左旋處理，樹(shù)高不變 L_Rotate(p); p1->bf=1; p->bf=-1; shorter=0; else if(p1->bf=-1)/p1的右子樹(shù)高，左旋處理后，樹(shù)變矮 L_Rotate(p); p1->bf=p->bf=0; shorter=1; els

14、e p2=p1->lchild; p1->lchild=p2->rchild; p2->rchild=p1; p->rchild=p2->lchild; p2->lchild=p; if(p2->bf=0) p->bf=0; p1->bf=0; else if(p2->bf=-1) p->bf=+1; p1->bf=0; else p->bf=0; p1->bf=-1; p2->bf=0; p=p2; shorter=1; void Rbalance_div(BSTree &p,int &a

15、mp;shorter) BSTree p1,p2; if(p->bf=-1) p->bf=0; shorter=1; else if(p->bf=0) p->bf=+1; shorter=0; else p1=p->lchild; if(p1->bf=0) R_Rotate(p); p1->bf=-1; p->bf=+1; shorter=0; else if(p1->bf=+1) R_Rotate(p); p1->bf=p->bf=0; shorter=1; else p2=p1->rchild; p1->rchi

16、ld=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; p2->rchild=p; if(p2->bf=0) p->bf=0; p1->bf=0; else if(p2->bf=1) p->bf=-1; p1->bf=0; else p->bf=0; p1->bf=1; p2->bf=0; p=p2; shorter=1; void Delete(BSTree q,BSTree &r,int &shorter) if(r->rchild=NU

17、LL) q->data=r->data; q=r; r=r->lchild; free(q); shorter=1; else Delete(q,r->rchild,shorter); if(shorter=1) Rbalance_div(r,shorter); ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) ElemType k,a,b; a.key=1; b.key=0; BSTree q; if(p=NULL) cout<<"結(jié)點(diǎn)不存在。"<<

18、;endl; return b; else if(LT(key.key,p->data.key) )/在p的左子樹(shù)中進(jìn)行刪除 k=DeleteAVL(p->lchild,key,shorter); if(shorter=1) Leftbalance_div(p,shorter); return k; else if(LQ(key.key,p->data.key) )/在p的右子樹(shù)中進(jìn)行刪除 k=DeleteAVL(p->rchild,key,shorter); if(shorter=1) Rbalance_div(p,shorter); return k; else q

19、=p; if(p->rchild=NULL) /右子樹(shù)空則只需重接它的左子樹(shù) p=p->lchild; free(q); shorter=1; else if(p->lchild=NULL)/左子樹(shù)空則只需重接它的右子樹(shù) p=p->rchild; free(q); shorter=1; else Delete(q,q->lchild,shorter); if(shorter=1) Leftbalance_div(p,shorter); p=q; return a; void Print_BSTTree(BSTree T,int i) if(T) if(T->

20、rchild) Print_BSTTree(T->rchild,i+1); for(int j=1;j<=i;j+) cout<<" " cout<<T->data.key<<endl; if(T->lchild) Print_BSTTree(T->lchild,i+1); int main() cout<<"中法計(jì)122班 徐彤坤 122930 "<<endl; BSTree T; ElemType e; InitBSTree(T); bool tall=false; bool choice=true; char y; while(choice) cout<<"輸入要插入結(jié)點(diǎn)(數(shù)字):" cin>>e.key; InsertAVL(T,e,tall); Print_BSTTree(T,0); cout<<"是否繼續(xù)，是選y，否選n:" cin>>y; if(y='Y'|y='y') choice=true; else choice=false; BSTree f,