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

1、精品文檔學 號： 課 程 設 計題 目按層次遍歷二叉樹學 院計算機科學與技術專 業(yè)計算機科學與技術班 級姓 名指導教師2021年6月20日1 問題描述及要求41.1問題描述41.2任務要求42 開發(fā)平臺及所使用軟件43 程序設計思路53.1 二叉樹存儲結(jié)構設計53.2 題目算法設計53.2.1 建立二叉樹53.2.2 遍歷二叉樹53.3.3 按要求格式輸出已建立的二叉樹63.3 測試程序64 調(diào)試報告65 經(jīng)驗和體會76源程序清單及運行結(jié)果76.1源程序清單76.2 運行結(jié)果97 參考文獻10本科生課程設計成績評定表11 課程設計任務書 學生姓名： 專業(yè)班級： 計科ZY1102班 指導教師：

2、工作單位： 計算機科學系 題目: 按層次遍歷二叉樹 初始條件：編寫按層次順序同一層自左至右遍歷二叉樹的算法。1二叉樹采用二叉鏈表作為存儲結(jié)構。2按嚴蔚敏?數(shù)據(jù)結(jié)構習題集(C語言版)?p44面題6.69所指定的格式輸出建立的二叉樹。3輸出層次遍歷結(jié)果。4自行設計測試用例。要求完成的主要任務: 包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求課程設計報告按學校規(guī)定格式用A4紙打印書寫，并應包含如下內(nèi)容： 1. 問題描述簡述題目要解決的問題是什么。2. 設計存儲結(jié)構設計、主要算法設計用類C/C+語言或用框圖描述、測試用例設計；3. 調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設計和編碼的討論

3、和分析。4. 經(jīng)驗和體會包括對算法改良的設想5. 附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，那么運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出。說明：1. 設計報告、程序不得相互抄襲和拷貝；假設有雷同，那么所有雷同者成績均為0分。2. 凡拷貝往年任務書或課程設計充數(shù)者，成績一律無效，以0分記。時間安排：1第17周完成，驗收時間由指導教師指定2驗收地點：實驗中心3驗收內(nèi)容：可執(zhí)行程序與源代碼、課程設計報告書。指導教師簽名： 2021年6月14日系主任或責任教師簽名： 年 月 日數(shù)據(jù)結(jié)構課程設計 按層次遍歷二叉樹1 問題描述及要求1.1問題描述編寫按層次順序同一層自左至右遍歷二叉樹的算

4、法，并將二叉樹按指定格式輸出。題集p44面題6.69所指定的格式指定格式如下： C F E A D B 圖一：指定輸出格式1.2任務要求編寫按層次順序同一層自左至右遍歷二叉樹的算法。1二叉樹采用二叉鏈表作為存儲結(jié)構。2按題集p44面題6.69所指定的格式輸出建立的二叉樹。3輸出層次遍歷結(jié)果。4測試用例自己設計。2 開發(fā)平臺及所使用軟件Windows 7.0 , Visual Studio20213 程序設計思路3.1 二叉樹存儲結(jié)構設計struct BinTreeNode /二叉樹用二叉鏈表存儲 char data; /二叉樹結(jié)點值為字符型BinTreeNode* leftchild; /左孩

5、子指針BinTreeNode*rightchild; /右孩子指針 3.2 題目算法設計3.2.1 建立二叉樹void BinTree:creatBinTree(istream& in,BinTreeNode*&subTree) /通過輸入流in建立二叉樹char item;cin.get(item);if(item!=' ')subTree=new BinTreeNode(item);creatBinTree(in,subTree->leftchild);creatBinTree(in,subTree->rightchild);else subTr

6、ee=NULL; 3.2.2 遍歷二叉樹void BinTree:levelOrder(BinTreeNode* subTree) /按層次序遍歷二叉樹queue<BinTreeNode *>q;BinTreeNode*p=subTree;q.push(p);while(!q.empty() /假設樹非空p=q.front();cout<<visit(p)<<" " /輸出隊頭元素q.pop();if(p->leftchild!=NULL)q.push(p->leftchild); /左子樹非空，入隊if(p->righ

7、tchild!=NULL)q.push(p->rightchild);3.3.3 按要求格式輸出已建立的二叉樹void Print_BinTree(BinTreeNode* Tree,int i) /按要求格式輸出已建立的二叉樹 i表示結(jié)點所在層次。初始i=0BinTreeNode*p=Tree;if(p->rightchild) Print_BinTree(Tree->rightchild,i+1); /遞歸函數(shù)for(int j=1;j<=i;j+) cout<<" " /打印i個空格表示層次cout<<p->dat

8、a<<endl;if(p->leftchild) Print_BinTree(Tree->leftchild,i+1);3.3 測試程序圖2：測試二叉樹 如下圖二叉樹,按先序遍歷順序輸入，AB#D#CE#F#。其中#代表空格，二叉樹是：A為根節(jié)點，A左孩子是B，右孩子是C,B的左孩子為空，右孩子為D，C的左孩子為E，右孩子為空，E的左孩子為空，右孩子為F。根據(jù)以下程序運行結(jié)果見圖4可知，程序正確運行。 假設輸入AB#D#CE#F#，那么程序出現(xiàn)錯誤，不能運行。見圖34 調(diào)試報告 1、在建立二叉樹時，輸入的格式一定要正確，沒有孩子的要用空格表示，在測試用例中， F沒有孩子

9、，要用兩個空格表示，如果輸入“AB#D#CE#F那么沒有輸出結(jié)果。 2、起初編寫輸出程序void Print_BinTree(BinTreeNode* Tree,int i)的時候，始終顯示編譯無錯誤，但是不能運行，出現(xiàn)了一堆有關內(nèi)存分配錯誤的問題。最后發(fā)現(xiàn)沒有將指針指向結(jié)點。經(jīng)改正，運行成功。5 經(jīng)驗和體會 本程序的建立和遍歷二叉樹的程序都比擬簡單，關鍵在于按要求打印二叉樹。起初一直找不到適宜的方法按題目要求打印二叉樹，在和同學討論了很久之后終于有了思路。在調(diào)試程序的時候也出現(xiàn)了問題，起初沒有在意輸入方式對程序運行結(jié)果的影響，導致程序無法運行，在檢查了很久之后終于找到了問題的所在，對輸入進行

10、了改正，得到了正確的結(jié)果。 除此之外，編寫C+程序的過程中，指針時鐘是個難點也是個重點，今后要多練習，多理解才行。6源程序清單及運行結(jié)果6.1源程序清單#include<iostream>#include<queue>using namespace std;structBinTreeNode /定義結(jié)構體char data;BinTreeNode* leftchild;BinTreeNode*rightchild;BinTreeNode():leftchild(NULL),rightchild(NULL) /結(jié)構體可以有構造函數(shù)BinTreeNode(intx,BinT

11、reeNode*l=NULL,BinTreeNode*r=NULL):data(x),leftchild(l),rightchild(r);class BinTree private:BinTreeNode* root;public:BinTree():root(NULL); /構造函數(shù)，構造一棵空的二叉樹BinTreeNode* getroot()return root;BinTree(const BinTree&s); /復制構造函數(shù)BinTree()destroy(root); /析構函數(shù)void destroy(BinTreeNode* subTree); /刪除void cr

12、eatBinTree(istream&in,BinTreeNode* &subTree); /從文件讀入建樹friend istream& operator>>(istream& in,BinTree & Tree); /重載操作：輸入void levelOrder(BinTreeNode* subTree); /層次序遍歷char visit(BinTreeNode*p)return p->data; /取值;istream& operator>>(istream& in,BinTree& Tree

13、) /重載操作：輸入并建立一棵二叉樹。in是輸入流對象Tree.creatBinTree(in,Tree.root);return in;void BinTree:creatBinTree(istream& in,BinTreeNode*&subTree) /從輸入流in輸入二叉樹表示建立對應的二叉鏈表char item;cin.get(item);if(item!=' ')subTree=new BinTreeNode(item);creatBinTree(in,subTree->leftchild);creatBinTree(in,subTree-&g

14、t;rightchild);else subTree=NULL;void BinTree:levelOrder(BinTreeNode* subTree)queue<BinTreeNode *>q;BinTreeNode*p=subTree;q.push(p);while(!q.empty() /隊列不空p=q.front();cout<<visit(p)<<" "q.pop();if(p->leftchild!=NULL)q.push(p->leftchild); /左子女進隊if(p->rightchild!=NUL

15、L)q.push(p->rightchild); /右子女進隊;Void BinTree:destroy(BinTreeNode*subTree) /釋放空間if(subTree!=NULL)destroy(subTree->leftchild);destroy(subTree->rightchild);delete subTree;void Print_BinTree(BinTreeNode* Tree,int i) /按要求輸出二叉樹，i表示結(jié)點所在層次，初次調(diào)用為0BinTreeNode*p=Tree;if(p->rightchild) Print_BinTree

16、(Tree->rightchild,i+1); for(int j=1;j<=i;j+) cout<<"" /打印i個空格表示層次cout<<p->data<<endl; /打印元素，換行if(p->leftchild) Print_BinTree(Tree->leftchild,i+1);int main()BinTree Tree;int a;int i=0;cout<<"請按照前序遍歷的方法，輸入初始值，每段空格結(jié)束："<<endl;cin>>Tr

17、ee;BinTreeNode*p=Tree.getroot();cout<<endl;cout<<"層序遍歷為："<<endl;Tree.levelOrder(p);cout<<endl;cout<<"按樹形打印輸出二叉樹"<<endl;Print_BinTree(p,i);cin>>a;return 0;6.2 運行結(jié)果圖三：輸入錯誤的運行結(jié)果圖四：輸入正確的運行結(jié)果7 參考文獻 1 ?數(shù)據(jù)結(jié)構習題集(C語言版)?，嚴蔚敏，吳偉民，米寧編著，清華大學出版社，出版或修訂時間：1999年2月 2?數(shù)據(jù)結(jié)構用面向?qū)ο蠓?/p>