按層次遍歷二叉樹

學(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)容：問題描述簡述題目要解決的問題是什么。設(shè)計存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類C/C++語言或用框圖描述）、測試用例設(shè)計；調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。經(jīng)驗和體會（包括對算法改進的設(shè)想）附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出。說明：設(shè)計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。凡拷貝往屆任務(wù)書或課程設(shè)計充數(shù)者，成績一律無效，以0分記。時間安排：1、 第18周完成。2、 7月2日8:30時到實驗中心檢查程序、交課程設(shè)計報告、源程序（U盤）。指導(dǎo)教師簽名： 2010年6月22日系主任（或責(zé)任教師）簽名： 年月日數(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ā)平臺及所使用軟件Windows7.0,VisualC++6.03程序設(shè)計思路3.1二叉樹存儲結(jié)構(gòu)設(shè)計typedefcharElemType; //二叉樹結(jié)點值的類型為字符型typedefstructBiTNode{ //二叉樹的二叉鏈表存儲表示ElemTypedate;structBiTNode*lchild,*rchild; //左右孩子指針}BiTNode，*BiTree;3.2題目算法設(shè)計建立二叉樹voidCreateBinTree（BinTree&T）{ //按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹 Tcharch;ch=getchar（）;//輸入函數(shù)。if（ch==’’）T=NULL;//輸入空格時為空else{if（!（T=（BiTNode*）malloc（sizeof（BiTNode））））printf（"%c"" 結(jié)點建立失敗!"）;T->data=ch;

CreateBinTree(T->lchild);CreateBinTree(T->rchild);}}遍歷二叉樹voidLevleOrder(BinTreeT){ //從第一層開始，從左到右BinTreeQueue[max],p;//用一維數(shù)組表示隊列，front和rear分別表示隊首和隊尾指針intfront,rear;front=rear=0;if(T) //若樹非空{(diào)Queue[rear++]=T;//根結(jié)點入隊列while(front!=rear){ //隊列非空p=Queue[front++]; //隊首元素出隊列，并訪問這個結(jié)點printf("%c",p->data);if(p->lchild!=NULL)Queue[rear++]=p->lchild;//左子樹非空，入隊列if(p->rchild!=NULL)Queue[rear++]=p->rchild;}}}按要求格式輸出已建立的二叉樹voidPrint_BinTree(BinTreeT,inti)//i表示結(jié)點所在層次，初次調(diào)用時i=0{if(T->rchild)Print_BinTree(T->rchild,i+1);〃函數(shù)遞歸for(j=1;j<=i;j++)printf("");//打印i個空格以表示出層次printf("%c\n”,T->data);//打印T元素，換行if(T->lchild)Print_BiTree(T->lchild,i+1);}3.3測試程序圖1圖1：測試二叉樹如圖所示二叉樹，按先序遍歷順序輸入，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(xiàn)沒有孩子，要用兩個空格表示，如果輸入“AB#D##CE#F”則沒有輸出結(jié)果。5經(jīng)驗和體會本程序的建立和遍歷二叉樹的程序都比較簡單，關(guān)鍵在于按要求打印二叉樹。起初一直找不到合適的方法按題目要求打印二叉樹，在和同學(xué)討論了很久之后終于有了思路。打印的格式中，最上層的節(jié)點是右子樹層次最高的，于是就可以用遞歸調(diào)用的方式實現(xiàn)。遞歸次數(shù)最高的就是輸出最頂置的節(jié)點。在調(diào)試程序的時候也出現(xiàn)了問題，起初沒有在意輸入方式對程序運行結(jié)果的影響，導(dǎo)致程序無法運行，在檢查了很久之后終于找到了問題的所在，對輸入進行了改正，得到了正確的結(jié)果6源程序清單及運行結(jié)果6.1源程序清單#include<stdio.h>#include<stdlib.h>#definemax100typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BinTree;//建立二叉樹voidCreateBinTree(BinTree&T){charch;ch=getchar();if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))printf("%c"" 結(jié)點建立失敗!");T->data=ch;CreateBinTree(T->lchild);CreateBinTree(T->rchild);}}//遍歷二叉樹voidLevleOrder(BinTreeT){BinTreeQueue[max],p;intfront,rear;front=rear=0;if(T){Queue[rear++]=T;while(front!=rear){p=Queue[front++];printf("%c",p->data);if(p->lchild!=NULL)Queue[rear++]=p->lchild;if(p->rchild!=NULL)Queue[rear++]=p->rchild;}}}//按要求輸出二叉樹voidPrint_BinTree(BinTreeT,inti) //本題的關(guān)鍵所在，i表示結(jié)點所在層次，初次調(diào)用時i=0{if(T->rchild)Print_BinTree(T->rchild,i+1);//本題的難點，函數(shù)遞歸來建立層次。for(intj=1;j<=i;j++)printf(- ");//打印i個空格以表示出層次printf("%c\n",T->data);//打印T元素，換行if(T->lchild)Print_BinTree(T->lchild,i+1);}intmain(){BinTreeT;inti=0;printf(-\n創(chuàng)建二叉樹\n");CreateBinTree(T);printf(-\n層次遍歷二叉樹并輸出遍歷結(jié)果\n");LevleOrder(T);printf(-\n按樹形打印輸出二叉樹\n");Print_BinTree(T,i);return0;}6.2運行結(jié)果

圖2：運行結(jié)果7參考文獻《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴蔚敏，吳偉民編著，出版社：清華大學(xué)出版社，出版或修訂時間：1997年4月《數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語言版）》，嚴蔚敏，吳偉民，米寧編著，清華大學(xué)出版社，出版或修訂時間：1999年2月

本科生課程設(shè)