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

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p>　　1 問(wèn)題描述及要求4</p><p><b>　　1.1問(wèn)題描述4</b></p><p><b>　　1.2任務(wù)要求4</b></p><p>　　2 開(kāi)發(fā)平臺(tái)及所使用軟件4</p>

2、<p>　　3 程序設(shè)計(jì)思路5</p><p>　　3.1 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)5</p><p>　　3.2 題目算法設(shè)計(jì)5</p><p>　　3.2.1 建立二叉樹(shù)5</p><p>　　3.2.2 遍歷二叉樹(shù)5</p><p>　　3.3.3 按要求格式輸出已建立的二叉樹(shù)6</p&

3、gt;<p>　　3.3 測(cè)試程序6</p><p><b>　　4 調(diào)試報(bào)告6</b></p><p><b>　　5 經(jīng)驗(yàn)和體會(huì)7</b></p><p>　　6源程序清單及運(yùn)行結(jié)果7</p><p>　　6.1源程序清單7</p><p>　　

4、6.2 運(yùn)行結(jié)果9</p><p><b>　　7 參考文獻(xiàn)10</b></p><p>　　本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表11</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　題目: 按層次遍歷二叉樹(shù) <

5、/p><p><b>　　初始條件：</b></p><p>　　編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。</p><p>　?。?）二叉樹(shù)采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)。</p><p>　?。?）按嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》p44面題6.69所指定的格式輸出建立的二叉樹(shù)。</p><p&

6、gt;　　（3）輸出層次遍歷結(jié)果。</p><p>　　（4）自行設(shè)計(jì)測(cè)試用例。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）</p><p>　　課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞?shū)寫(xiě)），并應(yīng)包含如下內(nèi)容： </p><p><b>　　1. 問(wèn)題描述</b&g

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

8、試過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。</p><p>　　4. 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）</p><p>　　5. 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出。</p><p><b>　　說(shuō)明：</b></p><p>　　1.

9、 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī)均為0分。</p><p>　　2. 凡拷貝往年任務(wù)書(shū)或課程設(shè)計(jì)充數(shù)者，成績(jī)一律無(wú)效，以0分記。</p><p><b>　　時(shí)間安排：</b></p><p>　　1．第17周完成，驗(yàn)收時(shí)間由指導(dǎo)教師指定</p><p>　　2．驗(yàn)收地點(diǎn)：實(shí)驗(yàn)中心</

10、p><p>　　3．驗(yàn)收內(nèi)容：可執(zhí)行程序與源代碼、課程設(shè)計(jì)報(bào)告書(shū)。</p><p>　　指導(dǎo)教師簽名： 2013年6月14日</p><p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><

11、;p>　　——按層次遍歷二叉樹(shù)</p><p><b>　　1 問(wèn)題描述及要求</b></p><p><b>　　1.1問(wèn)題描述</b></p><p>　　編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法，并將二叉樹(shù)按指定格式輸出。（題集p44面題6.69所指定的格式）指定格式如下：</p><

12、;p><b>　　圖一：指定輸出格式</b></p><p><b>　　1.2任務(wù)要求</b></p><p>　　編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。</p><p>　　（1）二叉樹(shù)采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)。</p><p>　　（2）按題集p44面題6.69所指定的格式輸

13、出建立的二叉樹(shù)。</p><p>　?。?）輸出層次遍歷結(jié)果。</p><p>　?。?）測(cè)試用例自己設(shè)計(jì)。</p><p>　　2 開(kāi)發(fā)平臺(tái)及所使用軟件</p><p>　　Windows 7.0 , Visual Studio2010</p><p><b>　　3 程序設(shè)計(jì)思路</b>&l

14、t;/p><p>　　3.1 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)</p><p>　　struct BinTreeNode //二叉樹(shù)用二叉鏈表存儲(chǔ)</p><p><b>　　{</b></p><p>　　char data;

15、 //二叉樹(shù)結(jié)點(diǎn)值為字符型</p><p>　　BinTreeNode* leftchild; //左孩子指針</p><p>　　BinTreeNode*rightchild; //右孩子指針</p><p><b>　　}</b></p

16、><p>　　3.2 題目算法設(shè)計(jì)</p><p>　　3.2.1 建立二叉樹(shù)</p><p>　　void BinTree::creatBinTree(istream& in,BinTreeNode*&subTree)</p><p>　　//通過(guò)輸入流in建立二叉樹(shù)</p><p><b>　

17、　{</b></p><p>　　char item;</p><p>　　cin.get(item);</p><p>　　if(item!=' ')</p><p><b>　　{</b></p><p>　　subTree=new BinTreeNode(item

18、);</p><p>　　creatBinTree(in,subTree->leftchild);</p><p>　　creatBinTree(in,subTree->rightchild);</p><p><b>　　}</b></p><p><b>　　else </b><

19、;/p><p><b>　　{</b></p><p>　　subTree=NULL;</p><p><b>　　}</b></p><p>　　}; </p><p>　　3.2.2 遍歷二叉樹(shù)</p><p&

20、gt;　　void BinTree::levelOrder(BinTreeNode* subTree) //按層次序遍歷二叉樹(shù)</p><p><b>　　{</b></p><p>　　queue<BinTreeNode *>q;</p><p>　　BinTreeNode*p=subTree;</p>&

21、lt;p>　　q.push(p);</p><p>　　while(!q.empty()) //若樹(shù)非空</p><p><b>　　{</b></p><p>　　p=q.front();cout<<visit(p)<<" ";

22、 //輸出隊(duì)頭元素</p><p><b>　　q.pop();</b></p><p>　　if(p->leftchild!=NULL){q.push(p->leftchild);} //左子樹(shù)非空，入隊(duì)</p><p>　　if(p->rightchild!=NULL){q.push

23、(p->rightchild);}</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　3.3.3 按要求格式輸出已建立的二叉樹(shù)</p><p>　　void Print_BinTree(BinTreeNode* Tree,int i)

24、 //按要求格式輸出已建立的二叉樹(shù)</p><p>　　i表示結(jié)點(diǎn)所在層次。初始i=0</p><p><b>　　{</b></p><p>　　BinTreeNode*p=Tree;</p><p>　　if(p->rightchild) Print_BinTree(Tree->right

25、child,i+1); //遞歸函數(shù)</p><p>　　for(int j=1;j<=i;j++) cout<<" "; //打印i個(gè)空格表示層次</p><p>　　cout<<p->data<<endl;</p><p>　　if(p->le

26、ftchild) Print_BinTree(Tree->leftchild,i+1);</p><p><b>　　};</b></p><p><b>　　3.3 測(cè)試程序</b></p><p>　　如圖所示二叉樹(shù),按先序遍歷順序輸入，AB#D##CE#F###。其中”#”代表空格，二叉樹(shù)是：A為根節(jié)點(diǎn)，A左

27、孩子是B，右孩子是C,B的左孩子為空，右孩子為D，C的左孩子為E，右孩子為空，E的左孩子為空，右孩子為F。根據(jù)以下程序運(yùn)行結(jié)果（見(jiàn)圖4）可知，程序正確運(yùn)行。</p><p>　　若輸入AB#D#CE#F###，則程序出現(xiàn)錯(cuò)誤，不能運(yùn)行。（見(jiàn)圖3）</p><p><b>　　4 調(diào)試報(bào)告</b></p><p>　　1、在建立二叉樹(shù)時(shí)，輸入的格

28、式一定要正確，沒(méi)有孩子的要用空格表示，在測(cè)試用例中， F沒(méi)有孩子，要用兩個(gè)空格表示，如果輸入“AB#D##CE#F”則沒(méi)有輸出結(jié)果。</p><p>　　2、起初編寫(xiě)輸出程序（void Print_BinTree(BinTreeNode* Tree,int i)）的時(shí)候，始終顯示編譯無(wú)錯(cuò)誤，但是不能運(yùn)行，出現(xiàn)了一堆有關(guān)內(nèi)存分配錯(cuò)誤的問(wèn)題。最后發(fā)現(xiàn)沒(méi)有將指針指向結(jié)點(diǎn)。經(jīng)改正，運(yùn)行成功。</p>&l

29、t;p><b>　　5 經(jīng)驗(yàn)和體會(huì)</b></p><p>　　本程序的建立和遍歷二叉樹(shù)的程序都比較簡(jiǎn)單，關(guān)鍵在于按要求打印二叉樹(shù)。起初一直找不到合適的方法按題目要求打印二叉樹(shù)，在和同學(xué)討論了很久之后終于有了思路。在調(diào)試程序的時(shí)候也出現(xiàn)了問(wèn)題，起初沒(méi)有在意輸入方式對(duì)程序運(yùn)行結(jié)果的影響，導(dǎo)致程序無(wú)法運(yùn)行，在檢查了很久之后終于找到了問(wèn)題的所在，對(duì)輸入進(jìn)行了改正，得到了正確的結(jié)果。</

30、p><p>　　除此之外，編寫(xiě)C++程序的過(guò)程中，指針時(shí)鐘是個(gè)難點(diǎn)也是個(gè)重點(diǎn)，今后要多練習(xí)，多理解才行。</p><p>　　6源程序清單及運(yùn)行結(jié)果</p><p><b>　　6.1源程序清單</b></p><p>　　#include<iostream></p><p>　　#inc

31、lude<queue></p><p>　　using namespace std;</p><p>　　structBinTreeNode //定義結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　char

32、data;</p><p>　　BinTreeNode* leftchild;</p><p>　　BinTreeNode*rightchild;</p><p>　　BinTreeNode():leftchild(NULL),rightchild(NULL){} </p><p>　　//結(jié)構(gòu)體可以有構(gòu)造函數(shù)

33、</p><p>　　BinTreeNode(intx,BinTreeNode*l=NULL,BinTreeNode*r=NULL):data(x),leftchild(l),rightchild(r){}</p><p><b>　　};</b></p><p>　　class BinTree </p><p><

34、;b>　　{</b></p><p><b>　　private:</b></p><p>　　BinTreeNode* root;</p><p><b>　　public:</b></p><p>　　BinTree():root(NULL){};

35、 //構(gòu)造函數(shù)，構(gòu)造一棵空的二叉樹(shù)</p><p>　　BinTreeNode* getroot(){return root;}</p><p>　　BinTree(const BinTree&s); //復(fù)制構(gòu)造函數(shù)</p><p>　　~BinTree(){destroy(root);}

36、 //析構(gòu)函數(shù)</p><p>　　void destroy(BinTreeNode* subTree); //刪除</p><p>　　void creatBinTree(istream&in,BinTreeNode* &subTree); //從文件讀入建樹(shù)&

37、lt;/p><p>　　friend istream& operator>>(istream& in,BinTree & Tree); //重載操作：輸入</p><p>　　void levelOrder(BinTreeNode* subTree); //層次序遍歷</p><p>　　ch

38、ar visit(BinTreeNode*p){return p->data;}; //取值</p><p><b>　　};</b></p><p>　　istream& operator>>(istream& in,BinTree& Tree)

39、 </p><p>　　//重載操作：輸入并建立一棵二叉樹(shù)。in是輸入流對(duì)象</p><p><b>　　{</b></p><p>　　Tree.creatBinTree(in,Tree.root);</p><p>　　return in;</p><p><b>　　};<

40、;/b></p><p>　　void BinTree::creatBinTree(istream& in,BinTreeNode*&subTree) </p><p>　　//從輸入流in輸入二叉樹(shù)表示建立對(duì)應(yīng)的二叉鏈表</p><p><b>　　{</b></p><p>　　c

41、har item;</p><p>　　cin.get(item);</p><p>　　if(item!=' ')</p><p><b>　　{</b></p><p>　　subTree=new BinTreeNode(item);</p><p>　　creatBinTre

42、e(in,subTree->leftchild);</p><p>　　creatBinTree(in,subTree->rightchild);</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b

43、></p><p>　　subTree=NULL;</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　void BinTree::levelOrder(BinTreeNode* subTree)</p><p><

44、;b>　　{</b></p><p>　　queue<BinTreeNode *>q;</p><p>　　BinTreeNode*p=subTree;</p><p>　　q.push(p);</p><p>　　while(!q.empty())

45、 //隊(duì)列不空</p><p><b>　　{</b></p><p>　　p=q.front();cout<<visit(p)<<" ";</p><p><b>　　q.pop();</b></p><p>　　if(p->lef

46、tchild!=NULL){q.push(p->leftchild);} //左子女進(jìn)隊(duì)</p><p>　　if(p->rightchild!=NULL){q.push(p->rightchild);} //右子女進(jìn)隊(duì)</p><p><b>　　}</b></p><p><

47、;b>　　};</b></p><p>　　Void BinTree::destroy(BinTreeNode*subTree) //釋放空間</p><p><b>　　{</b></p><p>　　if(subTree!=NULL)</p><p><

48、;b>　　{</b></p><p>　　destroy(subTree->leftchild);</p><p>　　destroy(subTree->rightchild);</p><p>　　delete subTree;</p><p><b>　　}</b></p>

49、<p><b>　　};</b></p><p>　　void Print_BinTree(BinTreeNode* Tree,int i) </p><p>　　//按要求輸出二叉樹(shù)，i表示結(jié)點(diǎn)所在層次，初次調(diào)用為0</p><p><b>　　{</

50、b></p><p>　　BinTreeNode*p=Tree;</p><p>　　if(p->rightchild) Print_BinTree(Tree->rightchild,i+1); </p><p>　　for(int j=1;j<=i;j++) cout<<"";

51、 //打印i個(gè)空格表示層次</p><p>　　cout<<p->data<<endl; //打印元素，換行</p><p>　　if(p->leftchild) Print_BinTree(Tree->leftchild,i+1);</p><p>&l

52、t;b>　　};</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　BinTree Tree;</p><p><b>　　int a;</b></p><p><b>　　int i=0

53、;</b></p><p>　　cout<<"請(qǐng)按照前序遍歷的方法，輸入初始值，每段空格結(jié)束："<<endl;</p><p>　　cin>>Tree;</p><p>　　BinTreeNode*p=Tree.getroot();</p><p>　　cout<<

54、;endl;</p><p>　　cout<<"層序遍歷為："<<endl;</p><p>　　Tree.levelOrder(p);</p><p>　　cout<<endl;</p><p>　　cout<<"按樹(shù)形打印輸出二叉樹(shù)"<<e

55、ndl;</p><p>　　Print_BinTree(p,i);</p><p><b>　　cin>>a;</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><

56、b>　　6.2 運(yùn)行結(jié)果</b></p><p>　　圖三：輸入錯(cuò)誤的運(yùn)行結(jié)果</p><p>　　圖四：輸入正確的運(yùn)行結(jié)果</p><p><b>　　7 參考文獻(xiàn)</b></p><p>　　[1] 《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》，嚴(yán)蔚敏，吳偉民，米寧編著，清華大學(xué)出版社，出版或修訂時(shí)間：1999年

57、2月</p><p>　　[2]《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述）（第二版）》，殷人昆主編，清華大學(xué)出版社，出版或修訂時(shí)間：2007年6月</p><p>　　[3]《C++程序設(shè)計(jì)》，閔聯(lián)營(yíng)，何克右編寫(xiě)，清華大學(xué)出版社，2010年8月</p><p>　　本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表</p><p>　　班級(jí) 　姓名：　 　學(xué)

58、號(hào)： </p><p>　　注：最終成績(jī)以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、</p><p>　　及格（60-69分）、60分以下為不及格</p><p><b>　　指導(dǎo)教師簽名：</b></p><p><b>　　2013年　月　日</b><