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

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　題 目: 計(jì)算二叉樹高度 </p><p>　　對任一棵二叉樹計(jì)算并輸出其高度.</p><p>

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

3、　1、 問題描述</b></p><p>　　簡述題目要解決的問題是什么。</p><p><b>　　2、 設(shè)計(jì)</b></p><p>　　存儲結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類C語言或用框圖描述）、測試用例設(shè)計(jì)；</p><p><b>　　3、 調(diào)試報(bào)告</b></p>

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

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

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

7、<b>　　3.實(shí)驗(yàn)設(shè)計(jì)2</b></p><p>　　3.1.設(shè)計(jì)思想框圖2</p><p>　　3.2.設(shè)計(jì)要點(diǎn)3</p><p><b>　　3.3具體設(shè)計(jì)3</b></p><p>　　3.3.1存儲結(jié)構(gòu)設(shè)計(jì)3</p><p>　　3.3.2主要算法設(shè)計(jì)3

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

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

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

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

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

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

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

15、</p><p>　　}tree,*Tree; </p><p>　　3.3.2主要算法設(shè)計(jì)</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測試用例設(shè)計(jì)</p><p><b>　　4.調(diào)試報(bào)告</b></p><p><b>　　4.1出現(xiàn)問題</b></p><p>　　創(chuàng)建二叉樹時，沒有對子樹進(jìn)行內(nèi)存分配，導(dǎo)致程序運(yùn)行后總是顯示內(nèi)存

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

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

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

24、/p><p>　　#include<stdio.h> </p><p>　　#include <string> </p><p>　　typedef struct tree//二叉樹二叉鏈表存儲結(jié)構(gòu)的定義 </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)化及運(yùn)行結(jié)果</p><p>　　以上程序還可以進(jìn)行以下改進(jìn)以便更加容易理解：</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)驗(yàn)與體會</b></p><p>　　此次課程設(shè)計(jì)是對本學(xué)期數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)成果的一個考察，也是對之前我們學(xué)過的c++的更高層次的運(yùn)用，數(shù)據(jù)結(jié)構(gòu)是建立在c++的基礎(chǔ)上的，因此在本次試驗(yàn)中，我又重新翻閱了以前的課本用以加深理解。</p><

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