二叉樹的遍歷與其結點的計算課程設計

1、<p>　　數 據 結 構 課 程 設 計</p><p>　　設計題目：二叉樹的遍歷及其相關結點的計算</p><p>　　學生姓名： </p><p>　　專業(yè)班級： </p><p>　　指導教師： </p&

2、gt;<p>　　完成時間： </p><p>　　信息工程 院 信息科學 系</p><p>　　課程設計成績評定表(本科)</p><p><b>　　目 錄</b></p><p>　　第一章 課程與設計的目的與意義1</p><p&

3、gt;　　1.1課題設計目的1</p><p>　　1.2課題設計意義1</p><p>　　第二章 需求分析1</p><p>　　2.1課程設計題目、任務及要求1</p><p>　　2.2課程設計思想1</p><p>　　第三章 二叉樹的基本概述1</p><p>　　3.1

4、 二叉樹相關概念1</p><p>　　3.2二叉樹的性質2</p><p>　　3.3 二叉樹的存儲2</p><p>　　第四章：系統(tǒng)的概要設計3</p><p>　　4.1 二叉樹的生成過程3</p><p>　　4.2 主要功能模塊設計3</p><p>　　第五章：系統(tǒng)詳細

5、設計4</p><p>　　5.1 主函數菜單模塊4</p><p>　　5.2 二叉樹的生成6</p><p>　　5.3 層次遍歷模塊8</p><p>　　5.4 求其相關結點的總數10</p><p>　　第六章 測試結果12</p><p><b>　　第七章 總

6、結14</b></p><p>　　第八章 參考文獻15</p><p>　　第一章 課程與設計的目的與意義</p><p>　　1.1課題設計目的：（1）：掌握數據結構分析設計思想及其存儲表示方法和技術。</p><p>　?。?）：掌握基于特定數據結構的基本運實現方法和設計。</p><p>　?。?/p>

7、3）：掌握工程化程序設計方法、技術及過程。</p><p>　　1.2課題設計意義：（1）：學會怎樣團隊協(xié)作去解決問題，增強自身的自信心、主動性思考能力以及自主學習的能力。</p><p>　?。?）：對課程設計這門課有更深的了解，通過這次的課題設計來提升對編程的興趣，更加努力的學習這門課。</p><p>　?。?）：通過課程設計的實踐，在程序設計方法、上機操作等

8、基本技能和科學作風方面受到比較系統(tǒng)的嚴格訓練。</p><p><b>　　第二章 需求分析</b></p><p>　　2.1課程設計題目、任務及要求</p><p>　?。?）對二叉樹作各種遍歷,輸出結果；</p><p>　?。?）求得二叉樹結點的總數和葉子結點的數目；</p><p>　　

9、（3）要求二叉樹的操作結果完整的輸出</p><p><b>　　2.2課程設計思想</b></p><p>　　（1）建立二叉樹采用一個一個輸入的方式。</p><p>　?。?）對二叉樹分別實現多種遍歷的方式。</p><p>　　（3）編寫算法實現求結點和其葉子的數目。</p><p>　　

10、第三章 二叉樹的基本概述</p><p>　　3.1 二叉樹相關概念</p><p>　　定義：二叉樹是n（>=0）個借點的有限集，它或者是空集（n=0），或者由一個根結點及兩顆互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。</p><p>　　這也是一個遞歸定義。二叉樹可以是空集，因此，根可以有空的左子樹或右子樹，或者左、右子樹皆為空。因此，二叉樹

11、有五種基本形態(tài)，如下圖1所示：</p><p>　　圖3.1 二叉樹的五種基本形態(tài)</p><p>　　滿二叉樹：一顆深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹。</p><p>　　完全二叉樹：若一顆二叉樹至多只有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。</p><

12、p><b>　　3.2二叉樹的性質</b></p><p>　　二叉樹具有以下重要性質：</p><p>　　性質1 二叉樹第i層上的結點數目最多為2^（i-1）（i>=1）。</p><p>　　性質2 深度為k的二叉樹至多有2^k-1（k>=1）個結點。</p><p>　　性質3 在任意一顆二叉樹

13、中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1。</p><p>　　性質4 具有n個結點的完全二叉樹的深度為└log2n┘+1（或┌l(fā)og2（n+1） ┐）。</p><p>　　3.3 二叉樹的存儲</p><p><b>　　1.順序存儲結構</b></p><p>　　該方法是把二叉樹的

14、所有結點，按照一定的次序順序，存儲到一片連續(xù)的存儲單元中。因此，必須把結點安排成一個適當的線性序列，使得結點在這個序列中的相互位置能反映出結點之間的邏輯關系。</p><p><b>　　2.鏈式存儲結構</b></p><p>　　從上面的介紹可知：順序方式存儲一般二叉樹將浪費存儲空間，并且若在樹中需要經常插入和刪除結點時，由于大量地移動結點，順序存儲變的不可取。因

15、此，存儲樹的最自然的方法是鏈接的方法。二叉樹的每個結點最多有兩個孩子，用鏈接方式存儲二叉樹時，每個結點除了存儲結點本身的數據外，還應設置兩個指針域lchild和rchild，分別指向該結點的左孩子和右孩子，相應的類型說明為：</p><p>　　typedef char datatype;</p><p>　　typedef struct node</p><p>

16、<b>　　{</b></p><p>　　datatype data;</p><p>　　struct node *lchild,*rchild;</p><p><b>　　}bitree;</b></p><p>　　第四章：系統(tǒng)的概要設計</p><p>　　4.1

17、 二叉樹的生成過程</p><p>　　二叉樹的生成，采用逐個建立的方式，如圖：</p><p><b>　　否</b></p><p><b>　　否</b></p><p>　　圖4.1 二叉樹的生成過程</p><p>　　4.2 主要功能模塊設計</p>

18、<p>　　程序主要設計了五個功能：首先是創(chuàng)建二叉排序樹，完成后出現任務菜單，菜單中設計了四個模塊：退出，三種遍歷，計算結點總數和葉子結點數目。</p><p><b>　　主函數流程如下：</b></p><p><b>　　三種遍歷</b></p><p><b>　　Switch()</b

19、></p><p><b>　　Switch()</b></p><p><b>　　退出</b></p><p>　　圖4.2 主函數流程圖</p><p>　　第五章：系統(tǒng)詳細設計</p><p>　　5.1 主函數菜單模塊</p><p>

20、　　該模塊功能主要是給用戶提供清晰的可操作界面，易于人機操作，并能很好的調用其他各模塊，使程序更加優(yōu)化，絲路更加清晰，結構更加明了，提高了程序的實用性。其算法如下：</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int i,j,m,n;</p><p>　　bit

21、ree t,*s;</p><p><b>　　while(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中序

22、遍歷\n</p><p>　　\t\t輸入4后序遍歷\n</p><p>　　\t\t輸入5求結點總數\n</p><p>　　\t\t輸入6求葉子結點數\n");</p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)<

23、/b></p><p><b>　　{</b></p><p>　　case 1:s=creatbitree(&t);break;</p><p>　　case 2:printf("前序遍歷結果為:");preorder(s);printf("\n");break;</p>&

24、lt;p>　　case 3:printf("中序遍歷結果為:");inorder(s);printf("\n");break;</p><p>　　case 4:printf("后序遍歷結果為:");postorder(s);printf("\n");break;</p><p>　　case 5:m=s

25、um(s);printf("該二叉樹的結點數為:%d\n",m);break;</p><p>　　case 6:n=yzjd(s);printf("該二叉樹的葉子結點數為:%d\n",n);break;</p><p><b>　　}</b></p><p>　　printf("\t\t輸入1

26、繼續(xù)\n\t\t輸入0退出\n");</p><p>　　scanf("%d",&j);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　圖5.1主函數算法的實現結果

27、 </p><p>　　5.2 二叉樹的生成</p><p>　　二叉樹的生成乃是討論如何在內存中建立二叉樹的存儲結構。建立順序存

28、儲結構的問題簡單，在這里討論如何建立二叉鏈表。下面介紹按完全二叉樹的層次順序，依次輸入結點信息建立二叉鏈表的算法：</p><p>　　bitree *creatbitree(bitree *root)</p><p><b>　　{</b></p><p><b>　　char ch;</b></p>&l

29、t;p><b>　　int i,j;</b></p><p>　　bitree *s,*p[20];</p><p>　　printf("請分別輸入結點的編號和其元素，然后輸入0結束創(chuàng)建\n");</p><p>　　scanf("%d%c",&i,&ch);</p>

30、<p>　　while(i!=0)</p><p><b>　　{</b></p><p>　　s=(bitree *)malloc(sizeof(bitree));</p><p>　　s->data=ch;</p><p>　　s->lchild=NULL;</p><p&g

31、t;　　s->rchild=NULL;</p><p><b>　　p[i]=s;</b></p><p><b>　　if(i==1)</b></p><p><b>　　root=s;</b></p><p><b>　　else</b><

32、/p><p><b>　　{</b></p><p><b>　　j=i/2;</b></p><p>　　if(i%2==0)</p><p>　　p[j]->lchild=s;</p><p><b>　　else</b></p>&

33、lt;p>　　p[j]->rchild=s;</p><p><b>　　}</b></p><p>　　scanf("%d%c",&i,&ch);</p><p><b>　　}</b></p><p>　　return(root);</p&g

34、t;<p>　　圖5.2 二叉樹生成算法的實現結果</p><p>　　5.3 層次遍歷模塊</p><p>　　二叉樹的定義是遞歸的，一棵非空的二叉樹是由根結點、左子樹、右子樹這三個基本部分組成的，因此，便利一棵非空的二叉樹的問題可以分解三個子問題：訪問根結點；遍歷左子樹；遍歷右子樹。于是就分為三種遍歷方式，其算法如下：</p><p>　　void

35、 inorder(bitree *t)</p><p><b>　　{</b></p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　inorder(t->lchild);</p><p>　　

36、printf("%c",t->data);</p><p>　　inorder(t->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void preorder(bitree *t)</p&g

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

38、lchild);</p><p>　　preorder(t->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void postorder(bitree *t)</p><p><b>　　

39、{</b></p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　postorder(t->lchild);</p><p>　　postorder(t->rchild);</p><p>　　pr

40、intf("%c",t->data);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　圖5.3 二叉樹遍歷算法的實現結果</p><p>　　5.4 求其相關結點的總數：</p><p>　　結點

41、是構成樹的基本結構，葉子結點是指那些度為零的結點。結點的類型和相關算法如下：</p><p><b>　　類型說明：</b></p><p>　　typedef char datatype;</p><p>　　typedef struct node</p><p><b>　　{</b></

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

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

44、gt;<p><b>　　i++;</b></p><p>　　sum(t->rchild);</p><p><b>　　}</b></p><p>　　return(i);</p><p><b>　　}</b></p><p>

45、　　int yzjd(bitree *t)</p><p><b>　　{</b></p><p>　　static int i=0;</p><p><b>　　if(t)</b></p><p><b>　　{</b></p><p>　　yzjd(

46、t->lchild);</p><p>　　if(t->lchild==NULL&&t->rchild==NULL)</p><p><b>　　i++;</b></p><p>　　yzjd(t->rchild);</p><p><b>　　}</b>&l

47、t;/p><p>　　return(i);</p><p><b>　　}</b></p><p>　　圖5.4 求相關結點算法的實現結果</p><p><b>　　第六章 測試結果</b></p><p>　　測試的順序如圖6.1所示：</p><p>

48、;　　圖6.1 測試的順序</p><p>　　測試的結果如圖6.2所示：</p><p>　　圖 6.2 測試的結果</p><p><b>　　總結</b></p><p>　　通過這次課程設計我確確實實感受到了編程的樂趣，從中也學到了不少知識。我在學習運用數據結構編程之前，并沒能深刻體會到這一點，直到這次課程設計，

49、我才有所領悟。</p><p>　　由于我對基本概念二叉樹和二叉排序樹理解的模糊不清，導致這次課程設計中我也出現過一些錯誤。經過多次的編寫與修改和多系的實驗，最終完成了任務，心中巨大的成就感油然而生。另外收獲了很多東西，在整個過程中，鍛煉了我們查找文獻，整合資源，然后吸收變成自己的東西。</p><p>　　總之，我會繼續(xù)編寫程序的，相信在越來越多的失敗與嘗試之后，自己會不斷進步不斷提高的

50、。</p><p><b>　　第八章 參考文獻</b></p><p>　　【1】唐策善.C程序設計[M].北京：高等教育出版社. 1995.</p><p>　　【2】譚浩強.C程序設計[M].北京：清華大學出版社. 2005.</p><p><b>　　【3】數據結構課本</b></p