




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、安徽工程大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 說 明 書 學(xué)生姓名: 劉超學(xué) 號(hào):3120702109 學(xué) 院:計(jì)算機(jī)與信息學(xué)院專 業(yè):信息與計(jì)算科學(xué)題 目:二叉樹的創(chuàng)建和遍歷指導(dǎo)教師潘海玉 2014年8月25日目錄1. 需求分析-12. 概要設(shè)計(jì)-13. 詳細(xì)設(shè)計(jì)-34. 調(diào)試分析-95. 課程總結(jié)-106. 附錄 -121. 需求分析問題描述:根據(jù)運(yùn)行時(shí)輸入的先序序列,創(chuàng)建一棵二叉樹,分別對(duì)其 進(jìn)行先序、中序、后序、層序遍歷,并顯示遍歷結(jié)果。void CreateBTree(BTree &
2、;T) /按先序次序輸入,構(gòu)造二叉樹void PreOrder(BTree T) /遞歸先序遍歷void InOrder(BTree T) /遞歸中序遍歷void PostOrder(BTree T) /遞歸后序遍歷void LevelOrder(BTree T) /層序遍歷void NRPreOrder(BTree bt) /非遞歸先序遍歷void NRInOrder(BTree bt) /非遞歸中序遍歷void NRPostOrder(BTree bt) /非遞歸后序遍歷void main() /二叉樹的建立與遍歷實(shí)現(xiàn)2.概要設(shè)計(jì)此次課程設(shè)計(jì)遍歷算法的框架圖層序遍歷遍歷算法遞歸遍歷非遞歸遍
3、歷先序遍歷中序遍歷后序遍歷先序遍歷中序遍歷后序遍歷 此次課程設(shè)計(jì)所用的三組二叉樹 AACBCB DFEEFDGHABFGCDEH本設(shè)計(jì)所使用的存儲(chǔ)結(jié)構(gòu):typedef char ElemType;/定義二叉樹結(jié)點(diǎn)值的類型為字符型typedef struct bnode/二叉鏈表結(jié)構(gòu)定義ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;typedef struct BTree ptr; int tag;stacknode;3.詳細(xì)設(shè)計(jì)void CreateBTree(BTree &T)/按先序次序輸入,構(gòu)造二叉鏈表表示的二叉
4、樹T,#表示空樹char ch;ch=getchar(); if(ch='#') T=NULL;/讀入#時(shí),將相應(yīng)節(jié)點(diǎn)指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創(chuàng)建失敗!");/生成結(jié)點(diǎn)空間T->data=ch;CreateBTree(T->lchild);/構(gòu)造二叉樹的左子樹CreateBTree(T->rchild);/構(gòu)造二叉樹的右子樹void PreOrder(BTree T)/遞歸先序遍歷if(T)printf("%c ",T->data);
5、PreOrder(T->lchild);PreOrder(T->rchild);void InOrder(BTree T)/遞歸中序遍歷if(T)InOrder(T->lchild);printf("%c ",T->data);InOrder(T->rchild);void PostOrder(BTree T)/遞歸后序遍歷if(T)PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T->data);void LevelOrder(BTree T)
6、/層序遍歷BTree QMAX;int front=0,rear=0;BTree p;if(T) /根結(jié)點(diǎn)入隊(duì)Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊(duì)頭元素出隊(duì)front=(front+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空,入隊(duì)Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空,入隊(duì)Qrear=p->rchild;rear=(rear+1)%MAX
7、;void NRPreOrder(BTree bt)/非遞歸先序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0) while(p!=NULL) printf("%c",p->data);stacktop=p;/預(yù)留p指針在數(shù)組中top+;p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild;/*左子樹為空,進(jìn)右子樹*/void NRInOrder(BTree bt)/非遞歸中序遍歷BTree sta
8、ckMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0)while(p!=NULL) stacktop=p; /預(yù)留p指針在數(shù)組中top+;p=p->lchild; if (top>0)top-; p=stacktop;printf("%c",p->data); p=p->rchild;/*左子樹為空,進(jìn)右子樹*/void NRPostOrder(BTree bt)/非遞歸后序遍歷 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL)
9、top=0;p=bt;dowhile (p!=NULL) /遍歷左子樹stop.ptr = p; stop.tag = 1; /標(biāo)記為左子樹top+;p=p->lchild;while (top>0 && stop-1.tag=2)x = s-top;p = x.ptr;printf("%c",p->data); /tag為R,表示右子樹訪問完畢,故訪問根結(jié)點(diǎn) if (top>0)stop-1.tag =2; /遍歷右子樹p=stop-1.ptr->rchild; while (top>0);4.調(diào)試分析 一組測(cè)試樹 運(yùn)行
10、時(shí)界面 5.課程總結(jié)這個(gè)程序的代碼較為簡(jiǎn)單,可以實(shí)現(xiàn)了二叉樹的三種遞歸遍歷算法和三種非遞歸遍歷算法還有層序遍歷算法,想要改進(jìn)的話可以在選擇功能上下手,建立的時(shí)候提示更人性化,對(duì)輸入的數(shù)據(jù)進(jìn)行有效性驗(yàn)證,也可以改進(jìn)為對(duì)遍歷算法進(jìn)行選擇等等。二叉樹這個(gè)數(shù)據(jù)結(jié)構(gòu)幾乎在每一本的數(shù)據(jù)結(jié)構(gòu)的書都作為重點(diǎn)內(nèi)容講述,足見其在算法和程序設(shè)計(jì)界的重要地位。但是,到目前為止,自己還沒有真正體驗(yàn)到它的威力,可能是學(xué)習(xí)的還不夠深刻。像二叉樹遍歷的算法,用遞歸的算法只是簡(jiǎn)單的幾行代碼,然后就可以實(shí)現(xiàn)輸出遍歷次序。對(duì)于非遞歸的思想,要用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu),但是對(duì)于二叉樹遍歷問題來說非遞歸要較遞歸復(fù)雜。程序一開始總是出現(xiàn)語法錯(cuò)
11、誤,改了很多次也上網(wǎng)查了相關(guān)資料,才最后改為現(xiàn)在可以成功運(yùn)行的程序。在這個(gè)過程中,我體會(huì)到開發(fā)工程師的感覺了,就是要用挑剔的眼光想問題并且不斷地改進(jìn)自己的程序。通過這次課程設(shè)計(jì)逐漸提高了自己的程序設(shè)計(jì)和調(diào)試能力,通過上機(jī)實(shí)習(xí),嚴(yán)整自己設(shè)計(jì)算法的正確性,學(xué)會(huì)了有效利用基本調(diào)試方法,查找出代碼中的錯(cuò)誤并且修改。我會(huì)繼續(xù)我的興趣編寫程序的,相信在越來越多的嘗試之后,自己會(huì)不斷進(jìn)步和提高。6.附錄#include <stdlib.h>#include <stdio.h>#include<iostream.h>#define MAX 10 /結(jié)點(diǎn)個(gè)數(shù)不超過10個(gè)typ
12、edef char ElemType;/定義二叉樹結(jié)點(diǎn)值的類型為字符型typedef struct bnode/二叉鏈表結(jié)構(gòu)定義ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;void CreateBTree(BTree &T)/按先序次序輸入,構(gòu)造二叉鏈表表示的二叉樹T,#表示空樹char ch;ch=getchar(); if(ch='#') T=NULL;/讀入#時(shí),將相應(yīng)節(jié)點(diǎn)指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創(chuàng)建失敗
13、!");/生成結(jié)點(diǎn)空間T->data=ch;CreateBTree(T->lchild);/構(gòu)造二叉樹的左子樹CreateBTree(T->rchild);/構(gòu)造二叉樹的右子樹void PreOrder(BTree T)/遞歸先序遍歷if(T)printf("%c ",T->data);PreOrder(T->lchild);PreOrder(T->rchild);void InOrder(BTree T)/遞歸中序遍歷if(T)InOrder(T->lchild);printf("%c ",T->
14、;data);InOrder(T->rchild);void PostOrder(BTree T)/遞歸后序遍歷if(T)PostOrder(T->lchild);PostOrder(T->rchild);printf("%c ",T->data);void LevelOrder(BTree T)/層序遍歷BTree QMAX;int front=0,rear=0;BTree p;if(T) /根結(jié)點(diǎn)入隊(duì)Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊(duì)頭元素出隊(duì)front=(front
15、+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空,入隊(duì)Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空,入隊(duì)Qrear=p->rchild;rear=(rear+1)%MAX;void NRPreOrder(BTree bt)/非遞歸先序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0) while(p!=NULL) printf(
16、"%c",p->data);stacktop=p;/預(yù)留p指針在數(shù)組中top+;p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild;/*左子樹為空,進(jìn)右子樹*/void NRInOrder(BTree bt)/非遞歸中序遍歷BTree stackMAX,p;int top;if (bt!=NULL)top=0;p=bt;while(p!=NULL|top>0)while(p!=NULL) stacktop=p; /預(yù)留p指針在數(shù)組中top+;p=p->lchild; if (top&
17、gt;0)top-; p=stacktop;printf("%c",p->data); p=p->rchild;/*左子樹為空,進(jìn)右子樹*/typedef struct BTree ptr; int tag;stacknode;void NRPostOrder(BTree bt)/非遞歸后序遍歷 stacknode sMAX,x; BTree p=bt;int top;if(bt!=NULL) top=0;p=bt;dowhile (p!=NULL) /遍歷左子樹stop.ptr = p; stop.tag = 1; /標(biāo)記為左子樹top+;p=p->lc
18、hild;while (top>0 && stop-1.tag=2)x = s-top;p = x.ptr;printf("%c",p->data); /tag為R,表示右子樹訪問完畢,故訪問根結(jié)點(diǎn) if (top>0)stop-1.tag =2; /遍歷右子樹p=stop-1.ptr->rchild; while (top>0);void main()/主函數(shù)BTree T;T=NULL;int select;while(1)printf("nnn請(qǐng)選擇要執(zhí)行的操作:n");printf("1.創(chuàng)建二叉樹n");printf("2.二叉樹的遞歸遍歷算法(前、中、后)n");printf("3.二叉樹的層次遍歷算法n");printf("4.二叉樹的非遞歸遍歷算法(前、中、后)n"); printf("0.退出n");printf("輸入:"); cin>>select;switch(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 中國(guó)古代建筑文化的特色試題及答案
- 2025衛(wèi)生資格考試的復(fù)習(xí)進(jìn)度與試題與答案
- 經(jīng)濟(jì)法概論備考攻略及試題與答案
- 2025年行政管理運(yùn)行機(jī)制試題及答案
- 行政管理2025年自考英雄試題及答案分析
- 行政法學(xué)的未來研究愿景試題與答案
- 護(hù)士臨床思維能力試題及答案
- 衛(wèi)生資格考試復(fù)習(xí)計(jì)劃試題及答案制定
- 第2節(jié) 排列與組合
- 制圖員三級(jí)理論復(fù)習(xí)試題附答案
- 京東考試答案
- 畢業(yè)論文指導(dǎo)教師指導(dǎo)記錄6篇
- 跨越架施工方案
- 古書院礦1.2Mt新井設(shè)計(jì)(機(jī)械CAD圖紙)
- 財(cái)產(chǎn)和行為稅納稅申報(bào)表
- 人民幣全版(錢幣)教學(xué)打印版word版
- 貝氏體鋼軌超高周疲勞行為的研究課件
- 人員能力矩陣圖
- 多智能體系統(tǒng)教材課件匯總完整版ppt全套課件最全教學(xué)教程整本書電子教案全書教案課件合集
- 購(gòu)物中心租金修正測(cè)算
- 冀教版八年級(jí)下冊(cè)nit 5 Buying and Selling Lesson 30 A Cookie Sale課件(共13張PPT)
評(píng)論
0/150
提交評(píng)論