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

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

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

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

文檔簡介

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

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

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

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

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

6、用利用隊進(jìn)行遍歷。此后的判斷此二叉樹是否是完全二叉樹也才采用隊，而二叉樹的左右孩子的交換則采用的是一個簡單的遞歸。　　3課程設(shè)計的原程序代碼:　　#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)建二叉樹　　{ char ch;

9、　　cout<<"請輸入數(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;　　}　　//判斷此樹是否是完全二叉樹　　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) //輸出二叉樹　　{　　if(!T) {　　cout<<"空樹!\n&qu

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

20、Output(T->left_child); //輸出左子樹　　if(T->right_child)Output(T->right_child);//輸出右子樹　　}　　int Depth(BiTree &T) //求樹深&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é)點數(shù)　　{　　if(!T) retu

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

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

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

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

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>　　}　　}　　//*******************************左右子樹交換*****************************　　/*將結(jié)點的左右子樹交換*/　　/*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.建立二叉樹 >>"<<endl;　　cout<<&

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

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

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

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

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

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

68、此樹是否是完全二叉樹 >>"<<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<<"請輸入選擇的命令-->";　　cin>>a;　　if(a>=0||a<=12)　　{</p

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

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

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

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

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

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

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

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

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

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

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

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

85、b>　　else 　　cout<<"這是一個完全二叉樹。"<<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、建二叉樹：　　4.2主菜單 　　4.3求二叉樹樹深：　　4.4二叉樹結(jié)點數(shù):　　4.5二叉樹的中序遍歷:　　4.6二叉樹的層次遍歷：　　4.7左右孩子

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

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載