ds課程設計報告--平衡二叉樹

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

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

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

文檔簡介

1、　　一．題目與要求　　問題提出　　編寫已個平衡二叉樹，主要是對插入一個元素導致樹不平衡的情況進處平衡化處理以及相關的處理。　　本系統涉及的知識點<p&g

2、t;　　隊列的插入，刪除，二叉樹的建立于銷毀，平衡樹的平衡化，以及C語言中基礎應用于結構等。　　功能要求　　(1).通過不斷插入的方式創(chuàng)建一棵平衡二叉樹，包括輸入結點的關鍵字和相關信息。　　(2)按要求輸出創(chuàng)建的平衡二叉樹結點，包括順序（中序）輸出和按

3、層次輸出。　　(3)插入新增的結點，若結點不存在則插入平衡二叉樹，并進行相關調整。　　(4)銷毀二叉樹。　　(5)退出 　　二．功能設計</p

4、>　　1.數據結構的定義　　typedef struct ElemType{　　KeyType Key; //鍵值類型　　char info[20];　　}ElemT

5、ype;　　Typedef struct BSTNode{　　ElemType data； 　　int bf ; //結點的平衡因子　　struct BSTNode *lchild，*rch

6、ild；//左右孩子指針　　}BSTNode，*BSTree；　　模塊圖 　　1.主程序的流程　　2.各模塊之間的層次調用 </p

7、>　　程序代碼設計　　1.調平二叉樹　　if(插入元素與當前根元素相等) 　　{ 　　printf

8、("已存在相同關鍵字的結點\n"); 　　}　　if(插入元素小于當前根元素)) 　　{　　if(插入新結點不成功)&l

9、t;b>　　return 0;　　if(插入成功) 　　switch(查看根的平衡因子) 　　{　　case +1: </p&

10、gt;　　進行左平衡處理;　　{　　檢查*T的左子樹的平衡度，并作相應平衡處理　　{　　case +1:

11、;　　令根及其左孩子的平衡因子為0;　　做右平衡處理;　　{　　BTree lc; 　　lc指向的結點左子樹根結點;<p

12、>　　rc的右子樹掛接為結點的左子樹;　　lc的右孩子為原結點; 　　原結點指向新的結點lc;　　}　　break;　　case -1:

13、 　　rd指向*T的左孩子的右子樹根　　switch(查看右孩子平衡因子) 　　{　　case +1:　　根的平衡因子為-1;&

14、lt;/p>　　根左孩子的平衡因子為0; 　　break;　　case 0:　　令根和根左孩子的平衡因子為0;　　break;&l

15、t;/p>　　case -1:　　根平衡因子為0;　　根左孩子平衡因子為1; 　　break;　　}</b

16、>　　根右孩子的平衡因子為0;　　對*T的左子樹作左旋平衡處理;　　對*T作右旋平衡處理;　　}　　break;<p&

17、gt;　　case 0: 　　令根的平衡因子為+1;　　break;　　case -1: 　　令根的平衡因子為-1;　　break;</b

18、>　　}　　}　　2.輸出：　?。?）中序輸出　　采用遞歸算法對二叉

19、樹進行遍歷。　　if（結點不為空）　　{　　If(遍歷左孩子成功）　　If（遍歷結點成功）　　If（遍歷右孩子成功）<p&g

20、t;　　返回真　　返回假　　}　　else（結點為空）　　返回假<b&

21、gt;　　(2)按層次輸出　　根據隊列先進先出的特點，先將第一層結點進隊a，對其出出隊并輸出，同時將其不為空的孩子指針入另一隊列b，當a為空時，隊b進行出對并輸出處理，將結點的不為空的左右孩子入隊a，直到b 為空............如此直到兩隊均為空。　　根節(jié)點入隊；&

22、lt;p>　　While（a，b不同時為空）　　{　　If（i為奇數）　　{　　While（a隊不空）<

23、b>　　{　　a中結點出隊并輸出；　　If（左孩子不空）　　左孩子入隊b；　　If(有孩子不空）<p&

24、gt;　　右孩子入隊b；　　}　　}　　If（i為偶數）　　{

25、　　While（b隊不空）　　{　　b中結點出隊并輸出；　　If（左孩子不空）　　左孩子入隊a；

26、;　　If(有孩子不空）　　右孩子入隊a；　　}　　}　　I++;// 同時記錄樹的深度&

27、lt;/p>　　}　　3.銷毀二叉樹　　銷毀二叉樹的算法根據遞歸遍歷而來，算法大體相識。　　If(根節(jié)點不空）

28、　{　　If（左子樹不空）　　銷毀左子樹；　　If（右子樹不空）　　銷毀右子樹；

29、　　銷毀相對根節(jié)點；　　根節(jié)點賦空；//留下來以便再次創(chuàng)建二叉樹時使用　　}　　4.退出　　退出時詢問是否確認退出，確認則退出，否則返回

30、到主菜單　　調試分析　　遇到的問題：　　1）對平衡二叉樹的刪除的算法設計程序存在很大問題。刪除節(jié)點后需要對新的排序樹平衡化，改變節(jié)點的信息，使之形成一棵新的平衡二叉樹。　?。?）主函數中的實參和子

31、函數中的實參相等，造成調用該子函數時，雖然沒有錯誤，但其功能不能正確的實現。改變該變量后程序成功實現各種功能。　?。?）一些邏輯邏輯運算符書寫不正確，造成實現的功能不正確或程序死循環(huán)。　　2.用戶手冊　　1.了解程序清單上給出的功能，并根據提示依次進行操作。

32、;　　2.創(chuàng)建二叉樹，輸入的數據元素為整數，當輸入-123時，停止創(chuàng)建。并顯示平衡二叉樹的中序凹入樹形圖。　　3.查找（輸入你要查找的元素）。　　4.插入（輸入要插入的數據元素，并輸出）　　5.刪除（刪除指定的元素，并輸出）　　6.

33、結束　　說明：其中每一個功能實現后都會提示是否繼續(xù)：選擇y繼續(xù)，否則，終止。　　3.測試過程　　1.創(chuàng)建平衡二叉樹：（中序凹入輸出）　　2.查找<

34、p>　　查找成功或失敗時：　　3.插入　　4.刪除,結束　　五．課程設計總結　　由于指針處理不當，調試過程中經常出

35、現指針出錯的情況，導致程序終止，經過仔細修改后才得以改正。在程序整體設計過程中，由于忽視&的作用而導致程序無法正常運行。通過此次課程設計，讓我對數據結構的重要學習內容有了更加深刻的了解，同時也意識到自己還存在很大的不足，還有很多的知識需要完善。在編程的過程中錯誤時在所難免的，處了要修改錯誤外還有了解錯誤的原因。而不是僅僅修改而已。　　六．參考文獻&l

36、t;/p>　　[1] 數據結構（C語言版）嚴蔚寬吳偉民編著　　[2] C語程序設計白燕尹業(yè)安編著　　七.附錄：程序清單　　#include<stdio.h>　　#include&l

37、t;stdlib.h>　　#define ERROR 0　　#define TRUE 1　　#define OK 1　　#define FALSE 0　　#define LH 1

38、#define RH -1　　#define EH 0　　#define EQ(a,b) ((a)==(b))　　#define LT(a,b) ((a)<(b))　　#define LQ(a,b) ((a)<=(b))

39、;　　typedef int KeyType;　　typedef struct ElemType　　{　　KeyType Key;　　char info[20];　　}ElemType;<

40、;/p>　　typedef struct BSTNode　　{　　ElemType data;　　int bf;　　struct BSTNode *lchild,

41、*rchild;　　}BSTNode,*BSTree;　　typedef struct QNode　　{　　BSTree e;　　struct QNode

42、 *next;　　}QNode,*QNodeP;　　typedef struct 　　{ 　　QNodeP front;　　QNodeP rear;

43、　}LinkQueue;　　void CreatBalanceTree(BSTree &T);　　void R_Rotate(BSTree &p);　　void L_Rotate(BSTree &p);　　int InsertAVL(BSTree

44、&T,ElemType e);　　void LeftBalance(BSTree &T);　　void RightBalance(BSTree &T);　　int Print_Mid(BSTree T);　　int Visit(BSTree T);

45、　　int WideTraverse(BSTree T);　　void Destory(BSTree &T);　　int flag=0;　　bool taller;　　int number;//計數變量</p&g

46、t;　　void main()　　{　　BSTree T=NULL;　　int chose;　　ElemType e;　　printf("\n=======平衡

47、二叉樹=======\n");　　do{　　printf("||功能菜單： ||\n");　　printf("|| 1--創(chuàng)建平衡二叉樹 ||\n");　　prin

48、tf("|| 2--按要求輸出 ||\n");　　printf("|| 3--插入元素 ||\n");　　printf("|| 4--銷毀二叉樹 ||\n");　　printf("|| 5--退

49、出 ||\n");　　printf("\n請選擇：");　　do{　　scanf("%d",&chose);　　}while(flag==0&&chose

50、!=1&&chose!=5&&printf("尚未創(chuàng)建，必須先創(chuàng)建\n請選擇："));　　system("cls");　　switch(chose)　　{<

51、b>　　default:　　printf("輸入出錯\n");　　case 1:　　number=0;　　CreatBalanceTree(T);&l

52、t;/p>　　flag=1;　　system("cls");　　break;　　case 2:　　printf

53、("共有%d個結點\n",number);　　printf("有序輸出：");　　Print_Mid(T);　　printf("\n\n按層輸出：");　　WideTraverse(T);

54、　　printf("\n\n\n");　　break;　　case 3:　　printf("插入元素：\n");　　printf(&quo

55、t;請輸入關鍵字(輸入0停止)：");　　scanf("%d",&e.Key);　　flushall();　　printf("輸入相關信息(0-20字符):");　　scanf("%s",e.i

56、nfo);　　InsertAVL(T,e);　　break;　　case 4:　　printf("已銷毀平衡二叉樹\n");　　Des

57、tory(T);　　break;　　case 5:　　printf("確認退出? 1--YES 2--NO\n");　　if(scanf("%d",&a

58、mp;chose),chose==1) 　　exit(1);　　system("cls");　　}　　}while(1);<b&

59、gt;　　}　　void CreatBalanceTree(BSTree &T)　　{　　ElemType e;　　printf("\n\n創(chuàng)建平衡二叉樹\n");

60、　　printf("請輸入關鍵字(輸入0停止)：");　　scanf("%d",&e.Key);　　while(e.Key)　　{　　flushall();</

61、p>　　printf("輸入相關信息(0-20字符):");　　scanf("%s",e.info);　　printf("\n");　　if(InsertAVL(T,e))<b&

62、gt;　　number++;　　printf("請輸入關鍵字(輸入0停止)：");　　scanf("%d",&e.Key);　　}　　}</b

63、>　　int Print_Mid(BSTree T)　　{　　if(T)　　{　　if(Print_Mid(T

64、->lchild))　　if(Visit(T))　　if(Print_Mid(T->rchild))　　return OK;　　return ERROR;　　}

65、　　else return OK;　　}　　int Visit(BSTree T)　　{　　printf("%d ",T->data.Key);&

66、lt;/p>　　return OK;　　}　　int InitQueue(LinkQueue &Q)　　{　　Q.front=Q.rear=(QNodeP)ma

67、lloc(sizeof(QNode));　　if(!Q.front)　　return ERROR;　　Q.front->next=NULL;　　return OK;　　}</p&g

68、t;　　int QueueEmpty(LinkQueue Q)　　{　　if(Q.front==Q.rear)　　return TRUE;　　else return FALSE;<p

69、>　　}　　int EnQueue(LinkQueue &Q,BSTree p)　　{　　QNodeP q=NULL;　　q=(QNodeP)malloc(sizeof(QNode)

70、);　　if(!q)　　return ERROR;　　q->e=p;　　q->next=NULL;　　Q.rear->next=q;&l

71、t;/p>　　Q.rear=q;　　return OK;　　}　　int DeQueue(LinkQueue &Q,BSTree &p)

72、;　　{　　QNodeP q=NULL;　　if(Q.front==Q.rear)　　return ERROR;　　q=Q.front->next;　　p=q->e;</b&

73、gt;　　Q.front->next=q->next;　　if(!q->next)　　Q.rear=Q.front;　　free(q);　　return OK;</p&

74、gt;　　}　　int WideTraverse(BSTree T)　　{　　LinkQueue Q1,Q2;　　BSTree p=NULL;<

75、p>　　int i=1;　　InitQueue(Q1);　　InitQueue(Q2);　　printf("\n按層輸出：\n");　　if(T)

76、　　EnQueue(Q1,T);　　while((!QueueEmpty(Q1))||(!QueueEmpty(Q2)))　　{　　printf("第%d層:",i);　　if(

77、i%2)　　while(!QueueEmpty(Q1))　　{　　DeQueue(Q1,p);　　Visit(p);　　if(p-&g

78、t;lchild)　　EnQueue(Q2,p->lchild);　　if(p->rchild)　　EnQueue(Q2,p->rchild);　　}　　e

79、lse　　while(!QueueEmpty(Q2))　　{　　DeQueue(Q2,p);　　Visit(p);　　if(p->

80、;lchild)　　EnQueue(Q1,p->lchild);　　if(p->rchild)　　EnQueue(Q1,p->rchild);　　}　　printf(&quo

81、t;\n");　　i++;　　}　　printf("該樹共有%d層\n",i-1);　　return OK;

82、;　　}　　int InsertAVL(BSTree &T,ElemType e)　　{　　if(!T)　　{

83、　　T=(BSTree)malloc(sizeof(BSTNode));　　if(!T) 　　exit(ERROR);　　T->data=e;　　T->lchild=T->rchild=NULL

84、;　　T->bf=EH;　　taller=TRUE;　　}　　else 　　{</b&

85、gt;　　if(EQ(e.Key,T->data.Key))　　{　　taller=FALSE;　　printf("樹中存在此關鍵字\n");　　return ERR

86、OR;　　}　　if(LT(e.Key,T->data.Key))　　{　　if(!InsertAVL(T->lchild,e))　　retu

87、rn ERROR;　　if(taller)　　{　　switch(T->bf)　　{　　case LH:<

88、;/p>　　LeftBalance(T);　　taller=FALSE;　　break;　　case EH:　　T->bf=LH;</b&

89、gt;　　taller=TRUE;　　break;　　case RH:　　T->bf=EH;　　taller=

90、FALSE;　　break;　　}　　}　　}　　else

91、　　{　　if(!InsertAVL(T->rchild,e))　　return ERROR;　　if(taller)　　{&l

92、t;/p>　　switch(T->bf)　　{　　case LH:　　T->bf=EH;　　taller=FALSE;

93、　　break;　　case EH:　　T->bf=RH;　　taller=TRUE;　　b

94、reak;　　case RH:　　RightBalance(T);　　taller=FALSE;　　break;

95、}　　}　　}　　}　　return OK;　　}<

96、/p>　　void LeftBalance(BSTree &T)　　{　　BSTree lc=NULL,rd=NULL;　　lc=T->lchild;　　switch(lc->bf)&l

97、t;/p>　　{　　case LH:　　T->bf=lc->bf=EH;　　R_Rotate(T);　　break;&

98、lt;/p>　　case RH:　　rd=lc->rchild;　　switch(rd->bf)　　{　　case LH:</b&g

99、t;　　T->bf=RH;　　lc->bf=EH;　　break;　　case EH:　　T->b

100、f=lc->bf=EH;　　break;　　case RH:　　T->bf=EH;　　lc->bf=LH;<p

101、>　　break;　　}　　rd->bf=EH;　　L_Rotate(T->lchild);　　R_Rotate(T);

102、;　　}　　}　　void RightBalance(BSTree &T)　　{　　BSTree lc=NULL,rd=NULL;<p&g

103、t;　　rd=T->rchild;　　switch(rd->bf)　　{　　case RH:　　T->bf=rd->bf=EH;

104、　L_Rotate(T);　　break;　　case LH:　　lc=rd->lchild;　　switch(lc->bf)

105、;　　{　　case RH:　　T->bf=LH;　　rd->bf=EH;　　break;<p&

106、gt;　　case EH:　　T->bf=rd->bf=EH;　　break;　　case LH:　　T->bf=EH;&

107、lt;/b>　　rd->bf=RH;　　break;　　}　　lc->bf=EH;　　R_Rotate(T->rchild);&l

108、t;/p>　　L_Rotate(T);　　}　　}　　void R_Rotate(BSTree &p)//右旋　　{<

109、;/p>　　BSTree lc=NULL;　　lc=p->lchild;　　p->lchild=lc->rchild;　　lc->rchild=p;　　p=lc;

110、　　}　　void L_Rotate(BSTree &p)　　{　　BSTree rc=NULL;　　rc=p->rchild;<

111、p>　　p->rchild=rc->lchild;　　rc->lchild=p;　　p=rc;　　}　　void Destory(BSTree &T)</p&

112、gt;　　{　　if(T)　　{　　if(T->lchild)　　Destory(T->lchild);

113、　　if(T->rchild)　　Destory(T->rchild);　　free(T);//必須先銷毀左右孩子　　T=NULL;　　}

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

溫馨提示

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

ds課程設計報告--平衡二叉樹

文檔簡介

溫馨提示

最新文檔

評論

ds課程設計報告--平衡二叉樹

文檔簡介

溫馨提示

最新文檔

評論

免費下載