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

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p><b>　?。ǘ鏄?shù)的遍歷）</b></p><p>　　系 別： 計(jì)算機(jī)工程系 </p><p>　　班 級(jí)： 11計(jì)應(yīng) </p><p>　　學(xué) 號(hào)：

2、 </p><p>　　姓 名： </p><p>　　指導(dǎo)老師： </p><p>　　完成日期： 2012/6/27 </p><p><b>　　目錄 </b></

3、p><p>　　一．課程設(shè)計(jì)的目的、要求、內(nèi)容、功能1</p><p>　　一．課程設(shè)計(jì)的目的1</p><p>　　二、課程設(shè)計(jì)的基本要求1</p><p>　　三、課程設(shè)計(jì)內(nèi)容2</p><p>　　四、實(shí)現(xiàn)什么功能2</p><p>　　二．基本算法的原理3</p>

4、<p><b>　　一．流程圖3</b></p><p><b>　　二．思想4</b></p><p><b>　　三．測(cè)試數(shù)據(jù)6</b></p><p>　　四．源程序及系統(tǒng)文件使用說(shuō)明9</p><p><b>　　一．源程序9</b&

5、gt;</p><p>　　二．定義和關(guān)鍵函數(shù)15</p><p><b>　　五．心得體會(huì)16</b></p><p><b>　　六．教師點(diǎn)評(píng)17</b></p><p>　　一．課程設(shè)計(jì)的目的、要求、內(nèi)容、功能</p><p><b>　　一．課程設(shè)計(jì)的

6、目的</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程。 </p><p>　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問(wèn)題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)它們進(jìn)行處

7、理。通過(guò)課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過(guò)此次課程設(shè)計(jì)主要達(dá)到以下目的：</p><p>　　1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　2.初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　3.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立

8、分析和解決問(wèn)題的能力；</p><p>　　4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　二、課程設(shè)計(jì)的基本要求</p><p>　　1. 問(wèn)題分析和任務(wù)定義：</p><p>　　根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？（而不是怎么做？）限制條件

9、是什么？ </p><p><b>　　2. 邏輯設(shè)計(jì)：</b></p><p>　　對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明)，各個(gè)主要模塊的算法，并畫(huà)出模塊之間的調(diào)用關(guān)系圖；</p>&l

10、t;p><b>　　3. 詳細(xì)設(shè)計(jì)：</b></p><p>　　定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫(xiě)出各函數(shù)的偽碼算法。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)一試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫(xiě)出函數(shù)形式的算法框架；</p>&

11、lt;p><b>　　4. 程序編碼：</b></p><p>　　把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；</p><p>　　5. 程序調(diào)試與測(cè)試：</p><p>　　采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過(guò)修改程序來(lái)證

12、實(shí)它或繞過(guò)它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成案例格式和風(fēng)格良好的源程序清單和結(jié)果；</p><p><b>　　三、課程設(shè)計(jì)內(nèi)容</b></p><p><b>　　二叉樹(shù)遍歷算法集成</b></p><p><b>　　功能要求：</b></p><p>　　界面友

13、好，易與操作?？刹捎貌藛位蚱渌藱C(jī)對(duì)話方式進(jìn)行選擇。</p><p>　　實(shí)現(xiàn)各種二叉樹(shù)的遍歷。包括先序遍歷、中序遍歷、后序遍歷的遞歸和非遞歸算法。</p><p>　　演示程序以人機(jī)對(duì)話的形式進(jìn)行。每次測(cè)試完畢正確顯示各種遍歷序列。</p><p>　　在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以

14、提出算法的改進(jìn)方法；</p><p><b>　　四、實(shí)現(xiàn)什么功能</b></p><p>　　該程序?qū)崿F(xiàn)二叉樹(shù)的遍歷 </p><p>　　二叉樹(shù)的遍歷是指按照一定的規(guī)則訪問(wèn)二叉樹(shù)的各個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)都被且只被訪問(wèn)一次。二叉樹(shù)遍歷的實(shí)質(zhì)是將非線性結(jié)構(gòu)的數(shù)據(jù)線性化的過(guò)程，二叉樹(shù)的遍歷是二叉樹(shù)的一個(gè)重要操作，許多關(guān)于二叉樹(shù)的操作都是基于二叉樹(shù)的

15、遍歷，例如查找二叉樹(shù)中具有某種特征的結(jié)點(diǎn)或?qū)Χ鏄?shù)中得全部結(jié)點(diǎn)逐一進(jìn)行處理等操作。二叉樹(shù)的遍歷根據(jù)訪問(wèn)的規(guī)則不同，可以分為先序遍歷、中序遍歷、后序遍歷、層次遍歷四種訪問(wèn)方式。</p><p><b>　　二．基本算法的原理</b></p><p><b>　　一．流程圖</b></p><p><b>　　二．思

16、想</b></p><p>　　二叉樹(shù)是有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，或者一個(gè)根結(jié)點(diǎn)和兩棵不相交的二叉樹(shù)組成其中一棵叫做左子樹(shù)，另一棵叫做右子樹(shù)。</p><p><b>　　思想：</b></p><p><b>　　遞歸</b></p><p>　　先序：是按照根左右的方式進(jìn)

17、行訪問(wèn)</p><p>　　中序：是按照左根右的方式進(jìn)行訪問(wèn)</p><p>　　后序：是按照左右根的方式進(jìn)行訪問(wèn)</p><p><b>　　非遞歸</b></p><p>　　先序：是按照根左右的方式進(jìn)行訪問(wèn)</p><p>　　p是要遍歷樹(shù)的根指針，若p != NULL 對(duì)于非遞歸算法，引

18、入棧模擬遞歸工作棧，初始時(shí)棧為空。 方法1：訪問(wèn)p->data后，將p入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T，出棧，再先序遍歷p的右子樹(shù)。 方法2：訪問(wèn)p->data后，將p->rchild入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為p->rchild，出棧，遍歷以該指針為根</p><p>　　中序：是按照左根右的方式進(jìn)行訪問(wèn)</p><p&g

19、t;　　p是要遍歷樹(shù)的根指針，中序遍歷要求在遍歷完左子樹(shù)后，訪問(wèn)根，再遍歷右子樹(shù)。 先將p入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為p，出棧，訪問(wèn)p->data，再中序遍歷p的右子樹(shù)。</p><p>　　后序：是按照左右根的方式進(jìn)行訪問(wèn)</p><p>　　p是要遍歷樹(shù)的根指針，后序遍歷要求在遍歷完左右子樹(shù)后，再訪問(wèn)根。需要判斷根結(jié)點(diǎn)的左右子樹(shù)是否均遍歷過(guò)。 可采用標(biāo)記

20、法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志top一同入棧(0：遍歷左子樹(shù)前的現(xiàn)場(chǎng)保護(hù)，1：遍歷右子樹(shù)前的現(xiàn)場(chǎng)保護(hù))。 首先將p和top(為0)入棧，遍歷左子樹(shù)；返回后，修改棧頂top為1，遍歷右子樹(shù)；最后訪問(wèn)根結(jié)點(diǎn)。</p><p>　　層次：用一個(gè)隊(duì)列保存被訪問(wèn)的當(dāng)前節(jié)點(diǎn)的左右孩子以實(shí)現(xiàn)層遍歷。</p><p>　　從隊(duì)列取出一個(gè)元素并訪問(wèn);</p><p>　　如果該元素有右

21、子樹(shù)就將它放入隊(duì)列;</p><p>　　如果該元素有左子樹(shù)就將它放入隊(duì)列;</p><p><b>　　三．測(cè)試數(shù)據(jù)</b></p><p><b>　　輸入第一組數(shù)據(jù)</b></p><p><b>　　輸出</b></p><p><b>

22、;　　輸入第二組數(shù)據(jù)</b></p><p><b>　　輸出</b></p><p><b>　　輸入第三組數(shù)據(jù)</b></p><p><b>　　輸出</b></p><p><b>　　輸入第四組數(shù)據(jù)</b></p>&l

23、t;p><b>　　輸出</b></p><p><b>　　輸入第五組數(shù)據(jù)</b></p><p><b>　　輸出</b></p><p>　　四．源程序及系統(tǒng)文件使用說(shuō)明</p><p><b>　　一．源程序</b></p>&

24、lt;p>　　#include "stdio.h"</p><p>　　#define maxsize 100 </p><p>　　struct node</p><p>　　{char data;</p><p>　　node *ld,*rd;};</p><p>　　node *chua

25、ngjian()</p><p>　　{node *q[maxsize];</p><p><b>　　node *s;</b></p><p><b>　　char n;</b></p><p><b>　　int i,j;</b></p><p>　

26、　printf("請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的值和編號(hào)\n");</p><p>　　scanf("%d%c",&i,&n);</p><p>　　while(i!=0 && n!='$')</p><p>　　{s=new node;</p><p>　　s-&

27、gt;data=n;</p><p>　　s->ld=NULL;</p><p>　　s->rd=NULL;</p><p><b>　　q[i]=s;</b></p><p><b>　　if(i!=1)</b></p><p><b>　　{j=i/

28、2;</b></p><p>　　if(i%2==0)</p><p>　　q[j]->ld=s;</p><p><b>　　else</b></p><p>　　q[j]->rd=s;}</p><p>　　//printf("請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的值和編號(hào)\n

29、");</p><p>　　scanf("%d%c",&i,&n);}</p><p>　　return(q[1]);}</p><p>　　void xianxu(node *bt)</p><p>　　{if(bt!=NULL)</p><p>　　{printf(&q

30、uot;%c",bt->data);</p><p>　　xianxu(bt->ld);</p><p>　　xianxu(bt->rd);}}</p><p>　　void zhongxu(node *bt)</p><p>　　{if(bt!=NULL)</p><p>　　{zhong

31、xu(bt->ld);</p><p>　　printf("%c",bt->data);</p><p>　　zhongxu(bt->rd);}}</p><p>　　void houxu(node *bt)</p><p>　　{if(bt!=NULL)</p><p>　　{h

32、ouxu(bt->ld);</p><p>　　houxu(bt->rd);</p><p>　　printf("%c",bt->data);}}</p><p>　　void cengci(node *bt)</p><p>　　{node *q[maxsize],*p;</p><

33、p>　　int front,rear;</p><p><b>　　front=0;</b></p><p><b>　　rear=0;</b></p><p>　　if(bt!=NULL)</p><p>　　{rear=(rear+1)%maxsize;</p><p&

34、gt;　　q[rear]=bt;}</p><p>　　while(front!=rear)</p><p>　　{front=(front+1)%maxsize;</p><p>　　p=q[front];</p><p>　　printf("%c",p->data);</p><p>　　

35、if(p->ld!=NULL)</p><p>　　{rear=(rear+1)%maxsize;</p><p>　　q[rear]=p->ld;}</p><p>　　if(p->rd!=NULL)</p><p>　　{rear=(rear+1)%maxsize;</p><p>　　q[rea

36、r]=p->rd;</p><p><b>　　}}}</b></p><p>　　void fdgxx(node *root)</p><p>　　{ node *p,*s[100];</p><p>　　int top=0; //top為棧頂指針</p><p><b>　　

37、p=root;</b></p><p>　　while((p!=NULL)||(top>0))</p><p>　　{ while(p!=NULL)</p><p>　　{printf("%c",p->data);</p><p>　　s[++top]=p; p=p->ld;

38、 }</p><p>　　p=s[top--]; p=p->rd; }}</p><p>　　void fdgzx( node *root)</p><p>　　{ node *p,*s[100]; //s為一個(gè)棧，top為棧頂指針</p><p>　　int top=0;</p><p><

39、;b>　　p=root;</b></p><p>　　while((p!=NULL)||(top>0)) </p><p>　　{ while(p!=NULL)</p><p>　　{s[++top]=p;p=p->ld;}</p><p>　　{p=s[top--];</p><p>

40、;　　printf("%c",p->data);</p><p>　　p=p->rd; } }}</p><p>　　void fdghx( node *root)</p><p>　　{ node *p,*s1[100]; //s1棧存放樹(shù)中結(jié)點(diǎn)</p><p>　　int s2[

41、100],top=0,b; //s2棧存放進(jìn)棧標(biāo)志</p><p><b>　　p=root;</b></p><p><b>　　do</b></p><p>　　{ while(p!=NULL)</p><p>　　{s1[top]=p;s2[top++]=0; //

42、第一次進(jìn)棧標(biāo)志為</p><p><b>　　p=p->ld;}</b></p><p><b>　　if(top>0)</b></p><p>　　{b=s2[--top];</p><p>　　p=s1[top];</p><p><b>　　if(

43、b==0)</b></p><p>　　{s1[top]=p;s2[top++]=1; //第二次進(jìn)棧標(biāo)志為</p><p><b>　　p=p->rd;}</b></p><p><b>　　else</b></p><p>　　{printf("%c",p

44、->data);</p><p>　　p=NULL;}}}while(top>0);}</p><p>　　void main()</p><p><b>　　{</b></p><p>　　node *bt;</p><p>　　bt=chuangjian();</p>

45、<p>　　printf("遞歸排序?yàn)?\n");</p><p>　　printf("先序遍歷為：");</p><p>　　xianxu(bt);</p><p>　　printf("\n中序遍歷為：");</p><p>　　zhongxu(bt);</p&

46、gt;<p>　　printf("\n后序遍歷為：");</p><p>　　houxu(bt);</p><p>　　printf("\n");</p><p>　　printf("非遞歸遍歷為:\n");</p><p>　　printf("先序遍歷為:&

47、quot;);</p><p>　　fdgxx(bt);</p><p>　　printf("\n中序遍歷為：");</p><p>　　fdgzx(bt);</p><p>　　printf("\n后序遍歷為：");</p><p>　　fdghx(bt);</p>

48、<p>　　printf("\n層次遍歷為：");</p><p>　　cengci(bt);</p><p>　　printf("\n");}</p><p><b>　　二．定義和關(guān)鍵函數(shù)</b></p><p><b>　　定義二叉樹(shù)node</

49、b></p><p>　　并建立二叉樹(shù)chuangjian</p><p><b>　　二叉樹(shù)的遞歸算法</b></p><p>　　先序遍歷xianxu</p><p>　　中序遍歷zhongxu</p><p><b>　　后序遍歷Houxu</b></p&g

50、t;<p><b>　　二叉樹(shù)的非遞歸算法</b></p><p><b>　　先序遍歷fdgxx</b></p><p><b>　　中序遍歷fdgzx</b></p><p><b>　　后序遍歷fdghx</b></p><p>　　二

51、叉樹(shù)的層次遍歷算法</p><p>　　層次遍歷cengci</p><p><b>　　主函數(shù)Mai</b></p><p>　　該函數(shù)在輸入過(guò)程中輸入“0”或“$”結(jié)束。</p><p><b>　　五．心得體會(huì)</b></p><p>　　兩個(gè)星期的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)終于

52、完了，自己也松了一口氣，今年的數(shù)據(jù)結(jié)構(gòu)比起去年的C語(yǔ)言程序設(shè)計(jì)我感覺(jué)難多了，讓我覺(jué)得很無(wú)力，學(xué)得不是怎么好，一直都感到很迷茫，似懂非懂的，就好像是屬于半吊子，沒(méi)有學(xué)好它感到很遺憾</p><p>　　經(jīng)過(guò)兩個(gè)星期的課程設(shè)計(jì)，自己努力的研究了一下，感到這兩個(gè)星期還是弄懂了好一些，</p><p>　　只是好像并不是很多，主要是現(xiàn)在的程序一般都很長(zhǎng)，很多算法又不會(huì)，很多東西都是模模糊糊的，才導(dǎo)