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

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設計報告</p><p><b>　　（二叉樹的遍歷）</b></p><p>　　系 別： 計算機工程系 </p><p>　　班 級： 11計應 </p><p>　　學 號：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、t;　　p是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。 先將p入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為p，出棧，訪問p->data，再中序遍歷p的右子樹。</p><p>　　后序：是按照左右根的方式進行訪問</p><p>　　p是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點的左右子樹是否均遍歷過。 可采用標記

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

21、子樹就將它放入隊列;</p><p>　　如果該元素有左子樹就將它放入隊列;</p><p><b>　　三．測試數(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)文件使用說明</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("請輸入二叉樹各結(jié)點的值和編號\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("請輸入二叉樹各結(jié)點的值和編號\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為一個棧，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棧存放樹中結(jié)點</p><p>　　int s2[

41、100],top=0,b; //s2棧存放進棧標志</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、第一次進棧標志為</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; //第二次進棧標志為</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("遞歸排序為:\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>　　二．定義和關鍵函數(shù)</b></p><p><b>　　定義二叉樹node</

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

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

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

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