數據結構課程設計報告--帶父親節(jié)點的平衡二叉樹的建立

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：19 大?。?07.50KB 人氣指數：12 舉報 版權申訴

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

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

文檔簡介

1、　　課程設計報告　　課程設計名稱：數據結構課程設計　　課程設計題目：帶父親節(jié)點的平衡二叉樹的建立　　院（系）：計算機學院　　專業(yè)：網絡工程　　班級：

2、　　學號：　　姓名： 　　指導教師： 　　目錄　　1

3、課程設計介紹1　　1.1 課程設計內容1　　1.2課程設計要求1　　2 課程設計原理2　　2.1 課設題目粗略分析2　　2.2 原理圖介紹2　　2.2.1 功能模塊圖2&

4、lt;/p>　　2.2.2 流程圖分析3　　3 數據結構分析8　　3.1 存儲結構8　　3.2 算法描述8　　4 調試與分析10　　4.1 調試過程10<p

5、>　　4.1程序執(zhí)行過程11　　參考文獻12　　附錄（關鍵部分程序清單）13　　1 課程設計介紹　　1.1 課程設計內容　　設計程序，

6、建立帶有父親結點的平衡二叉樹，系統(tǒng)主要功能是：從鍵盤上輸入一整數序列，建立一顆平衡二叉樹。　　1.2課程設計要求　　要能夠形象方便的觀察樹的結構；　　要能夠形象的演示樹的平衡過程；　　課程設計報告必須符合課程設計報告規(guī)范；</p

7、>　　提交合格的報告后，經指導老師測試程序后，課設完成。　　2 課程設計原理　　2.1 課設題目粗略分析　　根據課設題目要求，我將整體程序分為四大模塊，這四個模塊相互獨立，沒有任何嵌套調用的情況，以下是四個模塊的大體分析：

8、　　(1)判斷模塊：在插入一個關鍵字時，首先先對該關鍵字進行判斷，如果該關鍵字已經存在則不插入，否則插入該關鍵字，調用函數InsertAVL（）。　　(2)左子樹插入模塊：如果判斷完的新關鍵字插在左子樹上，則對該以指針p所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針p指向新的根結點，調用函數LeftProcess（）。　　(3

9、)右子樹插入模塊：如果判斷完的新關鍵字插在右子樹上，則對該以指針p所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針p指向新的根結點，調用函數RightProcess（）。　　(4)輸出模塊：對建立完成的平衡二叉樹輸出，輸出格式為二叉樹的括號表示，且每一步插入操作對應一次輸出，最后做一次總體輸出，調用函數，DispBSTree（）。

10、;　　2.2 原理圖介紹　　主函數主要實現(xiàn)的功能是函數調用，主函數首先對輸入的關鍵字進行判斷，調用函數InsertAVL（），若該關鍵字在已建樹中已經存在，則返回主函數接著對下一個關鍵字進行判斷。若該關鍵字在已建樹中不存在，則插入該數，若插入左子樹中則調用函數LeftProcess（）進行插入操作，若插入右子樹中則調用函數DispBSTree（）進行插入操作。當所有的關鍵字都

11、插入完事之后，進行輸出，調用函數，DispBSTree（）。　　2.2.1 功能模塊圖　　1.判斷模塊 　　若在平衡二叉排序樹b中不存在和e有相同關鍵字的結點，則插入一個數據元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉處理，布爾變量t

12、aller反映b長高與否。　　2.左子樹插入模塊　　對以指針p所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針p指向新的根結點，插入分三種情況：原本左右子樹等高，現(xiàn)因左子樹增高而使樹增；原本右子樹比左子樹高，現(xiàn)左右子樹等高；原本左子樹比右子樹高，須作左子樹的平衡處理。若新關鍵字插入在*p的左孩子的左子樹上，要

13、做LL調整，若新關鍵字插入在*p的左孩子的右子樹上，要做LR調整。　　3.右子樹子樹插入模塊　　對以指針p所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針p指向新的根結點，插入分三種情況：原本左右子樹等高，現(xiàn)因右子樹增高而使樹增；原本左子樹比右子樹高，現(xiàn)左右子樹等高；原本右子樹比左子樹高，須作右子樹的平衡處理。若新關鍵字插入在*p的右孩子的右子樹

14、上，要做RR調整，若新關鍵字插入在*p的右孩子的左子樹上，要做RL調整。　　2.2.2 流程圖分析　　1．主函數流程圖　　主函數主要實現(xiàn)的功能是函數調用，主函數首先對輸入的關鍵字進行判斷，若該關鍵字在已建樹中已經存在，則返回主函數接著對下一個關鍵字進行判斷。若該關鍵字在已建樹

15、中不存在，則插入該數，當所有的關鍵字都插入完事之后，進行輸出。流程圖如圖2.1所示。　　圖2.1 主函數流程圖　　2．判斷模塊流程圖　　若在平衡二叉排序樹b中不存在和e有相同關鍵字的結點，則插入一個數據元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則

16、作平衡旋轉處理，布爾變量taller反映b長高與否。流程圖如圖2.2所示。　　圖2.2 判斷模塊流程圖　　3．左子樹插入模塊流程圖 　　斷完的新關鍵字插在左子樹上，則對該以指針p所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針p指向新的根結針。流程圖如圖2.3所示。

17、;　　圖2.3左子樹插入模塊流程圖　　4．右子樹插入模塊流程圖　　斷完的新關鍵字插在右子樹上，則對該以指針p所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針p指向新的根結針。流程圖如圖2.4所示。　　圖2.4 右子樹插入模塊流程圖　　3 數據結

18、構分析　　3.1 存儲結構　　定義一個關鍵字類型的字符數組，其空間足夠大，用來存放關鍵字。　　3.2 算法描述　　1．判斷關鍵字算法如下：<p&g

19、t;　　{//若在平衡二叉排序樹b中不存在和e有相同關鍵字的結點，則插入一個數據元素為e的新結點，　　if(b==NULL) //原樹為空，插入新結點，樹長高，置taller為1　　{b=(BSTNode*)malloc(sizeof(BSTNode));　　b->key=e;<

20、/b>　　b->lchild=b->rchild=NULL;　　b->bf=0;　　taller=1;}　　else　　{if(e

21、==b->key) //樹中已存在和e有相同關鍵字的結點則不插入　　{taller=0;　　return 0;}　　if(e<b->key) //繼續(xù)在*b的左子樹中進行搜索　　{if((InsertAVL(b->lchild,e

22、,taller))==0) //未插入　　return 0;　　if(taller==1) //已插入到*b的左子樹中且左子樹長高　　LeftProcess(b,taller);}　　else

23、 //繼續(xù)在*b的右子樹中進行搜索　　{if((InsertAVL(b->rchild,e,taller))==0) //未插入　　return 0;　　if(taller==1) //已插入到

24、*b的右子樹中且右子樹長高 　　RightProcess(b,taller);}}　　return 1;}　　2.左平衡處理算法如下：　　{//對以指針p所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，　　//指針p指向新的

25、根結點　　BSTNode *p1,*p2;　　if(p->bf==0) //原本左右子樹等高，現(xiàn)因左子樹增高而使樹增高　　{p->bf=1;　　taller=1;}<p&g

26、t;　　else if(p->bf==-1) //原本右子樹比左子樹高，現(xiàn)左右子樹等高　　{p->bf=0;　　taller=0;}　　else //原本左子樹比右子樹高，須作左子樹的平衡處理&

27、lt;p>　　{p1=p->lchild; //p指向*p的左子樹根節(jié)點　　if(p1->bf==1) //新結點插入在*p的左孩子的左子樹上，要做LL調整　　{p->lchild=p1->rchild;　　p1->rchild=p;

28、　　p->bf=p1->bf=0;　　p=p1; }　　else if(p1->bf==-1) //新結點插入在*p的左孩子的右子樹上，要做LR調整　　{p2=p1->rchild;　　p

29、1->rchild=p2->lchild;　　p2->lchild=p1;　　p->lchild=p2->rchild;　　p2->rchild=p;　　if(p2->bf==0) //新結點插入在*p2處作為葉子結點的

30、情況　　p->bf=p1->bf=0;　　else if(p2->bf==1) /新結點插在*p2的左子樹上的情況　　{p1->bf=0;　　p->bf=-1;}　　else /

31、/新結點插在*p2的右子樹上的情況　　{p1->bf=1;　　p->bf=0;}　　p=p2;　　p->bf=0; //仍將p指向新的根結點，并置其bf值

32、為0 　　taller=0;}　　}　　4 調試與分析　　4.1 調試過程　　在調試程序是主要遇到一下幾類問題：&

33、lt;/p>　　本程序用到指針的地方特別多，由于指針那部分知識我掌握的不是很好，故而在這方面有困難。后來我通過在圖書館查資料、看書解決了這方面問題。　　對二叉樹的左右子樹進行插入調整的操作時，由于考慮問題不夠全面而導致輸出結果出現(xiàn)錯誤，在查質料重新學習二叉樹后，解決了此問題。　　4.1程序執(zhí)行過程</b

34、>　　圖4.1 第一組輸入執(zhí)行結果　　圖4.2 第二組輸入執(zhí)行結果　　參考文獻　　[1] 嚴蔚敏.吳偉民.數據結構[M].北京：清華大學出版社，2007.　　[2] 張長海.陳娟.C程序

35、設計[M].北京：高等教育出版社，2004. 　　[3] 譚浩強.C程序設計[M].北京：清華大學出版社，2005.　　[4] 徐孝凱.數據結構實用教程.[M].北京：清華大學出版社，2006.　　[5] 張秉權.數據結構（C語言描述）.[M].北京：中國輕工業(yè)出版社，2004.<p

36、>　　附錄（關鍵部分程序清單）　　程序代碼　　#include<stdio.h>　　#include<malloc.h>　　typedef int KeyType<p&

37、gt;　　typedef struct node　　{KeyType key;　　int bf;　　struct node *lchild,*rchild;　　}BSTNode;

38、;　　void LeftProcess(BSTNode *&p,int &taller)　　{ /*對以指針p所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時指針p指向新結點*/　　BSTNode *p1,*p2;<p

39、>　　if(p->bf==0)　　{p->bf=1;　　taller=1;　　}　　else if(p->bf==-1)</p&

40、gt;　　{p->bf=0;　　taller=0;　　}　　else　　{p1=p->

41、lchild　　if(p1->bf==1)　　{p->lchild=p1->rchild;　　p1->rchild=p;　　p->bf=p1->bf=0;　　p=p1;<

42、/b>　　}　　else if(p1->bf==-1)　　{p2=p1->rchild;　　p1->rchild=p2->lchild;　　p2->lchi

43、ld=p1;　　p->lchild=p2->rchild;　　p2->rchild=p;　　if(p2->bf==0)　　p->bf=p1->bf=0;　　else if(p2->bf==

44、1)　　{p1->bf=0;　　p->bf=-1;　　}　　else　　{p1->bf=1;<

45、;/p>　　p->bf=0;　　}　　p=p2;　　p->bf=0;<b&

46、gt;　　}　　taller=0;　　}　　}　　void RightProcess(BSTNode *&p,int &t

47、aller)　　{ /*對以指針p所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針p指向新的根結點*/　　BSTNode *p1,*p2;　　if(p->bf==0)　　{p-

48、>bf=-1;　　taller=1;　　}　　else if(p->bf==1)　　{p->bf=0;<p&g

49、t;　　taller=0;　　}　　else　　{p1=p->rchild;　　if(p1->bf==-1)<p&g

50、t;　　{p->rchild=p1->lchild;　　p1->lchild=p;　　p->bf=p1->bf=0;　　p=p1;　　}<

51、;p>　　else if(p1->bf==1)　　{p2=p1->lchild;　　p1->lchild=p2->rchild;　　p2->rchild=p1;　　p->rchild=p2->lchild;

52、;　　p2->lchild=p;　　if(p2->bf==0)　　p->bf=p1->bf=0;　　else if(p2->bf==-1)　　{p1->bf=0;<b

53、>　　p->bf=1;　　}　　else　　{p1->bf=-1;　　p->bf=0;&l

54、t;p>　　}　　p=p2;　　p->bf=0;　　taller=0;　　}</b&

55、gt;　　}　　int InsertAVL(BSTNode*&b,KeyType e,int &taller)　　{ /*若在平衡二叉排序樹b中不存在和e有相同關鍵字的結點，則插入一

56、個數據元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉處理，布爾變taller　　反映b長高與否*/　　if(b==NULL)　　{b=(BSTNode*)malloc(sizeof(BSTNode));<p&

57、gt;　　b->key=e;　　b->lchild=b->rchild=NULL;　　b->bf=0;　　taller=1;<b

58、>　　}　　else　　{if(e==b->key)　　{taller=0;　　return 0;　　}

59、　　if(e<b->key)　　{if((InsertAVL(b->lchild,e,taller))==0)　　return 0;　　if(taller==1)<p

60、>　　LeftProcess(b,taller);　　}　　else 　　{if((InsertAVL(b->rchild,e,taller))==0)　　retur

61、n 0;　　if(taller==1)　　RightProcess(b,taller);　　}　　}　　return

62、 1;　　}　　void DispBSTree(BSTNode *b)　　{ /*以括號表示法輸出AVL*/　　if(b!=NULL)

63、　　{printf("%d",b->key);　　if(b->lchild!=NULL||b->rchild!=NULL)　　{printf("(");　　DispBSTree(b->lchild);<

64、;p>　　if(b->rchild!=NULL)printf(",");　　DispBSTree(b->rchild);　　printf(")");　　}

65、}　　}　　int main()　　{　　BSTNode *b=NULL;　　int i,j;&

66、lt;/p>　　KeyType a[]={6,1,2,3,4,5,0,7,8,9},n=10;　　printf("創(chuàng)建一棵AVL樹:\n");　　for(i=0;i<n;i++)　　{printf("第%d步，插入%d元素:",i+1,a[

67、i]);　　InsertAVL(b,a[i],j);　　DispBSTree(b);　　printf("\n");　　}　　printf("AVL:")

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

溫馨提示

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

數據結構課程設計報告--帶父親節(jié)點的平衡二叉樹的建立

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計報告--帶父親節(jié)點的平衡二叉樹的建立

文檔簡介

溫馨提示

最新文檔

評論

免費下載