按層次遍歷二叉樹

1、學(xué) 號:課程設(shè)計題目按層次遍歷二叉樹學(xué)院計算機科學(xué)與技術(shù)專業(yè)計算機科學(xué)與技術(shù)班級名姓 指導(dǎo)教師課程設(shè)計任務(wù)書學(xué)生姓名:工作單位:專業(yè)班級:指導(dǎo)教師:題目：按層次遍歷二叉樹初始條件:編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。（1 ）二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)。（2 ）按嚴蔚敏數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語言版）p44面題6.69所指定的格式輸出建立的二叉樹。（3）輸出層次遍歷結(jié)果。（4）自行設(shè)計測試用例。要求完成的主要任務(wù):（包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）課程設(shè)計報告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?yīng)包含如下內(nèi)容: 1.問題描述簡述題目要解決的問題是什么。2.

2、設(shè)計存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類C/C+語言或用框圖描述）、測試用例設(shè)計;3.調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。4.經(jīng)驗和體會（包括對算法改進的設(shè)想）5.附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出。說明:1.設(shè)計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2.凡拷貝往屆任務(wù)書或課程設(shè)計充數(shù)者，成績一律無效，以0分記。時間安排:1、第18周完成。2、7月2日8:30時到實驗中心檢查程序、交課程設(shè)計報告、源程序（U盤）。指導(dǎo)教師簽名:2010年6月22日系主任（或責(zé)任教師）簽名:

3、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計按層次遍歷二叉樹1問題描述及要求1.1問題描述編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。1.2任務(wù)要求編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。(1) 二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)。(2) 按題集p44面題6.69所指定的格式輸出建立的二叉樹。(3) 輸出層次遍歷結(jié)果。(4) 測試用例自己設(shè)計。2開發(fā)平臺及所使用軟件Win dows 7.0, Visual C+6.03程序設(shè)計思路3.1二叉樹存儲結(jié)構(gòu)設(shè)計typ edef char ElemT ype;/二叉樹結(jié)點值的類型為字符型typ edef struct BiTNode/二叉樹的二叉鏈表存儲表示ElemT

4、 ypedate;struct BiTNode*lchild,*rchild;/左右孩子指針 BiTNode ，*BiTree;3.2 題目算法設(shè)計3.2.1建立二叉樹void CreateBi nTree(B in Tree &T)/按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹char ch;ch=getchar(); II輸入函數(shù)。if(ch=)T=NULL; /輸入空格時為空結(jié)點建立失敗!)；elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) prin tf(%cT-data=ch;CreateBi nTree(T-lchild);CreateBi nT

5、ree(T-rchild);3.2.2 遍歷二叉樹void LevleOrder(Bi nTree T)/從第一層開始，從左到右Bin Tree Queuemax, p; /用一維數(shù)組表示隊列，front和rear分別表示隊首和隊尾指針int fron t,rear;fron t=rear=0;if (T)/若樹非空Queuerear+=T; /根結(jié)點入隊列while (fron t!=rear)/隊列非空P=Queuefr on t+;/隊首元素出隊列，并訪問這個結(jié)點左子樹非空，入隊列prin tf(%c, p-data);if (p-lchild!=NULL) Queuerear+=p-l

6、child; / if (p-rchild!=NULL) Queuerear+=p-rchild; 要用兩個空格表示，如果輸入“AB#D#CE#F ”則沒有輸出結(jié)果。3.2.3按要求格式輸出已建立的二叉樹void PrintBin Tree(B in Tree T,i nt i ) i表示結(jié)點所在層次，初次調(diào)用時i=0if(T-rchild) Print_Bin Tree(T-rchild,i+1);/函數(shù)遞歸for( j=1;jdata); /打印T元素，換行if(T-lchild) Prin t_BiTree(T-lchild,i+1);3.3測試程序圖1 ：測試二叉樹如圖所示二叉樹，按先

7、序遍歷順序輸入,AB#D#CE#F# 。其中” # ”代表空格，理論上按層次遍歷的結(jié)果應(yīng)該是” CFEADB ”，二叉樹是：A為根節(jié)點，A左孩子是B，右孩子是C,B的左孩子為空, 右孩子為D，C的左孩子為E,右孩子為空，E的左孩子為空，右孩子為 F。根據(jù)以下程序運行結(jié)果（見圖2）可知，程序正確運行4調(diào)試報告F沒有孩子,在建立二叉樹時，輸入的格式一定要正確，沒有孩子的要用空格表示，在測試用例中,5經(jīng)驗和體會本程序的建立和遍歷二叉樹的程序都比較簡單，關(guān)鍵在于按要求打印二叉樹。起初一直找不到合適的方法按題目要求打印二叉樹，在和同學(xué)討論了很久之后終于有了思路。打印的格式中，最上層的節(jié)點是右子樹層次最高

8、的，于是就可以用遞歸調(diào)用的方式實現(xiàn)。遞歸次數(shù)最高的就是輸出最頂置的節(jié)點。導(dǎo)致程序無法運行,在調(diào)試程序的時候也出現(xiàn)了問題，起初沒有在意輸入方式對程序運行結(jié)果的影響,在檢查了很久之后終于找到了問題的所在，對輸入進行了改正，得到了正確的結(jié)果6源程序清單及運行結(jié)果6.1源程序清單#in elude #in elude #defi ne max 100typ edef char ElemT ype;typ edef struct BiTNodeElemT ypedata;struct BiTNode*lchild,*rchild; BiTNode,*B in Tree;/建立二叉樹void Create

9、Bi nTree(B in Tree &T)char ch;ch=getchar();if(ch= ) T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) prin tf(%c結(jié)點建立失敗!）；T-data=ch;CreateBi nTree(T-lchild);CreateBi nTree(T-rchild);/遍歷二叉樹void LevleOrder(Bi nTree T)Bi nTree Queuemax, p;int fron t,rear;fron t=rear=0;if (T)Queuerear+=T;while (fron t!

10、=rear)p=Queuefr on t+;prin tf(%c, p-data);if (p-lchild!=NULL) Queuerear+=p-lchild;if (p-rchild!=NULL) Queuerear+=p-rchild; /按要求輸出二叉樹i=0void Print_Bin Tree(B in Tree T,i nt i )II本題的關(guān)鍵所在,i表示結(jié)點所在層次 ，初次調(diào)用時if(T-rchild) Prin t_Bi nTree(T-rchild,i+1);II本題的難點，函數(shù)遞歸來建立層次。);II打印i個空格以表示出層次打印T元素，換行for(i nt j=1;j

11、data); IIif(T-lchild) Prin t_Bi nTree(T-lchild,i+1);int mai n()Bin Tree T;i nt i=0;prin tf(n創(chuàng)建二叉樹n);CreateB in Tree (T);printf（n 層次遍歷二叉樹并輸出遍歷結(jié)果n）;LevleOrder(T);prin tf（n按樹形打印輸出二叉樹n）;Prin t_Bi nTree(T, i);return 0;6.2運行結(jié)果圖2:運行結(jié)果7參考文獻1數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴蔚敏，吳偉民編著，出版社：清華大學(xué)出版社，出版或修 訂時間：1997年4月 2數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語言版），嚴蔚敏，吳偉民，米寧編著，清華大學(xué)出版社，出版 或修訂時間：1999年2月本科生課程設(shè)計成績評定表