(已處理)內(nèi)蒙古科技大學(xué)課程設(shè)計-二叉樹遍歷及應(yīng)用

1、遍歷二叉樹內(nèi)蒙古科技大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計題 目二叉樹遍歷及應(yīng)用學(xué) 號1376807435姓 名亢斌指導(dǎo)教師王麗穎日 期2015年6月30日目 錄一、問題描述1二、需求分析12.1主功能模塊12.2創(chuàng)建樹模塊12.3遍歷樹模塊1三、概要設(shè)計23.1主界面設(shè)計思想流程圖23.2. 創(chuàng)建二叉樹23.2.1二叉樹創(chuàng)建的思想23.2.2二叉樹創(chuàng)建的算法流程圖23.3.先序遞歸遍歷33.3.1先序遞歸遍歷思想33.3.2先序遞歸遍歷的算法流程圖33.4.中序遞歸遍歷33.4.1中序遞歸遍歷思想33.4.2中序遞歸遍歷的算法流程圖43.5.后序遞歸遍歷43.5.1后序遞歸遍歷思想43.5.2后序遞歸遍

2、歷的算法流程圖53.6.先序非遞歸遍歷53.6.1先序非遞歸遍歷思想53.6.2先序非遞歸遍歷的算法流程圖63.7.中序非遞歸遍歷63.7.1中序非遞歸遍歷思想63.7.2中序非遞歸遍歷的算法流程圖73.8.后序非遞歸遍歷73.8.1后序非遞歸遍歷思想73.8.2后序非遞歸遍歷的算法流程圖83.9.層序非遞歸遍歷83.9.1層序非遞歸遍歷思想83.9.2層序非遞歸遍歷的算法流程圖9四、詳細設(shè)計104.1界面設(shè)計104.2.詳細代碼分析114.2.1主模塊114.2.2創(chuàng)建樹模塊124.2.3遍歷樹模塊13五、調(diào)試分析135.1.調(diào)試結(jié)果135.1.1實驗數(shù)據(jù)135.1.2創(chuàng)建樹界面145.1.

3、3輸出結(jié)果界面14六、 總結(jié)附錄：程序代碼一、 問題描述建立二叉樹, 層序、先序、中序、后序遍歷.(用遞歸或非遞歸的方法都可以)要求能夠輸入樹的各個結(jié)點, 并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)、輸出中序遍歷序列的函數(shù)、輸出后序遍歷序列的函數(shù). 二、 需求分析在現(xiàn)實世界層次化的數(shù)據(jù)模型中, 數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系紛繁復(fù)雜. 其中很多關(guān)系無法使用簡單的線性結(jié)構(gòu)表示清楚, 比如祖先與后代的關(guān)系、整體與部分的關(guān)系等. 于是人們借鑒自然界中樹的形象創(chuàng)造了一種強大的非線性結(jié)構(gòu)樹. 樹形結(jié)構(gòu)的具體形式有很多種, 其中最常用的就是

4、二叉樹. 而二叉樹的多層次遍歷遍歷則是二叉樹的重要內(nèi)容. 本程序用Microsoft Visual C+ 6.0編寫, 可以實現(xiàn)對二叉樹的創(chuàng)建、采用遞歸和非遞歸等兩種方式先序、中序、后序進行遍歷. 2.1主功能模塊通過合理的界面設(shè)計, 根據(jù)提示信息, 使用者可以方便快捷地運行本程序來完成創(chuàng)建、遍歷二叉樹等操作. 界面美觀, 人性化, 程序智能, 安全性高. 2.2創(chuàng)建樹模塊當(dāng)進入程序運行界面后, 根據(jù)提示輸入需要建立的二叉樹, 按照先序次序輸入各個結(jié)點的值, 完成二叉樹的建立. 2.3遍歷樹模塊實現(xiàn)對該二叉樹的先序遞歸遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸

5、遍歷、層序非遞歸遍歷等方式的遍歷操作, 并輸出各遍歷序列. 三、 概要設(shè)計3.1主界面設(shè)計思想流程圖3.2. 創(chuàng)建二叉樹3.2.1二叉樹創(chuàng)建的思想(1)定義二叉樹結(jié)點值的類型為字符型. (2)結(jié)點個數(shù)不超過10個. (3)按先序次序輸入, 構(gòu)造二叉鏈表表示的二叉樹T, 空格表示空樹. 相關(guān)函數(shù)如下: void CreateBiTree(BiTree &T)3.2.2二叉樹創(chuàng)建的算法流程圖開始創(chuàng)建二叉樹結(jié)束3.3.先序遞歸遍歷3.3.1先序遞歸遍歷思想若二叉樹為空, 則空操作；否則(1)訪問根結(jié)點；(2)先序遍歷左子樹；(3)先序遍歷右子樹. 相關(guān)函數(shù)如下: void PreOrderT

6、raverse(BiTree T)3.3.2先序遞歸遍歷的算法流程圖開始判斷結(jié)點是否空訪問根結(jié)點結(jié)束按前根遍歷方式遍歷左子樹按前根遍歷方式遍歷右子樹YN3.4.中序遞歸遍歷3.4.1中序遞歸遍歷思想若二叉樹為空, 則空操作；否則(1)中序遍歷左子樹；(2)訪問根結(jié)點；(3)中序遍歷右子樹. 相關(guān)函數(shù)如下: void InOrderTraverse(BiTree T)3.4.2中序遞歸遍歷的算法流程圖開始判斷結(jié)點是否空按中根遍歷方式遍歷左子樹結(jié)束訪問根結(jié)點按中根遍歷方式遍歷右子樹YN3.5.后序遞歸遍歷3.5.1后序遞歸遍歷思想若二叉樹為空, 則空操作；否則(1)后序遍歷左子樹；(2)后序遍歷右

7、子樹；(3)訪問根結(jié)點. 相關(guān)函數(shù)如下: void PostOrderTraverse(BiTree T)3.5.2后序遞歸遍歷的算法流程圖開始判斷結(jié)點是否空按后根遍歷方式遍歷左子樹結(jié)束按后根遍歷方式遍歷右子樹訪問根結(jié)點YN3.6.先序非遞歸遍歷3.6.1先序非遞歸遍歷思想(1)訪問結(jié)點的數(shù)據(jù)域；(2)指針指向p的左孩子結(jié)點；(3)從棧中彈出棧頂元素；(4)指針指向p的右孩子結(jié)點. 相關(guān)函數(shù)如下: void NRPreOrder(BiTree bt)3.6.2先序非遞歸遍歷的算法流程圖開始申請一個STL棧stack<*> s判斷結(jié)點是否空輸出結(jié)點值p->datas.push(

8、p)結(jié)點的值變?yōu)樗淖蠛⒆优袛嘟Y(jié)點是否空p=s.pop()p=p->rchild結(jié)束判斷?；蚪Y(jié)點是否空NYNYN3.7.中序非遞歸遍歷3.7.1中序非遞歸遍歷思想(1)指針指向p的左孩子結(jié)點；(2)從棧中彈出棧頂元素；(3)訪問結(jié)點的數(shù)據(jù)域；(4)指針指向p的右孩子結(jié)點. 相關(guān)函數(shù)如下: void NRInOrder(BiTree bt)3.7.2中序非遞歸遍歷的算法流程圖開始申請一個STL棧stack<*> s判斷結(jié)點是否空s.push(p)結(jié)點的值變?yōu)樗淖蠛⒆优袛嘟Y(jié)點是否空輸出結(jié)點值p->datap=s.pop()p=p->rchild結(jié)束判斷?；蚪Y(jié)點是否空

9、NYYNN3.8.后序非遞歸遍歷3.8.1后序非遞歸遍歷思想若二叉樹為空, 則空操作；否則引入棧和標(biāo)記模擬遞歸工作棧, 初始時棧為空. 相關(guān)函數(shù)如下: void NRPostOrder(BiTree bt);3.8.2后序非遞歸遍歷的算法流程圖開始申請一個STL棧stack<*> s;用一個bool變量flag標(biāo)記是否訪問flag=0 s.push(p)p=p->lchild top+判斷標(biāo)志flag是否為1輸出結(jié)點的數(shù)據(jù)p->datap = s.pop()p= p->rchild結(jié)束NYYNNYYN判斷結(jié)點是否空判斷?；蚪Y(jié)點是否空判斷結(jié)點是否空3.9.層序非遞歸

10、遍歷3.9.1層序非遞歸遍歷思想(1)訪問該元素所指結(jié)點. (2)若該元素所指結(jié)點的左右孩子結(jié)點非空, 則該元素所指結(jié)點的左孩子指針和右孩子指針順序入隊. 相關(guān)函數(shù)如下: void LevelOrderTraverse(BiTree T)3.9.2層序非遞歸遍歷的算法流程圖開始申請一個STL隊列queue<*> q結(jié)束N判斷結(jié)點是否空Y判斷左結(jié)點是否空q.push(p->rchild)q.push(p->lchild)判斷右結(jié)點是否空q.push(root);判斷隊列是否為空p=q.front()；輸出結(jié)點值p->data; q.pop()YYNNYN四、 詳細設(shè)

11、計4.1界面設(shè)計圖4-1 系統(tǒng)運行主界面圖4-2 創(chuàng)建二叉樹界面圖4-3 二叉樹遞歸遍歷界面4.2.詳細代碼分析4.2.1主模塊本模塊定義了系統(tǒng)運行主界面的相關(guān)內(nèi)容和相關(guān)操作函數(shù), 源代碼如下: void main() BiTree T; T=NULL; int select; /cout<<"請按先序次序輸入各結(jié)點的值, 以空格表示空樹(輸入時可連續(xù)輸入):"<<endl;/ CreateBiTree(T); while(1) cout<<"nn請選擇要執(zhí)行的操作:n" cout<<"1.創(chuàng)建二

12、叉樹n" cout<<"2.二叉樹的遞歸遍歷算法（前、中、后）n" cout<<"3.二叉樹的層次遍歷算法n"cout<<"4.二叉樹的非遞歸遍歷算法（前、中、后）n" cout<<"0.退出n" cin>>select; switch(select) case 0:return; case 1: cout<<"請按先序次序輸入各結(jié)點的值, 以空格表示空樹(輸入時可連續(xù)輸入):"<<endl; Crea

13、teBiTree(T); break; case 2: if(!T) cout<<"未建立樹, 請先建樹！" else cout<<"n先序遍歷:n" PreOrderTraverse(T); cout<<"n中序遍歷:n" InOrderTraverse(T); cout<<"n后序遍歷:n" PostOrderTraverse(T); break; case 3: cout<<"n層序遍歷:n" LevelOrderTraverse

14、(T); break; case 4: if(!T) cout<<"未建立樹, 請先建樹！" else cout<<"n先序遍歷:n" NRPreOrder(T); cout<<"n中序遍歷:n" NRInOrder(T); cout<<"n后序遍歷:n" NRPostOrder(T); break; default: cout<<"請確認選擇項:n" /end switch /end while4.2.2創(chuàng)建樹模塊源代碼如下: voi

15、d CreateBiTree(BiTree &T)/按先序次序輸入, 構(gòu)造二叉鏈表表示的二叉樹T, 空格表示空樹/ if(T) return; char ch; ch=getchar(); /不能用cin來輸入, 在cin中不能識別空格. if(ch=' ') T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) cout<<"malloc fail!" T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild

16、); 4.2.3遍歷樹模塊本模塊包括了各種遍歷二叉樹的函數(shù), 源代碼如下: void PreOrderTraverse(BiTree T) /二叉樹的先序遍歷(遞歸)成員函數(shù)聲明void InOrderTraverse(BiTree T) /二叉樹的中序遍歷(遞歸)成員函數(shù)聲明void PostOrderTraverse(BiTree T) /二叉樹的后序遍歷(遞歸)成員函數(shù)聲明void LevelOrderTraverse(BiTree T) / 二叉樹的層序遍歷(非遞歸)成員函數(shù)聲明void NRPreOrder(BiTree bt) / 二叉樹的先序遍歷(非遞歸)成員函數(shù)聲明void N

17、RInOrder(BiTree bt) /二叉樹的中序遍歷(非遞歸)成員函數(shù)聲明void NRPostOrder(BiTree bt) /二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明五、 調(diào)試分析5.1.調(diào)試結(jié)果5.1.1實驗數(shù)據(jù)ABCDEFHG這棵樹是隨機畫的, 由數(shù)據(jù)結(jié)構(gòu)知識, 按照先序次序輸入各個節(jié)點的值為: ABD#CEG#F#H#(此處#代表空格). 在程序中輸入這些節(jié)點, 創(chuàng)建樹, 如下圖: 5.1.2創(chuàng)建樹界面圖5-1 創(chuàng)建樹界面5.1.3輸出結(jié)果界面輸入2, 輸出該二叉樹遞歸遍歷算法的遍歷結(jié)果, 結(jié)果如下: 輸入3, 輸出該二叉樹層序遍歷算法的遍歷結(jié)果, 結(jié)果如下: 輸入4, 輸出該

18、二叉樹非遞歸遍歷算法的遍歷結(jié)果, 結(jié)果如下: 六、總結(jié)感謝老師的指導(dǎo)！同時感謝同學(xué)的幫助。附錄：程序代碼#include "iostream"#include "stdlib.h"#include "stdio.h"using namespace std;typedef char ElemType;/定義二叉樹結(jié)點值的類型為字符型const int MaxLength=10;/結(jié)點個數(shù)不超過10個typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild; BT

19、Node,* BiTree;void CreateBiTree(BiTree &T) /按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空樹 char ch; ch=getchar(); /不能用cin來輸入，在cin中不能識別空格。 if(ch=' ') T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) cout<<"malloc fail!" T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild

20、); void PreOrderTraverse(BiTree T) /先序遍歷 if(T) cout<<T->data<<' ' PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); void InOrderTraverse(BiTree T) /中序遍歷 if(T) InOrderTraverse(T->lchild); cout<<T->data<<' ' InOrderTraverse(T->rchild);

21、void PostOrderTraverse(BiTree T) /后序遍歷 if(T) PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data<<' ' void LevelOrderTraverse(BiTree T) /層序遍歷 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根結(jié)點入隊 Qrear=T; rear=(rear+1)%MaxLength; while(front

22、!=rear) p=Qfront; /隊頭元素出隊 front=(front+1)%MaxLength; cout<<p->data<<' ' if(p->lchild) /左孩子不為空，入隊 Qrear=p->lchild; rear=(rear+1)%MaxLength; if(p->rchild) /右孩子不為空，入隊 Qrear=p->rchild; rear=(rear+1)%MaxLength; /非遞歸的先序遍歷算法void NRPreOrder(BiTree bt) BiTree stackMaxLength

23、,p; int top; if (bt!=NULL) top=0; p=bt; while(p!=NULL|top>0) while(p!=NULL) cout<<p->data; stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild; /非遞歸的中序遍歷算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0; p=bt; while(p!=NULL|top

24、>0) while(p!=NULL) stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop; cout<<p->data; p=p->rchild; /非遞歸的后序遍歷算法typedef struct BiTree ptr; int tag; stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0; p=bt; do while (p!=NU

25、LL) /遍歷左子樹 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; cout<<p->data; /tag為R，表示右子樹訪問完畢，故訪問根結(jié)點 if (top>0) stop-1.tag =2; /遍歷右子樹 p=stop-1.ptr->rchild; while (top>0); int main() BiTree T; T=NULL; int select; while(1) cout<<"nn請選擇要執(zhí)行的操作:n" cout<<"1.創(chuàng)建二叉樹n" cout<