數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----二叉樹(shù)的應(yīng)用

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：17 大小：140.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　信息科學(xué)與技術(shù)學(xué)院　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告　　目錄　　1、課程設(shè)計(jì)的目的、課程設(shè)計(jì)題目、題目要求2　　1.1課程設(shè)計(jì)的目的3　　1.2課程設(shè)計(jì)的題目

2、3　　1.3題目要求3　　2課程設(shè)計(jì)的實(shí)驗(yàn)報(bào)告內(nèi)容:4　　3課程設(shè)計(jì)的原程序代碼:4　　4運(yùn)行結(jié)果16　　5. 課程設(shè)計(jì)總結(jié)21</p&g

3、t;　　6參考書(shū)目22　　1課程設(shè)計(jì)的目的　　1.1課程設(shè)計(jì)的目的:　　通過(guò)以前的學(xué)習(xí)以及查看相關(guān)資料,按著題目要求編寫(xiě)程序,進(jìn)一步加強(qiáng)對(duì)編程的訓(xùn)練,使得自己掌握一些將書(shū)本知識(shí)轉(zhuǎn)化為實(shí)際應(yīng)用當(dāng)中.在整個(gè)程序中,主要

4、應(yīng)用的是鏈表,但是也運(yùn)用了類.通過(guò)兩種方法解決現(xiàn)有問(wèn)題.　　1.2課程設(shè)計(jì)的題目: 二叉樹(shù)的應(yīng)用　　1.3題目要求:　　建立二叉樹(shù)的二叉鏈表存儲(chǔ)算法　　二叉樹(shù)的先序遍歷，中序遍歷和后序遍歷輸出

5、　　非遞歸的先序遍歷，中序遍歷　　二叉樹(shù)的層次遍歷　　判斷此二叉樹(shù)是否是完全二叉樹(shù)　　二叉樹(shù)的左右孩子的交換　　2課程設(shè)計(jì)的實(shí)驗(yàn)報(bào)告內(nèi)容:　　通過(guò)遞歸對(duì)二叉樹(shù)進(jìn)行遍歷。二叉樹(shù)的非遞歸遍歷主要采

6、用利用隊(duì)進(jìn)行遍歷。此后的判斷此二叉樹(shù)是否是完全二叉樹(shù)也才采用隊(duì)，而二叉樹(shù)的左右孩子的交換則采用的是一個(gè)簡(jiǎn)單的遞歸。　　3課程設(shè)計(jì)的原程序代碼:　　#include<iostream>　　using namespace std;　　#define MAXSIZE

7、 100　　int sign=0;　　void menu();　　//　　typedef struct BiTNode　　{<

8、;p>　　char data;　　BiTNode *left_child,*right_child;　　}BiTNode,*BiTree;　　int CreateBiTree(BiTree &T)//創(chuàng)建二叉樹(shù)　　{ char ch;

9、　　cout<<"請(qǐng)輸入數(shù)據(jù)（#為結(jié)束）: ";　　cin>>ch;　　if(ch=='#') T=NULL;　　else<

10、p>　　{ 　　if(!(T=new BiTNode)){ 　　cout<<"Overflow!";//no alloction　　return 0;

11、　　}　　T->data=ch;　　CreateBiTree(T->left_child);//create leftchild　　CreateBiTree(T->right_child); //create rightchild

12、　　}　　return 1;　　}　　//判斷此樹(shù)是否是完全二叉樹(shù)　　int LevelOrder1(BiTree &T)<

13、/p>　　{　　BiTree stack[MAXSIZE];　　BiTreep;　　int front,rear;　　front=-1,rear=0;</p&

14、gt;　　stack[rear]=T;　　while(rear!=front)　　{　　front++;　　p=stack[front];　　if((p->

15、left_child==NULL)&&(p->right_child))　　sign=1;　　if(p->left_child)　　{　　rear++;</

16、p>　　stack[rear]=p->left_child;　　}　　if(p->right_child)　　{　　rear++;<

17、/b>　　stack[rear]=p->right_child;　　}　　}　　return 1;&l

18、t;b>　　}　　void Output(BiTree &T) //輸出二叉樹(shù)　　{　　if(!T) {　　cout<<"空樹(shù)!\n&qu

19、ot;;　　return ;　　} //空樹(shù)　　cout<<T->data<<" ";// 輸出根結(jié)點(diǎn)　　if(T->left_child)

20、Output(T->left_child); //輸出左子樹(shù)　　if(T->right_child)Output(T->right_child);//輸出右子樹(shù)　　}　　int Depth(BiTree &T) //求樹(shù)深&l

21、t;p>　　{　　int i,j;　　if(!T) return 0;　　i = Depth(T->left_child);　　j = Depth(T->right_child)

22、;　　return (i>j?i:j) + 1;　　}　　int Node(BiTree &T)//求結(jié)點(diǎn)數(shù)　　{　　if(!T) retu

23、rn 0;　　return 1+Node(T->left_child)+Node(T->right_child);　　}　　int Leaf(BiTree &T) //求葉子結(jié)點(diǎn)　　{</b

24、>　　if(!T) return 0;　　if(!T->left_child&&!T->right_child) return 1;//僅有根結(jié)點(diǎn)　　return Leaf(T->left_child)+Leaf(T->right_child);//返回葉子結(jié)點(diǎn)的數(shù)目

25、　　}　　void PreOrder(BiTree &T) //先序遍歷算法 DLR　　{　　if(!T) return ; //遞歸調(diào)用的結(jié)束條件

26、;　　cout<<T->data<<" "; // 訪問(wèn)根結(jié)點(diǎn)的數(shù)據(jù)域　　PreOrder(T->left_child);//先序遞歸遍歷T的左子樹(shù)　　PreOrder(T->right_child);//先序遞歸遍歷T的右子樹(shù)　　}

27、　　void InOrder(BiTree &T)//中序遍歷算法 LDR　　{　　if(!T) return ;　　InOrder(T->left_child);<p&

28、gt;　　cout<<T->data<<" ";　　InOrder(T->right_child);　　}　　void PostOrder(BiTree &T)//后序遍歷算法 LRD&l

29、t;p>　　{　　if(!T) return ;　　PostOrder(T->left_child);　　PostOrder(T->right_child);　　cout<<T->data<&

30、lt;" ";　　}　　//非遞歸先序遍歷　　int NRPreOrder(BiTree &T)　　{BiTree stack[100],p;&

31、lt;p>　　int top;　　if(T==NULL)　　return 1;　　top=-1;　　p=T;<

32、;/p>　　while(!(p==NULL&&top==-1)){　　while(p!=NULL){　　cout<<p->data<<" ";　　if(top<100-1)

33、　　{　　top++;　　stack[top]=p;　　}　　else{　　c

34、out<<"棧溢出"<<endl;　　return 0;　　}　　p=p->left_child;　　}&l

35、t;/p>　　if(top==-1)　　return 1;　　else{　　p=stack[top];　　top--;</p

36、>　　p=p->right_child;　　}　　}　　return 1;}　　//非遞歸中序遍歷&

37、lt;p>　　int NRInOrder(BiTree &T)　　{BiTree stack[100],p;　　int top;　　if(T==NULL)　　return 1;<

38、;/p>　　top=-1;　　p=T;　　while(!(p==NULL&&top==-1)){　　while(p!=NULL){　　if(top<

39、;100-1)　　{　　top++;　　stack[top]=p;　　}　　else{</b

40、>　　cout<<"棧溢出"<<endl;　　return 0;　　}　　p=p->left_child;<p

41、>　　}　　if(top==-1)　　return 1;　　else{　　p=stack[top];　　cou

42、t<<p->data<<" ";　　top--;　　p=p->right_child;　　}　　}&l

43、t;/p>　　return 1;}　　//層次遍歷　　void LevelOrder(BiTree &T)　　{BiTree queue[100];　　int front,rear;</p&g

44、t;　　if(T==NULL)　　return;　　front=-1;　　rear=0;　　queue[rear]=T;</p&g

45、t;　　while(front!=rear){　　front++;　　cout<<queue[front]->data<<" ";　　if(queue[front]->left_child!=NUL

46、L){　　rear++;　　queue[rear]=queue[front]->left_child;　　}　　if(queue[front]->right_child!=NULL)&

47、lt;/p>　　{　　rear++;　　queue[rear]=queue[front]->right_child;　　}&

48、lt;b>　　}　　}　　//*******************************左右子樹(shù)交換*****************************　　/*將結(jié)點(diǎn)的左右子樹(shù)交換*/　　/*BiT

49、Node *swap(BiTNode &T)　　{ 　　BiTNode *t,*t1,*t2; 　　if(T==NULL) t=NULL; 　　else <p

50、>　　{ 　　t=(BiTNode *)malloc(sizeof(BiTNode)); 　　t->data=T->data; 　　t1=swap(T->left_child); 　　t2=swap(T->

51、;right_child); 　　t->left_child=t2; 　　t->right_child=t1; 　　} 　　return(t); 　　}<

52、/b>　　void print(BiTNode &T) 　　{ 　　if(T!=NULL) 　　{ 　　printf("%

53、c",T->data); 　　if(T->left_child!=NULL||T->right_child!=NULL) 　　{ 　　printf("("); 　　print(b

54、->left_child); 　　if(b->right_child!=NULL)printf(", "); 　　print(b->right_child); 　　printf(")");

55、;　　} 　　} 　　}*/　　int PreOrderTraverse(BiTree T)　　{ <

56、p>　　if(!T)　　return 0;　　BiTree t;　　if (T->left_child||T->right_child)

57、　　{　　t=T->left_child;　　T->left_child=T->right_child;　　T->right_child=t;　　}

58、　　PreOrderTraverse(T->left_child);　　PreOrderTraverse(T->right_child);　　return 0;　　}

59、;　　//菜單　　void menu()　　{ cout<<"*****************************************************************************"<<endl;

60、　　cout<<"<< （主菜單） >>"<<endl;　　cout<<"********************************************************

61、*********************"<<endl;　　cout<<"<< 0.建立二叉樹(shù) >>"<<endl;　　cout<<&

62、quot;<< 1.二叉樹(shù)樹(shù)深 >>"<<endl;　　cout<<"<< 2.二叉樹(shù)結(jié)點(diǎn)數(shù)

63、 >>"<<endl;　　cout<<"<< 3.二叉樹(shù)的葉子結(jié)點(diǎn) >>"<<endl;　　cout<<"<<

64、; 4.二叉樹(shù)的先序遍歷 >>"<<endl;　　cout<<"<< 5.二叉樹(shù)的中序遍歷 >>"

65、;<<endl;　　cout<<"<< 6.二叉樹(shù)的后序遍歷 >>"<<endl;　　cout<<"<<

66、 7.二叉樹(shù)的非遞歸先序遍歷 >>"<<endl;　　cout<<"<< 8.二叉樹(shù)的非遞歸中序遍歷 >>"<<endl;

67、;　　cout<<"<< 9.二叉樹(shù)的層次遍歷 >>"<<endl;　　cout<<"<< 10.判斷

68、此樹(shù)是否是完全二叉樹(shù) >>"<<endl;　　cout<<"<< 11.左右孩子交換 >>"<<endl;　　cout&

69、lt;<"<< 12.退出 >>"<<endl;　　cout<<"************************************************************

70、*****************"<<endl;　　}　　//主函數(shù)　　void main()　　{ &l

71、t;p>　　int br,a;　　BiTree T;　　br=CreateBiTree(T);　　while(1){　　menu();

72、　　cout<<"請(qǐng)輸入選擇的命令-->";　　cin>>a;　　if(a>=0||a<=12)　　{</p

73、>　　switch (a){　　case 0:　　{cout<<"建立后的二叉樹(shù)為：\n";　　Output(T);　　cout<<endl;}

74、;　　system("pause");break;　　case 1:　　cout<<"該樹(shù)的樹(shù)深為: "<<Depth(T)<<endl;　　system("pause

75、");break;　　case 2:　　cout<<"該樹(shù)的結(jié)點(diǎn)數(shù)："<<Node(T)<<endl;　　system("pause");break;

76、;　　case 3:　　cout<<"該樹(shù)的葉子結(jié)點(diǎn)為："<<Leaf(T)<<endl;　　system("pause");break;　　case 4:<

77、;/p>　　{cout<<"該樹(shù)以先序遍歷輸出為：\n";　　PreOrder(T);　　cout<<endl;}　　system("pause");break;

78、　　case 5:　　{cout<<"該樹(shù)以中序遍歷輸出為:\n";　　InOrder(T);　　cout<<endl;}　　system("pause");break;

79、;　　case 6:　　{cout<<"該樹(shù)以后序遍歷輸出為：\n";　　PostOrder(T);　　cout<<endl;}　　system("pause

80、");break;　　case 7:　　{cout<<"該樹(shù)的非遞歸先序遍歷輸出為:\n";　　NRPreOrder(T);　　cout<<endl;}&l

81、t;p>　　system("pause");break;　　case 8:　　{cout<<"該樹(shù)的非遞歸中序遍歷輸出為:\n";　　NRInOrder(T);　　cout&l

82、t;<endl;}　　system("pause");break;　　case 9:　　{cout<<"該樹(shù)的層次遍歷：\n";　　LevelOrder(T);</p&g

83、t;　　cout<<endl;}　　system("pause");break;　　case 10:　　{　　LevelOrder1(T);&

84、lt;/p>　　if(sign==1)　　{　　cout<<"這不是一個(gè)完全二叉樹(shù)。"<<endl;　　}<

85、b>　　else 　　cout<<"這是一個(gè)完全二叉樹(shù)。"<<endl;　　//break;　　}　　system("

86、;pause");break;　　case 11:PreOrderTraverse(T);　　cout<<"左右孩子已經(jīng)替換成功"<<endl;break;　　case 12:exit(-1);　　}

87、　　}　　}　　}　　4運(yùn)行結(jié)果:　　4. 1用二叉鏈表創(chuàng)

88、建二叉樹(shù)：　　4.2主菜單 　　4.3求二叉樹(shù)樹(shù)深：　　4.4二叉樹(shù)結(jié)點(diǎn)數(shù):　　4.5二叉樹(shù)的中序遍歷:　　4.6二叉樹(shù)的層次遍歷：　　4.7左右孩子

89、交換：　　4.8左右孩子交換后的中序遍歷：　　4.9左右孩子交換后的層次遍歷：　　5. 課程設(shè)計(jì)總結(jié)：此次課程設(shè)計(jì)使我對(duì)書(shū)本的知識(shí)有進(jìn)一步了解。同時(shí)也是我知道自己的一些不足，這次課程設(shè)計(jì)我是在書(shū)本與同學(xué)的幫助下完成的。它并不難，但是我沒(méi)有自己獨(dú)自完成是我的錯(cuò)誤。<b

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----二叉樹(shù)的應(yīng)用

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----二叉樹(shù)的應(yīng)用

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載