數(shù)據(jù)結構課程設計---計算二叉樹高度

1、<p><b>　　課 程 設 計</b></p><p><b>　　課程設計任務書</b></p><p>　　題 目: 計算二叉樹高度 </p><p>　　對任一棵二叉樹計算并輸出其高度.</p><p>

2、;　?。?）利用教材6.3節(jié)所述的擴展前序二叉樹序列建立二叉樹。</p><p>　　（2） 測試用例自己設計.</p><p>　　要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）</p><p>　　課程設計報告按學校規(guī)定格式用A4紙打印（書寫），并應包含如下內容： </p><p><b>　

3、　1、 問題描述</b></p><p>　　簡述題目要解決的問題是什么。</p><p><b>　　2、 設計</b></p><p>　　存儲結構設計、主要算法設計（用類C語言或用框圖描述）、測試用例設計；</p><p><b>　　3、 調試報告</b></p>

4、<p>　　調試過程中遇到的問題是如何解決的；對設計和編碼的討論和分析。</p><p>　　4、 經(jīng)驗和體會（包括對算法改進的設想）</p><p>　　5、 附源程序清單和運行結果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結果要包含這些測試數(shù)據(jù)和運行輸出，</p><p>　　6、 設計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為

5、0分。</p><p><b>　　時間安排：</b></p><p>　　1、第20周（6月29日至7月3日）完成。</p><p>　　2、7月3 日8：00到計算中心檢查程序、交課程設計報告、源程序（CD盤）。</p><p>　　指導教師簽名： 年 月 日&l

6、t;/p><p>　　系主任（或責任教師）簽名： 年 月 日</p><p><b>　　目錄</b></p><p><b>　　1.引言2</b></p><p><b>　　2.問題描述2</b></p><p>

7、<b>　　3.實驗設計2</b></p><p>　　3.1.設計思想框圖2</p><p>　　3.2.設計要點3</p><p><b>　　3.3具體設計3</b></p><p>　　3.3.1存儲結構設計3</p><p>　　3.3.2主要算法設計3

8、</p><p>　　3.3.3測試用例設計4</p><p><b>　　4.調試報告4</b></p><p>　　4.1出現(xiàn)問題：4</p><p><b>　　4.2解決辦法5</b></p><p>　　5.源程序及測試結果5</p><

9、;p>　　6.算法優(yōu)化及運行結果7</p><p><b>　　7.經(jīng)驗與體會8</b></p><p><b>　　計算二叉樹高度</b></p><p><b>　　1.引言</b></p><p>　　數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，它不僅是計算機學

10、科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。</p><p>　　數(shù)據(jù)結構是一門專業(yè)選技術基礎課。一方面它要求我們學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及相應算法，并初步掌握算法的時間分析和空間分析的技術；另一方面，數(shù)據(jù)結構的學習過程也是復雜程序設計的訓練過程，要求我們編寫的程序結構清楚且正確易讀，符合軟件工程的規(guī)范，并培養(yǎng)我們的軟件抽象能力。本次課程設計任

11、務就是對二叉樹的高度的求取。</p><p><b>　　2.問題描述</b></p><p>　　已知任意一棵二叉樹，求取它的高度并輸出。</p><p><b>　　主要解決的問題：</b></p><p>　　1.存儲結構采用二叉鏈表，方便快捷 2.對子樹深度求取的算法，主要采用遞歸算

12、法</p><p><b>　　3.實驗設計</b></p><p>　　3.1.設計思想框圖 </p><p><b>　　3.2.設計要點</b></p><p>　　此次設計問題主要集中在求取二叉樹的高度算法編寫上，深度算法采用的是遞歸思想，對左右孩子不斷求取高度，直到左、右孩子為空，

13、再對左右孩子的高度進行比較，取兩者中較大的加一作為二叉樹的高度。</p><p><b>　　3.3具體設計</b></p><p>　　3.3.1存儲結構設計</p><p>　　線形表的順序存儲結構的特點是邏輯關系上相鄰的兩個元素物理位置上也相鄰，因此可以隨機存取表中任一元素。鏈式存儲結構的特點是用一組任意的存儲單元存儲線形表的數(shù)據(jù)元素。因

14、此在二叉樹中采用二叉鏈表作為存儲結構，操作簡單而且不會浪費空間。</p><p>　　typedef struct tree//二叉樹二叉鏈表存儲結構的定義 </p><p><b>　　{ </b></p><p>　　char data; </p><p>　　struct tree *lchild,*rchild;

15、</p><p>　　}tree,*Tree; </p><p>　　3.3.2主要算法設計</p><p>　　1. void create(Tree &t)//創(chuàng)建一棵二叉樹 </p><p><b>　　{ </b></p><p><b>　　char ch; </

16、b></p><p>　　ch=getchar();</p><p>　　if(ch=='#') t=NULL; //如果子樹為空，則用#表示</p><p><b>　　else { </b></p><p>　　t=(tree *)malloc(sizeof(tree));</p>

17、<p>　　t->data=ch;</p><p>　　create(t->lchild); </p><p>　　create(t->rchild);</p><p><b>　　} </b></p><p><b>　　}</b></p><p&

18、gt;　　2.int deep(Tree &t)//深度算法 </p><p><b>　　{ </b></p><p>　　int ld=0,rd=0;</p><p>　　if(!t) return 0; </p><p><b>　　else { </b></p><

19、;p>　　ld=deep(t->lchild); </p><p>　　rd=deep(t->rchild); </p><p><b>　　}</b></p><p>　　if(ld<rd) return rd+1; </p><p>　　else return ld+1; </p>

20、<p><b>　　} </b></p><p>　　3.3.3測試用例設計</p><p><b>　　4.調試報告</b></p><p><b>　　4.1出現(xiàn)問題</b></p><p>　　創(chuàng)建二叉樹時，沒有對子樹進行內存分配，導致程序運行后總是顯示內存

21、錯誤；</p><p>　　本次編程采用的是c語言，總是與c++混淆，導致語法錯誤；</p><p>　　編寫深度算法時，未對左右子樹ld、rd進行聲明，導致錯誤；</p><p>　　編寫深度算法時，在判斷左右子樹哪個更大時，判斷條件寫反了，導致編譯成功后不能運行到深度算法這來；</p><p>　　編寫頭文件時，未將sring加入頭文件里

22、，導致sring類的都沒有被聲明。</p><p><b>　　4.2解決辦法</b></p><p>　　1.重新對子樹進行內存分配 t=(tree *)malloc(sizeof(tree));</p><p>　　2.經(jīng)過糾錯后，將所有c++語言改成c語言；</p><p>　　3.重新對ld、

23、rd進行聲明 int ld=0,rd=0;</p><p>　　4.將判斷條件改過后，即可正常運行 if(ld<rd)；</p><p>　　5.經(jīng)過檢查后，將sring加入頭文件 #include<stdio.h> #include <string> </p><p>　　5.源程序及測試結果<

24、/p><p>　　#include<stdio.h> </p><p>　　#include <string> </p><p>　　typedef struct tree//二叉樹二叉鏈表存儲結構的定義 </p><p><b>　　{ </b></p><p>　

25、　char data; </p><p>　　struct tree *lchild,*rchild;</p><p>　　}tree,*Tree; </p><p>　　void create(Tree &t)//創(chuàng)建一棵二叉樹 </p><p><b>　　{ </b></p><p>

26、;<b>　　char ch; </b></p><p>　　ch=getchar();</p><p>　　if(ch=='#') t=NULL; //如果子樹為空，則用#表示</p><p><b>　　else { </b></p><p>　　t=(tree *)malloc

27、(sizeof(tree));</p><p>　　t->data=ch;</p><p>　　create(t->lchild); </p><p>　　create(t->rchild);</p><p><b>　　} </b></p><p><b>　　}&l

28、t;/b></p><p>　　int deep(Tree &t)//深度算法 </p><p><b>　　{ </b></p><p>　　int ld=0,rd=0;</p><p>　　if(!t) return 0; </p><p><b>　　else { &

29、lt;/b></p><p>　　ld=deep(t->lchild); </p><p>　　rd=deep(t->rchild); </p><p><b>　　}</b></p><p>　　if(ld<rd) return rd+1; </p><p>　　else

30、 return ld+1; </p><p><b>　　} </b></p><p>　　void main()//主函數(shù) </p><p><b>　　{</b></p><p><b>　　Tree t;</b></p><p>　　create(

31、t);</p><p>　　printf("%d\n",deep(t));</p><p><b>　　}</b></p><p>　　6.算法優(yōu)化及運行結果</p><p>　　以上程序還可以進行以下改進以便更加容易理解：</p><p>　　1.void deep(Tree

32、 t,int &ld,int &rd)//深度算法 </p><p><b>　　{ </b></p><p>　　if(t->lchild){</p><p><b>　　ld++;</b></p><p>　　deep(t->lchild,ld,rd);</p&

33、gt;<p><b>　　}</b></p><p>　　else if(t->rchild){</p><p><b>　　rd++;</b></p><p>　　deep(t->rchild,ld,rd);</p><p><b>　　} </b>

34、</p><p><b>　　} </b></p><p>　　2.void main()//主函數(shù) </p><p><b>　　{</b></p><p><b>　　Tree t;</b></p><p>　　printf("按先序遍歷輸

35、入二叉樹，孩子為空用'#'號表示:\n");</p><p>　　create(t);</p><p>　　int ld=0,rd=0;</p><p>　　deep(t,ld,rd);</p><p>　　printf("該二叉樹的高度為:\n");</p><p>　　

36、if(ld>rd) </p><p>　　printf("%d\n",ld+1); </p><p><b>　　else </b></p><p>　　printf("%d\n",rd+1); </p><p>　　system("pause");<

37、;/p><p><b>　　}</b></p><p><b>　　7.經(jīng)驗與體會</b></p><p>　　此次課程設計是對本學期數(shù)據(jù)結構學習成果的一個考察，也是對之前我們學過的c++的更高層次的運用，數(shù)據(jù)結構是建立在c++的基礎上的，因此在本次試驗中，我又重新翻閱了以前的課本用以加深理解。</p><

38、p>　　在本次課程設計中，我了解到自己在具體實現(xiàn)算法上仍有不足，能想得到算法的基本框圖，但要把它真正實現(xiàn)出來仍需要依靠課本和同學的幫助，尤其是一些基本的地方，比如說頭文件的創(chuàng)立、判定條件的編寫、文件的聲明、內存的分配，雖然大體上可以知道怎么做，但由于平時比較少進行實際操作，因此導致程序不斷報錯。因此以后還是要多進行上機操作，自己多動手編程，將課本上講的理論知識與實際相結合，將知識融會貫通，真正成為自己的東西。</p>