二叉平衡樹的實現(xiàn)---數(shù)據(jù)結構課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：26 大小：174.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩25頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　課程設計名稱：數(shù)據(jù)結構課程設計　　課程設計題目：二叉平衡樹的實現(xiàn)　　院（系）：計算機學院　　專業(yè)：計算機科學與技術　　班級： &

2、lt;/p>　　學號：　　姓名： 　　指導教師： 　　目錄<b

3、>　　1 需求分析1　　1.1 課程設計內容和要求1　　1.2 算法描述1　　1.2.1存儲結構1　　1.2.2 二叉排序樹和二叉平衡樹1　　1.2.3 層次遍歷二叉樹1

4、;　　2 系統(tǒng)設計2　　2.1 總體方案設計2　　2.2 函數(shù)設計2　　2.3 關鍵流程4　　2.3.1 系統(tǒng)主流程4　　2.3.2 reat()創(chuàng)建鏈表函數(shù)

5、流程5　　2.3.3 travel()層次遍歷函數(shù)流程6　　2.3.4 B1()求左右孩子深度函數(shù)流程7　　2.3.5 B2()求節(jié)點平衡度函數(shù)流程8　　2.3.6 kind()判斷節(jié)點不平衡的類型函數(shù)流程9　　2.3.

6、7 deal()轉化成平衡樹類型函數(shù)流程10　　3 調試分析11　　參考文獻14　　附錄15　　1 需求分析<

7、p>　　1.1 課程設計內容和要求　　內容：　　從鍵盤輸入多組數(shù)據(jù)，生成相應的二叉排序樹并將各二叉排序樹轉換為二叉平衡樹，比較二叉排序樹和二叉平衡樹的平均比較長度，并將文件保存到文件中。　　要求：<p

8、>　　1．二叉排序樹和二叉平衡樹的存儲結構自定；　　2．輸入數(shù)據(jù)要考慮多種情況，有代表性；　　3．給出動態(tài)顯示過程(選作)；　　1.2 算法描述　　1.2.1存儲結構

9、　　二叉排序樹是采用二叉鏈表建立，左孩子存放比父親節(jié)點小的數(shù)，右孩子存放比父親節(jié)點大的數(shù)。二叉排序樹向二叉平衡樹轉化時用隊列來存儲每一個節(jié)點，然后層次遍歷時也是用到隊列，然后輸出隊列就為層次遍歷的結果。　　1.2.2 二叉排序樹和二叉平衡樹　　用戶輸入數(shù)據(jù)，程序會按照層次遍歷的結果建立二叉排序樹，比根節(jié)點小的數(shù)放在做孩子節(jié)點中，比根節(jié)點

10、大的數(shù)據(jù)放入右孩子節(jié)點。二叉平衡樹建立時，需要判斷每個節(jié)點的平衡度，即左孩子的深度減去右孩子的深度的值的絕對值小于等于1，如果大于1，則該節(jié)點出現(xiàn)不平衡，從該節(jié)點開始調整成平衡。　　1.2.3 層次遍歷二叉樹　　從根節(jié)點出發(fā),輸出結點信息到隊列中,然后依次遍歷結點的左右孩子,每輸出一結點信息,,將其存儲在隊列中, 遍歷完結點后,隊列元素出隊.循環(huán)執(zhí)行該過

11、程,當隊列為空時,函數(shù)執(zhí)行結束。將結果再保存到文件中。　　2 系統(tǒng)設計　　2.1 總體方案設計　　系統(tǒng)的總體設計方案是：首先由用戶輸入數(shù)據(jù)，然后進入二叉排序函數(shù)對數(shù)據(jù)進行排序，排完序后對每一個節(jié)點求深度，然后判斷出不平衡的節(jié)點，調用平衡函數(shù)把不平衡的節(jié)點調整成平衡的節(jié)點，直

12、到循環(huán)結束，二叉平衡樹也就轉換完成。然后再層次遍歷二叉平衡樹，輸出結果并保存到文件中。　　2.2 函數(shù)設計　　﹙1﹚本系統(tǒng)所設計的函數(shù)見表2.1。　　表2.1 函數(shù)列表　　﹙2﹚本系統(tǒng)函數(shù)的調用關

13、系見圖2.1。　　圖2.1 調用關系圖　　2.3 關鍵流程　　2.3.1 系統(tǒng)主流程　?。?）主函數(shù)的簡單描述：　　本函數(shù)的具體功能是：該函數(shù)是系統(tǒng)執(zhí)行的必須函數(shù)，本函數(shù)包含其他各個子函數(shù)，經(jīng)

14、過調用，實現(xiàn)二叉排序樹，并把二叉排序樹轉化成二叉平衡樹。　　（2）主函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.2。　　圖2.2 主函數(shù)的流程圖　　2.3.2 reat()創(chuàng)建鏈表函數(shù)流程　?。?）創(chuàng)建鏈表函數(shù)的簡單描述：</p

15、>　　本函數(shù)的具體功能是：根據(jù)用戶輸入的數(shù)據(jù)創(chuàng)建二叉排序樹。　　（2）創(chuàng)建鏈表函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.3。流程圖中變量i,k為控制循環(huán)的整型變量；n為要輸入的數(shù)據(jù)的個數(shù)；D[100]為存儲輸入的數(shù)據(jù)。　　N&

16、lt;p>　　Y　　圖2.3 creat()函數(shù)的流程圖　　2.4.3 travel()層次遍歷函數(shù)流程　?。?）層次遍歷函數(shù)的簡單描述：　　本函數(shù)的具體功能：層次遍歷二叉樹，把遍歷的數(shù)據(jù)存儲到鏈表中。&

17、lt;p>　?。?）層次遍歷函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.4。　　N　　Y　　N

18、　　Y　　N　　Y N　　Y　　圖2.4 travel()函數(shù)的流程圖　　2.4.4 B1()求左右孩子深度函數(shù)流程&

19、lt;/p>　　（1）求深度函數(shù)的簡單描述：　　本函數(shù)的具體功能是：完成二叉排序樹的存儲　?。?）求深度函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.5。流程圖有變量n1,n2為標記該節(jié)點的位置。　　Y N

20、　　N　　Y　　N　　Y　　圖2.5 B1()函數(shù)的流程圖

21、;　　2.4.5 B2()求節(jié)點平衡度函數(shù)流程　　（1）求節(jié)點平衡度函數(shù)的簡單描述：　　本函數(shù)的具體功能是：計算出每一個節(jié)點的不平衡度，為轉化成二叉平衡樹做鋪墊。　　2）求節(jié)點平衡度函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.6。&l

22、t;b>　　N　　Y　　圖2.6 B2()函數(shù)的流程圖　　2.4.6 kind()判斷節(jié)點不平衡的類型函數(shù)流程　　判斷節(jié)點不平衡的類型函數(shù)的簡單描述：　　本函數(shù)的具體

23、功能是：判斷出每一個節(jié)點是RR 、RL、 LR 、LL中的哪種。　?。?）判斷節(jié)點不平衡的類型函數(shù)的流程圖　　本函數(shù)的具體流程見圖2.7。流程圖有變量k為標記該節(jié)點是第幾種不平衡類型。　　2 3 4 1　　圖2

24、.7 kind()函數(shù)的流程圖　　2.4.7 deal()轉化成平衡樹類型函數(shù)流程　?。?）轉化成平衡樹類型函數(shù)的簡單描述：　　本函數(shù)的具體功能是：從不平衡的節(jié)點開始，把節(jié)點轉化平衡。　?。?）轉化成平衡樹類型函數(shù)的流程圖　　本函

25、數(shù)的具體流程見圖2.8。流程圖有變量k為標記該節(jié)點是第幾種不平衡類型，i為循環(huán)變量，j為判斷節(jié)點是否存在。　　N　　Y　　N　　Y</

26、b>　　圖2.8 deal()函數(shù)的流程圖　　3 調試分析　　(1) 問題1　　問題描述：輸入數(shù)據(jù)后，輸出的二叉樹層次遍歷不準確。　　問題分析：d

27、eal函數(shù)編譯錯誤，搞錯了LL與LR類型。　　解決方法：進入單部調試函數(shù)，跟蹤每個參數(shù)，一點一點找到問題所在并改正。　　(2) 問題2　　問題描述：無法將數(shù)據(jù)保存到文件中。　　問題分析：可能是文件讀

28、寫錯誤或者隊列應用錯誤　　解決方法：檢查文件的讀寫，設置一個新的參數(shù)將樹中的值傳給它，用它完成文件的保存。　　4 測試及運行結果　　進入操作界面如圖4.1所示。　　圖4.1 操作界面結果　?。?）輸入多組數(shù)據(jù)的具體的測試結果如圖

29、4.2所示。　　圖4.2 多組數(shù)據(jù)測試結果　?。?）經(jīng)層次遍歷后的平衡二叉樹輸出數(shù)據(jù)的具體的測試結果如圖4.3所示。　　圖4.3 輸出數(shù)據(jù)測試結果　　測試結果保存到到D盤的二叉平衡樹的文件中如圖4.4所示。　　圖4.4保存到文件中

30、　　參考文獻　　[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）.北京：清華大學出版社，2007 　　[2] 譚浩強.C程序設計（第三版）.清華大學出版社，2009　　[3] 高一凡. 數(shù)據(jù)結構算法分析.清華大學出版社，2008</

31、p>　　[4] 張長海.C程序設計.高等教育出版社，20004 　　[5] 王裕明.數(shù)據(jù)結構與程序設計.清華大學出版社，2010　　[6] 王曙燕曹錳. C語言程序設計. 科學出版社，2005　　附錄

32、;　　源程序清單：　　#include<stdio.h>　　#include<stdlib.h>　　typedef struct BF　　{<

33、p>　　int data;　　int parent;　　int left;　　int right;　　int bf;<p&

34、gt;　　}BF;　　typedef struct Bitree　　{　　int data;　　struct Bitree *right;

35、　　struct Bitree *left;　　}Bitree;　　typedef struct　　{　　Bitree *base;

36、　　int top;　　int bottom;　　int size;　　}queue;　　BF c[100];　　v

37、oid inistall(queue &q)　　{　　q.base=(Bitree *)malloc(sizeof(Bitree)*100);　　q.top=q.bottom=0;　　q.size=100;

38、　　}　　void push(Bitree t,queue &q)　　{　　if(q.top==100)　　printf("queue full\n&quo

39、t;);　　q.base[q.top++]=t; 　　}　　int empty(queue q)　　{<p&g

40、t;　　if(q.top==q.bottom)　　return 1;　　else 　　return 0;　　}</

41、p>　　void pop(Bitree *&temp,queue &q)　　{　　if(q.top==q.bottom)　　printf("queue null\n");

42、　　else 　　temp=&(q.base[q.bottom++]);　　}　　queue travel(Bitree *t)　　{</p&g

43、t;　　queue q;　　Bitree *temp;　　inistall(q);　　push(*t,q); 　　while(!empty(q))<b&g

44、t;　　{　　pop(temp,q);　　printf("%d ",temp->data);　　if(temp->left)　　push(*temp->left,q);

45、if(temp->right)　　push(*temp->right,q);　　}　　return q;　　}<p&

46、gt;　　int Deep(Bitree *T)　　{　　int k,left,right;　　if(!T)k=0;　　else　　{&

47、lt;/b>　　right=Deep(T->right);　　left=Deep(T->left);　　if(right>left)　　k=1+right;　　else

48、;　　k=1+left;　　}　　return k;　　}　　int loca

49、te(int n)　　{　　int i;　　for(i=0;i<100;i++)　　if(c[i].data==n)　　retur

50、n i;　　}　　void B1(Bitree *T)　　{　　Bitree *p,*q;　　int n1,n2;

51、　　if(T) 　　{　　p=T;　　q=p->left;　　n1=locate(p->data);</p&g

52、t;　　if(q!=NULL)　　{n2=locate(q->data);　　c[n1].left=n2;　　c[n2].parent=n1;　　}

53、;　　else　　{　　c[n1].left=-1;　　}　　q=p->right;　　n1=locate(p->data

54、);　　if(q!=NULL)　　{n2=locate(q->data);　　c[n1].right=n2;　　c[n2].parent=n1;　　}<p&

55、gt;　　else　　{　　c[n1].right=-1;　　}　　B1(T->left);　　B1(T-&g

56、t;right);　　}　　}　　void B2(Bitree *T)　　{　　int n,left,right;&

57、lt;/p>　　if(T)　　{　　left=Deep(T->left);　　right=Deep(T->right);　　n=locate(T->d

58、ata);　　c[n].bf=left-right;　　B2(T->left);　　B2(T->right);　　}　　}

59、　　void B(Bitree *T)　　{　　int i;　　for(i=0;i<100;i++)　　c[i].parent=c[i].left=c[i].right

60、=-1;　　B1(T);　　B2(T);　　}　　void inistall(int a[],int n)<b

61、>　　{　　int i;　　for(i=0;i<n;i++)　　{　　c[i].data=a[i];　　c[i].left

62、=c[i].right=c[i].parent=-1;　　c[i].bf=0;　　}　　}　　void find(Bitree *T,int data,Bitree *&p)</p&

63、gt;　　{　　if(T)　　{　　if(T->data==data)　　p=T;</

64、p>　　find(T->left,data,p);　　find(T->right,data,p);　　}　　}　　int hunt(Bitree *p,Bi

65、tree *q)　　{　　if(p)　　{　　if(p->data==q->data)

66、　　return 1;　　else 　　{　　if(hunt(p->left,q))　　return 1;&

67、lt;p>　　else　　return hunt(p->right,q);　　}　　}　　else return 0;&l

68、t;p>　　}　　int kind(Bitree *p,Bitree *q)　　{　　Bitree *r,*s;　　int k;

69、　　if(p->right!=NULL)　　{　　r=p->right;　　s=r->right;　　if((s!=NULL)&&(hunt(s,q)))&l

70、t;p>　　k=2;//RR　　s=r->left;　　if((s!=NULL)&&(hunt(s,q)))　　k=3;//RL　　}</b&g

71、t;　　if(p->left!=NULL)　　{　　r=p->left;　　s=r->right;　　if((s!=NULL)&&(hunt(s,q)))&l

72、t;/p>　　k=4;//LR　　s=r->left;　　if((s!=NULL)&&(hunt(s,q)))　　k=1;//LL

73、;　　}　　return k;　　}　　int pos(Bitree *r,Bitree *q)　　{<p&

74、gt;　　int k;　　if(r->left==q)k=2;　　if(r->right==q)k=1;　　return k;　　}</p&

75、gt;　　void deal(Bitree *&T,int data)　　{　　int i,k=0,j,e;　　Bitree *p,*q,*r,*temp;　　i=locate(data);</p&

76、gt;　　while(c[i].bf<2&&c[i].bf>-2&&i!=-1)　　i=c[i].parent;　　if((c[i].bf>1||c[i].bf<-1)&&(i!=-1))　　{<

77、/b>　　find(T,c[i].data,p);　　j=c[i].parent;　　find(T,data,q);　　if(j!=-1)//r存在　　{ find(T,c[j].data,r);

78、　　e=pos(r,p);//e:1為p是r的右孩子 2為p是r的左孩子　　k=kind(p,q);//1:LL 2:RR 3:RL 4:LR　　if(e==1)//p是r的右孩子　　{　　swit

79、ch(k)　　{　　case 1:r->right=p->left;　　p->left=r->right->right;　　r->right->right=p;</p

80、>　　break;　　case 2:r->right=p->right;　　p->right=r->right->left;　　r->right->left=p;&

81、lt;b>　　break;　　case 3:temp=p->right->left;　　p->right->left=temp->right;　　temp->right=p->right;　　p->

82、right=temp;　　p->right=temp->left;　　temp->left=p;　　r->right=temp;　　break;　　case 4:tem

83、p=p->left->right;　　p->left->right=temp->left;　　temp->left=p->left;　　p->left=temp;　　p->left=temp->right;<

84、;/p>　　temp->right=p;　　r->right=temp;　　break;　　default:break;　　}<

85、;p>　　}　　if(e==2)//p是r的左孩子　　{ 　　switch(k)　　{&l

86、t;p>　　case 1:r->left=p->left;　　p->left=r->left->right;　　r->left->right=p;　　break;　　case 2:r-&

87、gt;left=p->right;　　p->right=r->left->left;　　r->left->left=p;　　break;　　case 3:temp=p->right->l

88、eft;　　p->right->left=temp->right;　　temp->right=p->right;　　p->right=temp;　　p->right=temp->left;<p&

89、gt;　　temp->left=p;　　r->left=temp;　　break;　　case 4:temp=p->left->right;　　p->left->right=temp->lef

90、t;　　temp->left=p->left;　　p->left=temp;　　p->left=temp->right;　　temp->right=p;　　r->left=temp;<

91、;/p>　　break;　　default:break;　　}　　}　　B(T);</

92、p>　　}　　else//A為頭結點　　{ 　　k=kind(p,q);//1:LL 2:RR 3:RL 4:LR　　switch(k)<

93、/b>　　{　　case 1:T=p->left;　　p->left=T->right;　　T->right=p;　　break;</b&

94、gt;　　case 2:T=p->right;　　p->right=T->left;　　T->left=p;　　break;　　case 3:temp=p->ri

95、ght->left;　　p->right->left=temp->right;　　temp->right=p->right;　　p->right=temp;　　p->right=temp->left;

96、;　　temp->left=p;　　T=temp;　　break;　　case 4:temp=p->left->right;　　p->left->

97、;right=temp->left;　　temp->left=p->left;　　p->left=temp;　　p->left=temp->right;　　temp->right=p;&l

98、t;b>　　T=temp;　　break;　　default:break;　　}　　B(T);<p&g

99、t;　　}　　}　　}　　void creat(Bitree *&T)　　{<p&

100、gt;　　int i,k,D[1000],n,j;　　Bitree *p,*q,*R,*S,*G;　　printf("\t請輸入數(shù)據(jù)個數(shù):");　　scanf("%d",&n);　　getchar();

101、　　for(i=0;i<n;i++)　　{　　printf("\t第%d個數(shù)據(jù):",i+1);　　scanf("%d",&D[i]);　　}&

102、lt;/b>　　inistall(D,n);　　for(i=0;i<n;i++)　　{　　if(i==0)　　{</b

103、>　　p=q=T=(Bitree *)malloc(sizeof(Bitree));　　p->data=D[i];　　p->left=p->right=NULL;　　B(T);<p

104、>　　continue;　　}　　q=(Bitree *)malloc(sizeof(Bitree));　　q->data=D[i];　　q->left=q->right=

105、NULL;　　p=T;　　while(p!=NULL)　　{　　G=p;　　if(D[i]>p->dat

106、a)　　p=p->right;　　else　　p=p->left;　　}　　if(D[i]>G->data)

107、　　G->right=q;　　else　　G->left=q;　　B(T);　　deal(T,D[i]);

108、;　　}//for　　}　　void WritetoText(Bitree *t) /*將所有記錄寫入文件*/ 　　{ 　　FILE *fp; /*定義文件指針*/</

109、p>　　Bitree *temp;　　queue q;　　int s;　　inistall(q);　　push(*t,q);

110、　　fp=fopen("d:\\二叉平衡樹.txt","w"); /*打開文件*/ 　　while(!empty(q))　　{　　pop(temp,q);　　printf("%d &q

111、uot;,temp->data);　　s=temp->data;　　fprintf(fp,"%d\n",s);　　if(temp->left)　　push(*temp->left,q);

112、　　if(temp->right)　　push(*temp->right,q);　　}　　fclose(fp); /*關閉文件*/　　printf("\n\t\t\tSuccessed!\n"); /*

113、返回成功信息*/ 　　} 　　void show()　　{　　printf("\t**************************************************\n

114、");　　printf("\n");　　printf("\t\t\t請二叉平衡樹的實現(xiàn)\n");　　printf("\n");　　printf("\t*********************

115、*****************************\n");　　printf("\t注：請輸入任意不重復的數(shù)字，本程序會先轉換為二叉排序樹\n");　　printf("\t 再轉化為二叉平衡樹經(jīng)層次遍歷輸出并保存到D盤的文件中\(zhòng)n");<b&g

116、t;　　}　　void main()　　{　　Bitree *T;　　queue qq;　　show();</

117、b>　　loop:creat(T);　　printf("\t生成的平衡二叉樹為:");　　travel(T);　　WritetoText(T);　　goto loop;<p&

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

二叉平衡樹的實現(xiàn)---數(shù)據(jù)結構課程設計

文檔簡介

溫馨提示

最新文檔

評論

二叉平衡樹的實現(xiàn)---數(shù)據(jù)結構課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載