數(shù)據(jù)結(jié)構(gòu)課程設(shè)計平衡二叉樹操作

1、 課程設(shè)計報告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目指導(dǎo)教師設(shè)計起止日學(xué)院計算機(jī)學(xué)院專業(yè)軟件工程學(xué)生姓名班級學(xué)號成績一需求分析1、建立平衡二叉樹并進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作。2、設(shè)計一個實現(xiàn)平衡二叉樹的程序，可進(jìn)行創(chuàng)建、增加、刪除、調(diào)平等操作，實現(xiàn)動態(tài)的輸入數(shù)據(jù)，實時的輸出該樹結(jié)構(gòu)。3、測試數(shù)據(jù)：自選數(shù)據(jù)二概要設(shè)計平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下：每當(dāng)插入一個新結(jié)點

2、，從該結(jié)點開始向上計算各結(jié)點的平衡因子，即計算該結(jié)點的祖先結(jié)點的平衡因子，若該結(jié)點的祖先結(jié)點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續(xù)插入結(jié)點；若插入結(jié)點的某祖先結(jié)點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結(jié)點；判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點的關(guān)系，確定是哪種類型的調(diào)整；如果是型或型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是型或型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；計算調(diào)整后的

3、平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。三詳細(xì)設(shè)計樹的內(nèi)部變量typedefstructBTNodeintdata;intbf;/平衡因子structBTNode*lchild,*rchild;/左、右孩子BTNode,*BTree;調(diào)平二叉樹（左右調(diào)平方式大體雷同，之具體寫出其中一種調(diào)平方式TOC o 1-5 h zif（插入元素與當(dāng)前根元素相等）printf（已存在相同關(guān)鍵字的結(jié)點n）;if（插入元素小于當(dāng)前根元素）if（插入新結(jié)點不成功）return0;if（插入成功）switch（查看根的平衡因子）c

4、ase+1:進(jìn)行左平衡處理;檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理case+1:TOC o 1-5 h z令根及其左孩子的平衡因子為0;做右平衡處理;BTreelc;lc指向的結(jié)點左子樹根結(jié)點;rc的右子樹掛接為結(jié)點的左子樹;lc的右孩子為原結(jié)點;原結(jié)點指向新的結(jié)點lc;break;case-1:rd指向*T的左孩子的右子樹根TOC o 1-5 h zswitch（查看右孩子平衡因子）case+1:根的平衡因子為-1;根左孩子的平衡因子為0;break;case0:令根和根左孩子的平衡因子為0;break;case-1:1;根平衡因子為0;根左孩子平衡因子為break;根右孩子的平衡因子為

5、0;TOC o 1-5 h z對*T的左子樹作左旋平衡處理;對*TD右旋平衡處理;break;case0:令根的平衡因子為+1;break;case-1:令根的平衡因子為-1;break;四調(diào)試分析在進(jìn)行對插入新結(jié)點并調(diào)平時由于利用的是普通的插入方法進(jìn)行、型的轉(zhuǎn)換，使得在調(diào)試時經(jīng)常沒有更改內(nèi)部變量的值，導(dǎo)致編譯出錯。對于在空樹情況下刪除結(jié)點的考慮，是在后期的調(diào)試檢驗過程中發(fā)現(xiàn)的。在沒有更改代碼前，如果按此操作，程序就會崩潰。原因就是在刪除函數(shù)中雖然考慮到了空樹的情況，但是在輸出樹的函數(shù)中沒有加入空樹的考慮而只是在創(chuàng)建樹函數(shù)中加入了的判斷。經(jīng)過反復(fù)的檢查，發(fā)現(xiàn)可以直接在輸出函數(shù)中加入判斷而不必再

6、其他位置判斷，并且調(diào)試成功。五使用說明和測試結(jié)果測試數(shù)據(jù)：創(chuàng)建二叉樹 #ffli量.ufpi矗C-蘭MF?旦-TT-i1e.咱liWf.I：|T11洋中!I忠I!壬丄因）片sIllrmJII.1.1.rchild;/rc的右子樹掛接為*pOOODlc-rchild=p;p=lc;/p指向新的結(jié)點/*對以*pD根的二叉排序樹作左旋處理*/voidLeft_Balance(BTree&p)BTreerc;rc=p-rchild;/指向的*p右子樹根結(jié)點p-rchild=rc-lchild;/rc左子樹掛接到*pOOODrc-lchild=p;p=rc;/p指向新的結(jié)點 #/*對以指針T所指結(jié)點為根

7、的二叉樹作左平衡旋轉(zhuǎn)處理*/&T)voidLeft_Root_Balance(BTreeBTreelc,rd;lc=T-lchild;switch(lc-bf)caseLH:T-bf=lc-bf=EH;Right_Balance(T);break;caseRH:rd=lc-rchild;switch(rd-bf)caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;Left_Balance(T-lchild);Right_Balance(T);/*對以指針T

8、所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理voidRight_Root_Balance(BTree&T)/指向*TD左子樹根結(jié)點/檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理/新結(jié)點插入在*T的左孩子的左子樹上，要作單右旋處理/新結(jié)點插入在*T的左孩子的右子樹上，要作雙旋處理/rd指向*T的左孩子的右子樹根/修改*叮其左孩子的平衡因子/對*T的左子樹作左旋平衡處理/對*TD右旋平衡處理*/BTreerc,ld;rc=T-rchild;/指向*TD左子樹根結(jié)點switch(rc-bf)/檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理caseRH:/新結(jié)點插入在*T的右孩子的右子樹上，要作單左旋處理T-bf=

9、rc-bf=EH;Left_Balance(T);break;caseLH:/新結(jié)點插入在*T的右孩子的左子樹上，要作雙旋處理ld=rc-lchild;/ld指向*T的右孩子的左子樹根switch(ld-bf)/修改*TD其右孩子的平衡因子 #caseLH:T-bf=EH;rc-bf=RH;break;caseEH:T-bf=rc-bf=EH;break;caseRH:T-bf=LH;rc-bf=EH;break;ld-bf=EH;Right_Balance(T-rchild);/對*T的右子樹作左旋平衡處理Left_Balance(T);/對*TD左旋平衡處理/*插入結(jié)點i,若T中存在和i相

10、同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為boolInsertAVL(BTree&T,inti,bool&taller)if(!T)/插入新結(jié)點，樹長高，置taller為truei的新結(jié)點，并返回叮否則返叮*/T=(BTree)malloc(sizeof(BTNode);T-data=i;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;elseif(EQ(i,T-data)taller=false;printf(已存在相同關(guān)鍵字的結(jié)點return0;if(LT(i,T-data)/樹中已存在和有相同關(guān)鍵字的結(jié)點n);/應(yīng)繼續(xù)在*T的左子樹中進(jìn)行搜索if(!Ins

11、ertAVL(T-lchild,i,taller)return0;else/應(yīng)繼續(xù)在*T的右子樹中進(jìn)行搜索if(!InsertAVL(T-rchild,i,taller)return0; # #return1;/*按樹狀打印輸出二叉樹的元素，m表示結(jié)點所在層次*/voidPrintBT(BTreeT,intm)if(T)inti;if(T-rchild)PrintBT(T-rchild，m+1);for(i=1;ilchild)PrintBT(T-lchild,m+1);elseprintf(這是一棵空樹！n);getchar();/*創(chuàng)建二叉樹，以輸入-32767為建立的結(jié)束*/voidCr

12、eatBT(BTree&T)intm;inti;booltaller=false;T=NULL;printf(n請輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹):);scanf(%i,&i);getchar();while(i!=-32767)InsertAVL(T,i,taller);printf(n請輸入關(guān)鍵字(以-32767結(jié)束建立二叉樹):);scanf(%i,&i);getchar();taller=false;m=0;printf(您創(chuàng)建的二叉樹為：n);PrintBT(T,m); #/*刪除結(jié)點時左平衡旋轉(zhuǎn)處理*/voidLeft_Root_Balance_det(BTree&p,i

13、nt&shorter)BTreep1,p2;if（p-bf=l）/p結(jié)點的左子樹高，刪除結(jié)點后p的bf減，樹變矮p-bf=0;shorter=1;elseif(p-bf=O)/p結(jié)點左、右子樹等高，刪除結(jié)點后p-bf=-1;shorter=0;else/p結(jié)點的右子樹高pl=p-rchild;/pl指向p的右子樹if(pl-bf=O)/pl結(jié)點左、右子樹等高，刪除結(jié)點后Left_Balance(p);p1-bf=1;p-bf=-1;shorter=0;elseif(pl-bf=T)/pl的右子樹高，左旋處理后，樹變矮Left_Balance(p);p1-bf=p-bf=0;shorter=1;

14、else/pl的左子樹高，進(jìn)行雙旋處理(先右旋后左旋p的bf減，樹高不變p的bf為一2,進(jìn)行左旋處理，樹高不變），樹變矮p2=pl-lchild;pl-lchild=p2-rchild;p2-rchild=pl;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)p-bf=0;pl-bf=0;elseif(p2-bf=-l)p-bf=l;pl-bf=0; #elsep-bf=0;p1-bf=-1;p2-bf=0;p=p2;shorter=1;/*/voidRight_Root_Balance_det(BTree&p,int&shorter)BTreep1,p2;

15、if(p-bf=-1)p-bf=0;shorter=1;elseif(p-bf=0)p-bf=1;shorter=0;elsep1=p-lchild;if(p1-bf=0)Right_Balance(p);p1-bf=-1;p-bf=1;shorter=0;elseif(p1-bf=1)Right_Balance(p);p1-bf=p-bf=0;shorter=1;elsep2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)p-bf=0;p1-bf=0;elseif(p2

16、-bf=1)p-bf=-1;p1-bf=0;elsep-bf=0;p1-bf=1;p2-bf=0;p=p2;shorter=1;/*刪除結(jié)點*/voidDelete(BTreeq,BTree&r,int&shorter)if(r-rchild=NULL)q-data=r-data;q=r;r=r-lchild;free(q);shorter=1;elseDelete(q,r-rchild,shorter);if(shorter=1)Right_Root_Balance_det(r,shorter);/*二叉樹的刪除操作*/intDeleteAVL(BTree&p,intx,int&shorte

17、r)intk;BTreeq;if(p=NULL)printf(不存在要刪除的關(guān)鍵字！n);return0;elseif(xp-data)/在p的左子樹中進(jìn)行刪除k=DeleteAVL(p-lchild,x,shorter);if(shorter=1)Left_Root_Balance_det(p,shorter);returnk;elseif(xp-data)/在p的右子樹中進(jìn)行刪除k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)Right_Root_Balance_det(p,shorter);returnk;elseq=p;if(p-rchild=

18、NULL)/右子樹空則只需重接它的左子樹p=p-lchild;free(q);shorter=1;elseif(p-lchild=NULL)/左子樹空則只需重接它的右子樹p=p-rchild;free(q);shorter=1;else/左右子樹均不空Delete(q,q-lchild,shorter);if(shorter=1)Left_Root_Balance_det(p,shorter);p=q;return1; # # /*二叉樹調(diào)平操作*/voidAdj_balance(BTree&T)intm;inti;booltaller=false;T=NULL;printf(n請輸入關(guān)鍵字(

19、以-32767結(jié)束建立平衡二叉樹)：)；scanf(%d,&i);getchar()；while(i!=-32767)SetAVL(T,i,taller)；printf(n請輸入關(guān)鍵字scanf(%d,&i)；getchar()；taller=false；m=0；printf(平衡二叉樹創(chuàng)建結(jié)束if(T)PrintBT(T,m)；else(以-32767結(jié)束建立平衡二叉樹.n)；)：)； # #printf(這是一棵空樹.n);/*調(diào)平二叉樹具體方法*/boolSetAVL(BTree&T,inti,bool&taller)長高，置taller為trueT=(BTree)malloc(sizeof(BTNode);T-data=i;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;else/樹中已存在和有相同關(guān)鍵字的結(jié)點n);