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

1、課程設(shè)計報告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目平衡二叉樹操作指導(dǎo)教師設(shè)計起止日2010-5-16學(xué)院計算機學(xué)院專業(yè)軟件工程學(xué)生姓名班級/學(xué)號成績一.需求分析1、建立平衡二叉樹并進行創(chuàng)建、增加、刪除、調(diào)平等操作。2、設(shè)計一個實現(xià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)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子

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

3、如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。三.詳細(xì)設(shè)計樹的內(nèi)部變量typedefstructBTNode(intdata;/平衡因子/左、右孩子intbf;structBTNode*lchild,*rchild;BTNode,*BTree;調(diào)平二叉樹（左右調(diào)平方式大體雷同，之具體寫出其中一種調(diào)平方式）if（插入元素與當(dāng)前根元素相等）printf（"已存在相同關(guān)鍵字的結(jié)點n"）;if（插入元素小于當(dāng)前根元素）if（插入新結(jié)點不成功）retur

4、n0;if（插入成功）switch（查看根的平衡因子）case+1:進行左平衡處理；檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理case+1:令根及其左孩子的平衡因子為0;做右平衡處理；BTreelc;lc指向的結(jié)點左子樹根結(jié)點；rc的右子樹掛接為結(jié)點的左子樹；lc的右孩子為原結(jié)點；原結(jié)點指向新的結(jié)點lc;break;case-1:rd指向*T的左孩子的右子樹根switch（查看右孩子平衡因子）case+1:根的平衡因子為-1;根左孩子的平衡因子為0;break;case0:令根和根左孩子的平衡因子為0;break;case-1:根平衡因子為0;根左孩子平衡因子為1;break;)根右孩子的平衡

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

6、判斷而不必再其他位置判斷，并且調(diào)試成功。五.使用說明和測試結(jié)果測試數(shù)據(jù)：創(chuàng)建二叉樹抄,盛三登料彳需躲袈3,直號創(chuàng)建平衡二黑樹明在平創(chuàng)二叉樹上增加薪結(jié)算弁奧平Ks.F,：=-H.i±I“錨A美使字以-魏hk吉束建立二見樹“庠* 輸入美鋰宇£先對吉米星交二尺的口謂情A美健手B.7：2hK吉束建立二見樹，巧* 輸入美鋌字（以-靠我對古車隹立二叉的* 植入美健丸打.7：2%K吉束建立二見樹"1'槃襦黯髓料E-請粕入美鏢字（以7義海鳧吉事建立二叉樹X10請輸入關(guān)鍵手工以-耀我達(dá)吉里建立二尺樹八M清箝丸美鑲室£如會海時吉申建立二禺村XTZW您擷的二支何為I3

7、415g5W接任植返續(xù).增加二叉樹直接創(chuàng)建平衡二叉樹廠整粗明構(gòu)集程設(shè)iH安嚏六'平都二火樹鼻作"描叫'平法;又找幄柞.*仝'上腿噎2T雷褊w賓m一直皿座平衡二第期*一在平湎：尺情二堵筆罪駛并'肝歷工丁一退出3請移入美寬字以-羽環(huán)7維地建立平兩二尺軻，汴清常久關(guān)碑宇以T±7G7結(jié)束建立平衡二叉鈍卜后謂鐲人關(guān)校字以7?"7后先建立平兩二圮樹,：,謂箱入關(guān)陡字以HZ7G7結(jié)室建立平衡二叉的，:6請讀川關(guān)校字以7?9?后再建立平由二尺樹：5請箱入關(guān)品字以7七"7結(jié)束建立平彼1二叉樹）；1謂皆及匏?以72%?后由逑立平匍二況樹X3請

8、箱入關(guān)度平4以7七"7結(jié)束冬立平衡二艮樹）；2謂詒兒瑩度字,以72%?靖夬建立平匍二尺樹:i9142族任章出匿乳.平衡二叉樹加入新節(jié)點并調(diào)平逼甯入關(guān)加字S以-心?阻浩束建立平窗;義網(wǎng)"請就人并排?以-乳x?克洋立三衡二發(fā)樹門消需入關(guān)鉞牛s以-g?ET造用建士平荷二尺利：R請就上若排子以T2陛?克洋友三衡二二樹）工謂需人關(guān)加豐以TEFET轉(zhuǎn)束建立平曲二尺樹X4請輸，美群*以-乳雪工1克泮立衛(wèi)衡二二樹代之謂需入關(guān)加豐以TEFET轉(zhuǎn)束建立平曲二叉樹，工遣被，美群*以T£X?克津市平衡二里樹篝黑,看於嚴(yán)哈宋建棄兩二尺利，T加9$帙任餐度鉞竦.2禹菱縷富后也鬻晝點*-宜接創(chuàng)

9、建平衡二尺樹4-在平衡二天樹4*加新結(jié)點并調(diào)平衡5力詠小且出春播入的罪增加的主攥W9gai-9B唉耳芭健雄等.刪除結(jié)點六.心得體會了解了建立樹的方法；學(xué)會了利用二分法建立樹結(jié)構(gòu)。、；學(xué)習(xí)到了二叉樹的調(diào)平方法；學(xué)會了向一個已知樹插入或刪除結(jié)點的方法。七.附錄源代碼#include"stdafx.h"#include<stdio.h>#include<malloc.h>#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)<(b)#defineLQ(a,b)(a)>(b)# defineLH+1/左高# defineEH

10、0/等高# defineRH-1/右高typedefstructBTNodeintdata;intbf;/平衡因子structBTNode*lchild,*rchild;/左、右孩子BTNode,*BTree;/*需要的函數(shù)聲明*/voidRight_Balance(BTree&p);voidLeft_Balance(BTree&p);voidLeft_Root_Balance(BTree&T);voidRight_Root_Balance(BTree&T);boolInsertAVL(BTree&T,inti,bool&taller);void

11、PrintBT(BTreeT,intm);voidCreatBT(BTree&T);voidLeft_Root_Balance_det(BTree&p,int&shorter);voidRight_Root_Balance_det(BTree&p,int&shorter);voidDelete(BTreeq,BTree&r,int&shorter);intDeleteAVL(BTree&p,intx,int&shorter);voidAdj_balance(BTree&T);boolSetAVL(BTree&

12、;T,inti,bool&taller);boolInsert_Balance_AVL(BTree&T,inti,bool&taller);/*主函數(shù)*/voidmain()intinput,search,m;booltaller=false;intshorter=0;BTreeT;T=(BTree)malloc(sizeof(BTNode);T=NULL;while(1)printf("n請選擇需要的二叉樹操作n");5.printf("1.創(chuàng)建二叉樹2.增加新結(jié)點3.直接創(chuàng)建平衡二叉樹4.在平衡二叉樹上增加新結(jié)點并調(diào)平衡刪除0.退出n&

13、quot;);scanf("%d”,&input);getchar();switch(input)case 1:CreatBT(T);break;case 2:printf("請輸入你要增加的關(guān)鍵字");scanf("%d”,&search);getchar();InsertAVL(T,search,taller);m=0;PrintBT(T,m);break;case 3:Adj_balance(T);break;case 4:printf("請輸入你要增加的關(guān)鍵字");scanf("%d",&a

14、mp;search);getchar();SetAVL(T,search,taller);m=0;PrintBT(T,m);break;case 5:printf("請輸入你要刪除的關(guān)鍵字");scanf("%d",&search);getchar();DeleteAVL(T,search,shorter);m=0;PrintBT(T,m);break;case0:break;default:printf("輸入錯誤，請重新選擇。");break;if(input=0)break;printf("按任意鍵繼續(xù).&qu

15、ot;);getchar();/*對以*p為根的二叉排序樹作右旋處理*/voidRight_Balance(BTree&p)BTreelc;lc=p->lchild;/lc指向的*p左子樹根結(jié)點p->lchild=lc->rchild;/rc的右子樹掛接為*p的左子樹lc->rchild=p;p=lc;/p指向新的結(jié)點/*對以*p為根的二叉排序樹作左旋處理*/voidLeft_Balance(BTree&p)BTreerc;/指向的*p右子樹根結(jié)點/rc左子樹掛接到*p的右子樹rc=p->rchild;p->rchild=rc->lch

16、ild;rc->lchild=p;p=rc;/p指向新的結(jié)點)/*對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理*/voidLeft_Root_Balance(BTree&T)(BTreelc,rd;lc=T->lchild;/指向*T的左子樹根結(jié)點switch(lc->bf)/檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理(caseLH:/新結(jié)點插入在*丁的左孩子的左子樹上，要作單右旋處理T->bf=lc->bf=EH;Right_Balance(T);break;caseRH:/新結(jié)點插入在*丁的左孩子的右子樹上，要作雙旋處理rd=lc->rchil

17、d;/rd指向*T的左孩子的右子樹根switch(rd->bf)/修改*T及其左孩子的平衡因子(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);/*T的左子樹作左旋平衡處理Right_Balance(T);/*T作右旋平衡處理)/*對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理*/voidRight_Root_Balance(BTree

18、&T)BTreerc,ld;rc=T->rchild;/指向*丁的左子樹根結(jié)點switch(rc->bf)/檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理(caseRH:/新結(jié)點插入在*丁的右孩子的右子樹上，要作單左旋處理T->bf=rc->bf=EH;Left_Balance(T);break;caseLH:/新結(jié)點插入在*丁的右孩子的左子樹上，要作雙旋處理ld=rc->lchild;/ld指向*T的右孩子的左子樹根switch(ld->bf)/修改*T及其右孩子的平衡因子(caseLH:T->bf=EH;rc->bf=RH;break;c

19、aseEH: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);/風(fēng)叮作左旋平衡處理*/)/*插入結(jié)點i,若T中存在和i相同關(guān)鍵字的結(jié)點，則插入一個數(shù)據(jù)元素為i的新結(jié)點，并返回1,否則返回0boolInsertAVL(BTree&T,inti,bool&taller)(if(!T)/插入新結(jié)點，樹長高"，置taller為true(T=(BTree)

20、malloc(sizeof(BTNode);T->data=i;T->lchild=T->rchild=NULL;T->bf=EH;taller=true;)else(if(EQ(i,T->data)/樹中已存在和有相同關(guān)鍵字的結(jié)點(taller=false;printf("已存在相同關(guān)鍵字的結(jié)點n");return0;)if(LT(i,T->data)/應(yīng)繼續(xù)在*T的左子樹中進行搜索(if(!InsertAVL(T->lchild,i,taller)return0;)else/應(yīng)繼續(xù)在*T的右子樹中進行搜索(if(!InsertA

21、VL(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;i<=m;i+)printf("");/打印i個空格以表示出層次printf("%dn",T->data);/打印T元素，換行if(T->lchild)PrintBT(T->lchild,m+1);)else(printf(

22、"這是一棵空樹！n");getchar();)/*創(chuàng)建二叉樹，以輸入-32767為建立的結(jié)束*/voidCreatBT(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&

23、quot;,&i);getchar();taller=false;)m=0;printf("您創(chuàng)建的二叉樹為：n");PrintBT(T,m);)/*刪除結(jié)點時左平衡旋轉(zhuǎn)處理*/voidLeft_Root_Balance_det(BTree&p,int&shorter)(BTreep1,p2;if(p->bf=1)/p結(jié)點的左子樹高，刪除結(jié)點后p的bf減，樹變矮(p->bf=0;shorter=1;elseif(p->bf=0)/p結(jié)點左、右子樹等高，刪除結(jié)點后p的bf減，樹高不變(p->bf=-1;shorter=0;els

24、e/p結(jié)點的右子樹高(p1=p->rchild;/p1指向p的右子樹if(p1->bf=0)/p1結(jié)點左、右子樹等高，刪除結(jié)點后p的bf為-2,進行左旋處理，樹高不變(Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;elseif(p1->bf=-1)/p1的右子樹高，左旋處理后，樹變矮(Left_Balance(p);p1->bf=p->bf=0;shorter=1;else/p1的左子樹高，進行雙旋處理(先右旋后左旋)，樹變矮(p2=p1->lchild;p1->lchild=p2->rchi

25、ld;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf=0)(p->bf=0;p1->bf=0;elseif(p2->bf=-1)(p->bf=1;p1->bf=0;)else(p->bf=0;p1->bf=-1;)p2->bf=0;P=P2；shorter=1;)&shorter)/*刪除結(jié)點時右平衡旋轉(zhuǎn)處理*/voidRight_Root_Balance_det(BTree&p,int(BTreep1,p2;if(p->bf=

26、-1)(p->bf=0;shorter=1;)elseif(p->bf=0)(p->bf=1;shorter=0;)else(p1=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;)else(p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lc

27、hild=p2->rchild;p2->rchild=p;if(p2->bf=0)(p->bf=0;p1->bf=0;)elseif(p2->bf=1)(p->bf=-1;p1->bf=0;)else(p->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(

28、q);shorter=1;)else(Delete(q,r->rchild,shorter);if(shorter=1)Right_Root_Balance_det(r,shorter);)/*二叉樹的刪除操作*/intDeleteAVL(BTree&p,intx,int&shorter)(intk;BTreeq;if(p=NULL)(printf("不存在要刪除的關(guān)鍵字!n");return0;)elseif(x<p->data)/在p的左子樹中進行刪除(k=DeleteAVL(p->lchild,x,shorter);if(sho

29、rter=1)Left_Root_Balance_det(p,shorter);returnk;)elseif(x>p->data)/在p的右子樹中進行刪除(k=DeleteAVL(p->rchild,x,shorter);if(shorter=1)Right_Root_Balance_det(p,shorter);returnk;)else(q=p;if(p->rchild=NULL)/右子樹空則只需重接它的左子樹(p=p->lchild;free(q);shorter=1;)elseif(p->lchild=NULL)/左子樹空則只需重接它的右子樹(p=

30、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)鍵字(以-32767結(jié)束建立平衡二叉樹):");scanf("%d",&i);getchar();while(i!=-32767)(SetAVL(T,i,taller);printf("n請輸入關(guān)鍵字(以-32767結(jié)束建立平衡二叉樹):");scanf("%d",&i);getchar();ta