數(shù)據(jù)結(jié)構(gòu)-二叉樹的遍歷與其結(jié)點(diǎn)的計算-課程設(shè)計-實驗報告

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計</p><p>　　設(shè)計題目：二叉樹的遍歷及其相關(guān)結(jié)點(diǎn)的計算</p><p><b>　　目 錄</b></p><p>　　第一章 課程與設(shè)計的目的與意義1</p><p>　　1.1課題設(shè)計目的1</p><p>　　1.2課題設(shè)計意

2、義1</p><p>　　第二章 需求分析1</p><p>　　2.1課程設(shè)計題目、任務(wù)及要求1</p><p>　　2.2課程設(shè)計思想1</p><p>　　第三章 二叉樹的基本概述1</p><p>　　3.1 二叉樹相關(guān)概念1</p><p>　　3.2二叉樹的性質(zhì)2<

3、;/p><p>　　3.3 二叉樹的存儲2</p><p>　　第四章：系統(tǒng)的概要設(shè)計3</p><p>　　4.1 二叉樹的生成過程3</p><p>　　4.2 主要功能模塊設(shè)計3</p><p>　　第五章：系統(tǒng)詳細(xì)設(shè)計4</p><p>　　5.1 主函數(shù)菜單模塊4</p&

4、gt;<p>　　5.2 二叉樹的生成6</p><p>　　5.3 層次遍歷模塊8</p><p>　　5.4 求其相關(guān)結(jié)點(diǎn)的總數(shù)10</p><p>　　第六章 測試結(jié)果12</p><p><b>　　第七章 總結(jié)14</b></p><p>　　第八章 參考文獻(xiàn)1

5、5</p><p>　　第一章 課程與設(shè)計的目的與意義</p><p>　　1.1課題設(shè)計目的：（1）：掌握數(shù)據(jù)結(jié)構(gòu)分析設(shè)計思想及其存儲表示方法和技術(shù)。</p><p>　?。?）：掌握基于特定數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)實現(xiàn)方法和設(shè)計。</p><p>　?。?）：掌握工程化程序設(shè)計方法、技術(shù)及過程。</p><p>　　1.2

6、課題設(shè)計意義：（1）：學(xué)會怎樣團(tuán)隊協(xié)作去解決問題，增強(qiáng)自身的自信心、主動性思考能力以及自主學(xué)習(xí)的能力。</p><p>　?。?）：對課程設(shè)計這門課有更深的了解，通過這次的課題設(shè)計來提升對編程的興趣，更加努力的學(xué)習(xí)這門課。</p><p>　　（3）：通過課程設(shè)計的實踐，在程序設(shè)計方法、上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)的嚴(yán)格訓(xùn)練。</p><p><

7、;b>　　第二章 需求分析</b></p><p>　　2.1課程設(shè)計題目、任務(wù)及要求</p><p>　　（1）對二叉樹作各種遍歷,輸出結(jié)果；</p><p>　?。?）求得二叉樹結(jié)點(diǎn)的總數(shù)和葉子結(jié)點(diǎn)的數(shù)目；</p><p>　?。?）要求二叉樹的操作結(jié)果完整的輸出</p><p><b>

8、;　　2.2課程設(shè)計思想</b></p><p>　?。?）建立二叉樹采用一個一個輸入的方式。</p><p>　?。?）對二叉樹分別實現(xiàn)多種遍歷的方式。</p><p>　?。?）編寫算法實現(xiàn)求結(jié)點(diǎn)和其葉子的數(shù)目。</p><p>　　第三章 二叉樹的基本概述</p><p>　　3.1 二叉樹相關(guān)概念&

9、lt;/p><p>　　定義：二叉樹是n（>=0）個借點(diǎn)的有限集，它或者是空集（n=0），或者由一個根結(jié)點(diǎn)及兩顆互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。</p><p>　　這也是一個遞歸定義。二叉樹可以是空集，因此，根可以有空的左子樹或右子樹，或者左、右子樹皆為空。因此，二叉樹有五種基本形態(tài)，如下圖1所示：</p><p>　　圖3.1 二叉樹的

10、五種基本形態(tài)</p><p>　　滿二叉樹：一顆深度為k且有2^k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。</p><p>　　完全二叉樹：若一顆二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。</p><p><b>　　3.2二叉樹的性質(zhì)</b></p>

11、<p>　　二叉樹具有以下重要性質(zhì)：</p><p>　　性質(zhì)1 二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2^（i-1）（i>=1）。</p><p>　　性質(zhì)2 深度為k的二叉樹至多有2^k-1（k>=1）個結(jié)點(diǎn)。</p><p>　　性質(zhì)3 在任意一顆二叉樹中，若終端結(jié)點(diǎn)的個數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。</p>&

12、lt;p>　　性質(zhì)4 具有n個結(jié)點(diǎn)的完全二叉樹的深度為└log2n┘+1（或┌l(fā)og2（n+1） ┐）。</p><p>　　3.3 二叉樹的存儲</p><p><b>　　1.順序存儲結(jié)構(gòu)</b></p><p>　　該方法是把二叉樹的所有結(jié)點(diǎn)，按照一定的次序順序，存儲到一片連續(xù)的存儲單元中。因此，必須把結(jié)點(diǎn)安排成一個適當(dāng)?shù)木€性

13、序列，使得結(jié)點(diǎn)在這個序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。</p><p><b>　　2.鏈?zhǔn)酱鎯Y(jié)構(gòu)</b></p><p>　　從上面的介紹可知：順序方式存儲一般二叉樹將浪費(fèi)存儲空間，并且若在樹中需要經(jīng)常插入和刪除結(jié)點(diǎn)時，由于大量地移動結(jié)點(diǎn)，順序存儲變的不可取。因此，存儲樹的最自然的方法是鏈接的方法。二叉樹的每個結(jié)點(diǎn)最多有兩個孩子，用鏈接方式存儲二叉樹時，

14、每個結(jié)點(diǎn)除了存儲結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子，相應(yīng)的類型說明為：</p><p>　　typedef char datatype;</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　da

15、tatype data;</p><p>　　struct node *lchild,*rchild;</p><p><b>　　}bitree;</b></p><p>　　第四章：系統(tǒng)的概要設(shè)計</p><p>　　4.1 二叉樹的生成過程</p><p>　　二叉樹的生成，采用逐個建立的方

16、式，如圖：</p><p><b>　　否</b></p><p><b>　　否</b></p><p>　　圖4.1 二叉樹的生成過程</p><p>　　4.2 主要功能模塊設(shè)計</p><p>　　程序主要設(shè)計了五個功能：首先是創(chuàng)建二叉排序樹，完成后出現(xiàn)任務(wù)菜單，菜單

17、中設(shè)計了四個模塊：退出，三種遍歷，計算結(jié)點(diǎn)總數(shù)和葉子結(jié)點(diǎn)數(shù)目。</p><p><b>　　主函數(shù)流程如下：</b></p><p><b>　　三種遍歷</b></p><p><b>　　Switch()</b></p><p><b>　　Switch()<

18、;/b></p><p><b>　　退出</b></p><p>　　圖4.2 主函數(shù)流程圖</p><p>　　第五章：系統(tǒng)詳細(xì)設(shè)計</p><p>　　5.1 主函數(shù)菜單模塊</p><p>　　該模塊功能主要是給用戶提供清晰的可操作界面，易于人機(jī)操作，并能很好的調(diào)用其他各模塊，使程序

19、更加優(yōu)化，絲路更加清晰，結(jié)構(gòu)更加明了，提高了程序的實用性。其算法如下：</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int i,j,m,n;</p><p>　　bitree t,*s;</p><p><b>　　while(

20、j)</b></p><p><b>　　{</b></p><p>　　printf("\t\t輸入1創(chuàng)建二叉樹\n</p><p>　　\t\t輸入2前序遍歷\n</p><p>　　\t\t輸入3中序遍歷\n</p><p>　　\t\t輸入4后序遍歷\n</p&

21、gt;<p>　　\t\t輸入5求結(jié)點(diǎn)總數(shù)\n</p><p>　　\t\t輸入6求葉子結(jié)點(diǎn)數(shù)\n");</p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)</b></p><p><b>　　{</b&g

22、t;</p><p>　　case 1:s=creatbitree(&t);break;</p><p>　　case 2:printf("前序遍歷結(jié)果為:");preorder(s);printf("\n");break;</p><p>　　case 3:printf("中序遍歷結(jié)果為:");i

23、norder(s);printf("\n");break;</p><p>　　case 4:printf("后序遍歷結(jié)果為:");postorder(s);printf("\n");break;</p><p>　　case 5:m=sum(s);printf("該二叉樹的結(jié)點(diǎn)數(shù)為:%d\n",m);brea

24、k;</p><p>　　case 6:n=yzjd(s);printf("該二叉樹的葉子結(jié)點(diǎn)數(shù)為:%d\n",n);break;</p><p><b>　　}</b></p><p>　　printf("\t\t輸入1繼續(xù)\n\t\t輸入0退出\n");</p><p>　　s

25、canf("%d",&j);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　圖5.1主函數(shù)算法的實現(xiàn)結(jié)果

26、 </p><p>　　5.2 二叉樹的生成</p><p>　　二叉樹的生成乃是討論如何在內(nèi)存中建立二叉樹的存儲結(jié)構(gòu)。建立順序存儲結(jié)構(gòu)的問題簡單，在這里討論如何建立二叉鏈表。下面介紹按完全二叉樹的層次順序，依次輸入結(jié)點(diǎn)信息

27、建立二叉鏈表的算法：</p><p>　　bitree *creatbitree(bitree *root)</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p><b>　　int i,j;</b></p>

28、<p>　　bitree *s,*p[20];</p><p>　　printf("請分別輸入結(jié)點(diǎn)的編號和其元素，然后輸入0結(jié)束創(chuàng)建\n");</p><p>　　scanf("%d%c",&i,&ch);</p><p>　　while(i!=0)</p><p><

29、b>　　{</b></p><p>　　s=(bitree *)malloc(sizeof(bitree));</p><p>　　s->data=ch;</p><p>　　s->lchild=NULL;</p><p>　　s->rchild=NULL;</p><p><

30、b>　　p[i]=s;</b></p><p><b>　　if(i==1)</b></p><p><b>　　root=s;</b></p><p><b>　　else</b></p><p><b>　　{</b></p&g

31、t;<p><b>　　j=i/2;</b></p><p>　　if(i%2==0)</p><p>　　p[j]->lchild=s;</p><p><b>　　else</b></p><p>　　p[j]->rchild=s;</p><p&g

32、t;<b>　　}</b></p><p>　　scanf("%d%c",&i,&ch);</p><p><b>　　}</b></p><p>　　return(root);</p><p>　　圖5.2 二叉樹生成算法的實現(xiàn)結(jié)果</p><

33、;p>　　5.3 層次遍歷模塊</p><p>　　二叉樹的定義是遞歸的，一棵非空的二叉樹是由根結(jié)點(diǎn)、左子樹、右子樹這三個基本部分組成的，因此，便利一棵非空的二叉樹的問題可以分解三個子問題：訪問根結(jié)點(diǎn)；遍歷左子樹；遍歷右子樹。于是就分為三種遍歷方式，其算法如下：</p><p>　　void inorder(bitree *t)</p><p><b&g

34、t;　　{</b></p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　inorder(t->lchild);</p><p>　　printf("%c",t->data);</p>&

35、lt;p>　　inorder(t->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void preorder(bitree *t)</p><p><b>　　{</b></p>

36、<p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　printf("%c",t->data);</p><p>　　preorder(t->lchild);</p><p>　　preorder(t->r

37、child);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void postorder(bitree *t)</p><p><b>　　{</b></p><p><b>　　if(t

38、)</b></p><p><b>　　{</b></p><p>　　postorder(t->lchild);</p><p>　　postorder(t->rchild);</p><p>　　printf("%c",t->data);</p><

39、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　圖5.3 二叉樹遍歷算法的實現(xiàn)結(jié)果</p><p>　　5.4 求其相關(guān)結(jié)點(diǎn)的總數(shù)：</p><p>　　結(jié)點(diǎn)是構(gòu)成樹的基本結(jié)構(gòu)，葉子結(jié)點(diǎn)是指那些度為零的結(jié)點(diǎn)。結(jié)點(diǎn)的類型和相關(guān)算法如下：</p>

40、;<p><b>　　類型說明：</b></p><p>　　typedef char datatype;</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　datatype data;</p><

41、;p>　　struct node *lchild,*rchild;</p><p><b>　　}bitree;</b></p><p><b>　　算法描述：</b></p><p>　　int sum(bitree *t)</p><p><b>　　{</b><

42、;/p><p>　　static int i=0;</p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　sum(t->lchild);</p><p><b>　　i++;</b></p&g

43、t;<p>　　sum(t->rchild);</p><p><b>　　}</b></p><p>　　return(i);</p><p><b>　　}</b></p><p>　　int yzjd(bitree *t)</p><p><b

44、>　　{</b></p><p>　　static int i=0;</p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　yzjd(t->lchild);</p><p>　　if(t->l

45、child==NULL&&t->rchild==NULL)</p><p><b>　　i++;</b></p><p>　　yzjd(t->rchild);</p><p><b>　　}</b></p><p>　　return(i);</p><

46、p><b>　　}</b></p><p>　　圖5.4 求相關(guān)結(jié)點(diǎn)算法的實現(xiàn)結(jié)果</p><p><b>　　第六章 測試結(jié)果</b></p><p>　　測試的順序如圖6.1所示：</p><p>　　圖6.1 測試的順序</p><p>　　測試的結(jié)果如圖6.2所

47、示：</p><p>　　圖 6.2 測試的結(jié)果</p><p><b>　　總結(jié)</b></p><p>　　通過這次課程設(shè)計我確確實實感受到了編程的樂趣，從中也學(xué)到了不少知識。我在學(xué)習(xí)運(yùn)用數(shù)據(jù)結(jié)構(gòu)編程之前，并沒能深刻體會到這一點(diǎn)，直到這次課程設(shè)計，我才有所領(lǐng)悟。</p><p>　　由于我對基本概念二叉樹和二叉排序樹

48、理解的模糊不清，導(dǎo)致這次課程設(shè)計中我也出現(xiàn)過一些錯誤。經(jīng)過多次的編寫與修改和多系的實驗，最終完成了任務(wù)，心中巨大的成就感油然而生。另外收獲了很多東西，在整個過程中，鍛煉了我們查找文獻(xiàn)，整合資源，然后吸收變成自己的東西。</p><p>　　總之，我會繼續(xù)編寫程序的，相信在越來越多的失敗與嘗試之后，自己會不斷進(jìn)步不斷提高的。</p><p><b>　　第八章 參考文獻(xiàn)</b