數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之二叉樹的遍歷

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

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

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

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告　　題目 　　學(xué)生姓名 　　學(xué) 號 　　專業(yè)班級

2、 　　指導(dǎo)老師 　　設(shè)計日期 　　指導(dǎo)老師評閱意見：　　目錄</b&g

3、t;　　問題定義································

4、;······3　　可行性分析·························

5、3;·········3-4　　調(diào)試界面······················&#

6、183;··············4-7　　錯誤分析·················

7、·····················7　　總結(jié)···········&#

8、183;·····························7-8　　附錄··&#

9、183;····································

10、·8-14　　問題定義　　1.1 課題：　　建立二叉樹，層序、先序、中序、后序遍歷（用遞歸或非遞歸的方法）以及中序線索化。　　1.2意義：<

11、/p>　　通過以前的學(xué)習(xí)以及查看相關(guān)資料，按照題目要求編寫程序，進(jìn)一步加強(qiáng)對編程的訓(xùn)練，使得自己掌握一些將書本知識轉(zhuǎn)化為實際應(yīng)用當(dāng)中去，在整個程序中，主要應(yīng)用的是鏈表，但也運(yùn)用了棧。通過兩種方法解決現(xiàn)有問題。　　1.3要求：　　要求能夠輸入樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；

12、分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)、輸出中序遍歷序列的函數(shù)、輸出后序遍歷序列的函數(shù)；實現(xiàn)二叉樹的中序線索化。　　可行性分析　　2.1 創(chuàng)建二叉樹鏈表的結(jié)點存儲結(jié)構(gòu)及數(shù)據(jù)的輸入函數(shù)　　因為每個結(jié)點所存儲的數(shù)據(jù)類型為字符串，卻

13、無法使用字符串和String等數(shù)據(jù)類型，所以使用單鏈表作為結(jié)點所存儲的數(shù)據(jù)類型。以#表示空結(jié)點。　　利用先序遍歷創(chuàng)建鏈表 　　2.1.1用單鏈表s記錄輸入的數(shù)據(jù) 　　2.1.2利用非遞歸調(diào)用分別生成根節(jié)點的左子樹和右子樹。　　2.1.3返回菜單重新選擇。

14、;　　基本程序如下：　　void CreatBiTree_q(BiTree &T)/　　{ 　　······&

15、lt;/p>　　if(ch=='#')　　T=NULL;　　else　　{　　T=(BiTree)malloc(s

16、izeof(BiTNode));　　if(!T)　　exit(0);　　T->data=ch;　　T->LTag=Link;　　T->R

17、Tag=Link;　　CreatBiTree_q(T->lchild);　　CreatBiTree_q(T->rchild);　　}　　}

18、2.2先序遍歷、中序遍歷、后序遍歷二叉鏈表。　　A 、先序遍歷：訪問根節(jié)點，左子樹，右子樹的順序。　　B、中序遍歷：訪問左子樹，根節(jié)點，右子樹的順序。　　C、后序遍歷：訪問左子樹，右子樹，根節(jié)點的順序。　　D、層次遍歷：從根結(jié)點開始，按從左至右的順序依次訪問。</p

19、>　　E、中序線索化：將二叉樹線索化，再進(jìn)行中序遍歷輸出。　　2.3主函數(shù)　　a、調(diào)用生成二叉樹的函數(shù)，從鍵盤輸入二叉樹的各個結(jié)點　　b、分別調(diào)用先序遍歷、中序遍歷、后序遍歷二叉樹的函數(shù)，輸出所有結(jié)點<

20、;b>　　顯示的菜單為：　　***********************************************　　請選擇遍歷算法　　1.按先序輸入二叉樹序列以#表示空節(jié)點　　2.先序遍歷二叉樹遞非

21、歸算法 　　3.中序遍歷二叉樹非遞歸算法　　4.后序遍歷二叉樹非遞歸算法　　5.層次遍歷二叉樹非遞歸算法　　6.中序線索遍歷二叉樹算法　　0.按0退出"<<endl

22、　請輸入序號（0，1,2,3,4,5,6）：　　三、調(diào)試界面：　　3.1調(diào)試所用二叉樹：　　A <p&g

23、t;　　B 　　C D 　　E F

24、 　　G 　　輸入的二叉樹是：ABC##DE#F##G###（#代表空結(jié)點）<p

25、>　　輸出的遍歷應(yīng)該是：先序遍歷：A B C D E F G　　中序遍歷：C B E F D G A　　后序遍歷：C B G E F D A　　層序遍歷：A B C D E F G 　　中序線索化遍歷：C B E F D G A<p&g

26、t;　　3.2程序運(yùn)行如下：　　1、菜單界面：　　2、創(chuàng)建界面：　　3、先序非遍歷二叉樹：　　4、中序非遍歷二叉樹：　　5、后序非遍歷二叉樹：</p

27、>　　6、層次遍歷二叉樹：　　7、中序線索化，中序遍歷：　　四、錯誤分析：　　1、中序線索化后，先序、中序、后序、層次遍歷均出現(xiàn)錯誤，陷入死循環(huán)，　　改正：另外編寫一個創(chuàng)建二叉樹的函數(shù)，中序線索化另外重新創(chuàng)

28、建，中序輸出函數(shù)也另外編寫　　2、中序線索化時，用到的線索在結(jié)構(gòu)體內(nèi)定義，在線索化時，顯示為未定義　　改正：直接在外部定義線索#define Link 0 和#define Thread 1　　五、總結(jié)　　實驗開始時定義結(jié)構(gòu)時，比細(xì)心

29、，總會有或多或少的問題出現(xiàn)，如數(shù)據(jù)域和指針域定義的類型不一樣，在實驗過程中總有這樣或那樣的問題，在本次實驗中，二叉樹的先序，中序，后序遍歷都是采用非遞歸調(diào)用，用起來稍微復(fù)雜，這使我更進(jìn)一步學(xué)習(xí)和理解了樹的遍歷，更靈活地運(yùn)用了指針與數(shù)組。　　附錄　　6.1源程序

30、　　#include <iostream.h>　　#include <stdio.h>　　#include <stdlib.h>　　#include <malloc.h> 　　#define Link

31、0　　#define Thread 1　　int right=0;　　typedef char TElemType;　　typedef struct BiTNode　　{

32、　　TElemType data;　　struct BiTNode *lchild,*rchild; 　　int LTag, RTag,flag;　　}BiTNode,*BiTree;　　BiTree pre;

33、　　void CreatBiTree_q(BiTree &T)　　{　　TElemType ch;　　scanf("%c",&ch);　　if(ch=='#')

34、　　T=NULL;　　else　　{　　T=(BiTree)malloc(sizeof(BiTNode));　　if(!

35、T)　　exit(0);　　T->data=ch;　　T->LTag=Link;　　T->RTag=Link;　　CreatBiTree_q(T->

36、lchild);　　CreatBiTree_q(T->rchild);　　}　　}　　void CreateBiTree(BiTree *T)<

37、;b>　　{ 　　TElemType ch;　　scanf("%c",&ch);　　if(ch=='#')　　*T=NULL;<p&g

38、t;　　else　　{　　*T=(BiTree)malloc(sizeof(BiTNode));　　if(!*T) exit(-1);　　(*T)->data=ch;

39、　　CreateBiTree(&(*T)->lchild);　　CreateBiTree(&(*T)->rchild);　　}　　}　　void P

40、reOrderTraverse(BiTree &T)　　{　　BiTree p,S[20];　　int top=-1;　　p=T; 　　do<

41、;/b>　　{　　while(p!= NULL) 　　{　　cout << p->data<<" ";<p&g

42、t;　　top++;　　S[top]=p; 　　p=p->lchild;　　}　　if( top >-1 )　　{</

43、b>　　p=S[top]; 　　top--; 　　p = p->rchild; 　　}　　}while (( p != NULL ) ||(t

44、op>-1));　　}　　int inorderTraverse(BiTree &T)　　{　　BiTree p,s[20];int i=-1;<p&g

45、t;　　p=T;　　while(p||i>-1)　　{　　if(p)　　{

46、;　　i++;　　s[i]=p;　　p=p->lchild;　　}　　else<p

47、>　　{　　p=s[i];　　cout<<" ";　　cout<<p->data;　　i--;<

48、/p>　　p=p->rchild;　　}　　}return 0;　　}　　void postorder (BiTree T){<p&

49、gt;　　int s2[20],top=0;　　BiTree p,s1[20];　　p=T;　　do {　　while (p!=NULL)

50、;　　{　　s1[top]=p; s2[top++]=0; 　　p=p->lchild;　　} 　　while(top && s2[top-1]==1)<

51、p>　　{　　top--;　　p=s1[top]; 　　cout<<" ";　　cout<<p->data; <

52、;p>　　} 　　if(top>0) 　　{ 　　s2[top-1]=1;　　p=s1[top-1]->rchild; <b&g

53、t;　　}　　}while (top>0); 　　}　　void LevelOrder(BiTree &b)　　{　　B

54、iTree qu[20];　　int front,rear;　　front=rear=-1;　　rear++;　　qu[rear]=b;　　while(front!=rear)</p&g

55、t;　　{　　front=(front+1)%20;　　b=qu[front];　　printf(" %c ",b->data);　　if(b->lchild!=NULL)<

56、/p>　　{　　rear=(rear+1)%20;　　qu[rear]=b->lchild;　　} 　　if(b->rchild!=NULL)</

57、p>　　{　　rear=(rear+1)%20;　　qu[rear]=b->rchild;　　} 　　} &l

58、t;/p>　　}　　void InThreading(BiTree p)　　{　　if(p)　　{</b&

59、gt;　　InThreading(p->lchild);　　if(!p->lchild)//前驅(qū)線索　　{　　p->LTag=Thread;　　p->lchild=pr

60、e;　　}　　if(!pre->rchild)//后繼線索　　{　　pre->RTag=Thread;　　pre->rchild=p;&

61、lt;/p>　　}　　pre=p;　　InThreading(p->rchild);　　}　　}</

62、b>　　void InOrderThreading(BiTree *Thrt,BiTree T)　　{　　if(!((*Thrt)=(BiTree)malloc(sizeof(BiTNode))))　　exit

63、(0);　　(*Thrt)->LTag=Link;　　(*Thrt)->RTag=Thread;　　(*Thrt)->rchild=(*Thrt);　　if(!T)<

64、p>　　(*Thrt)->lchild=(*Thrt);　　else　　{　　(*Thrt)->lchild=T;　　pre=(*Thrt);<p&

65、gt;　　InThreading(T);　　pre->rchild=(*Thrt);　　pre->RTag=Thread;　　(*Thrt)->rchild=pre;　　}&

66、lt;b>　　}　　void InorderTraverse_Thr(BiTree &T)　　{　　BiTree p;　　p=T->lchild;</

67、p>　　while(p!=T)p=T　　{　　while(p->LTag==Link)　　p=p->lchild;　　cout<<p->data;<

68、;p>　　while(p->RTag==Thread&&p->rchild!=T)　　{　　p=p->rchild;　　cout<<" ";　　cout<&

69、lt;p->data;　　}　　p=p->rchild;　　}　　}　　int main()</p

70、>　　{　　BiTree T,t;　　int e;　　while(e!=0)　　{

71、cout<<endl<<"請選擇遍歷算法："<<endl;　　cout<<"1.按先序輸入二叉樹序列以#表示空節(jié)點 "<<endl;　　cout<<"2.先序遍歷二叉樹遞歸算法："<<endl; </p&g

72、t;　　cout<< "3.中序遍歷二叉樹遞歸算法："<<endl;　　cout<<"4.后序遍歷二叉樹遞歸算法： "<<endl;　　cout<<"5.層次遍歷二叉樹遞歸算法"<<endl;</

73、p>　　cout<<"6.中序線索遍歷二叉樹算法"<<endl;　　cout<<"0.按0退出"<<endl;　　cout<<"請輸入序號（0，1,2,3,4,5,6）："<<endl;</

74、p>　　cin>>e;　　cout<<endl;　　if(e==1)　　{ 　　cout <&l

75、t;"按先序輸入二叉樹序列以#表示空節(jié)點： "<<endl;　　CreateBiTree(&T);　　cout<<endl;　　}　　if(e==2)</b&

76、gt;　　{　　cout << "先序遍歷遞歸算法是： "<<endl;;　　PreOrderTraverse(T);　　cout<<endl;<

77、p>　　}　　if(e==3) 　　{ 　　cout<< "中序遍歷遞歸算法是： "<<endl;;　　inorderTraverse

78、(T);　　cout<<endl;　　}　　if(e==4)　　{　　cout<<"

79、;后序遍歷的非遞歸算法是： "<<endl;　　postorder (T);　　cout<<endl;　　}　　if(e==5)<

80、;p>　　{ 　　printf("\n層次遍歷二叉樹:\n");　　LevelOrder(T);　　}　　if(e==6)</

81、p>　　{　　cout <<"按先序輸入二叉樹序列以#表示空節(jié)點： "<<endl;　　CreatBiTree_q(T);　　cout<<endl;

82、　printf("中序線索化二叉樹:\n");　　InOrderThreading(&t,T);　　printf("線索化工作已經(jīng)完成!中序遍歷二叉樹\n");　　InorderTraverse_Thr(t);　　print

83、f("\n");　　}　　}　　return 0;　　}&

84、lt;b>　　6.2 參考資料　　【1】嚴(yán)蔚敏、吳偉民主編《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學(xué)出版社 2002【2】殷人昆等著《數(shù)據(jù)結(jié)構(gòu)》（C++版）清華大學(xué)出版社 2001【3】金遠(yuǎn)平著《數(shù)據(jù)結(jié)構(gòu)》（C++描述）清華大學(xué)出版社 2005【4】許卓群等著《數(shù)據(jù)結(jié)構(gòu)與

眾賞文庫> 全部分類> 畢業(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è)計之二叉樹的遍歷

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之二叉樹的遍歷

文檔簡介

溫馨提示

最新文檔

評論

免費下載