數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(先中后序遍歷)

1、安徽工程大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計 說 明 書   學(xué)生姓名: 劉超學(xué) 號：3120702109 學(xué) 院:計算機與信息學(xué)院專 業(yè):信息與計算科學(xué)題 目:二叉樹的創(chuàng)建和遍歷指導(dǎo)教師潘海玉    2014年8月25日目錄1. 需求分析-12. 概要設(shè)計-13. 詳細設(shè)計-34. 調(diào)試分析-95. 課程總結(jié)-106. 附錄 -121. 需求分析問題描述：根據(jù)運行時輸入的先序序列，創(chuàng)建一棵二叉樹，分別對其 進行先序、中序、后序、層序遍歷，并顯示遍歷結(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() /二叉樹的建立與遍歷實現(xiàn)2.概要設(shè)計此次課程設(shè)計遍歷算法的框架圖層序遍歷遍歷算法遞歸遍歷非遞歸遍

3、歷先序遍歷中序遍歷后序遍歷先序遍歷中序遍歷后序遍歷 此次課程設(shè)計所用的三組二叉樹 AACBCB DFEEFDGHABFGCDEH本設(shè)計所使用的存儲結(jié)構(gòu)：typedef char ElemType;/定義二叉樹結(jié)點值的類型為字符型typedef struct bnode/二叉鏈表結(jié)構(gòu)定義ElemType data;struct bnode *lchild,*rchild;Bnode,* BTree;typedef struct BTree ptr; int tag;stacknode;3.詳細設(shè)計void CreateBTree(BTree &T)/按先序次序輸入，構(gòu)造二叉鏈表表示的二叉

4、樹T，#表示空樹char ch;ch=getchar(); if(ch='#') T=NULL;/讀入#時，將相應(yīng)節(jié)點指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創(chuàng)建失敗!");/生成結(jié)點空間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é)點入隊Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊頭元素出隊front=(front+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空，入隊Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空，入隊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;/*左子樹為空，進右子樹*/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;/*左子樹為空，進右子樹*/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é)點 if (top>0)stop-1.tag =2; /遍歷右子樹p=stop-1.ptr->rchild; while (top>0);4.調(diào)試分析 一組測試樹 運行

10、時界面 5.課程總結(jié)這個程序的代碼較為簡單，可以實現(xiàn)了二叉樹的三種遞歸遍歷算法和三種非遞歸遍歷算法還有層序遍歷算法，想要改進的話可以在選擇功能上下手，建立的時候提示更人性化，對輸入的數(shù)據(jù)進行有效性驗證，也可以改進為對遍歷算法進行選擇等等。二叉樹這個數(shù)據(jù)結(jié)構(gòu)幾乎在每一本的數(shù)據(jù)結(jié)構(gòu)的書都作為重點內(nèi)容講述，足見其在算法和程序設(shè)計界的重要地位。但是，到目前為止，自己還沒有真正體驗到它的威力，可能是學(xué)習(xí)的還不夠深刻。像二叉樹遍歷的算法，用遞歸的算法只是簡單的幾行代碼，然后就可以實現(xiàn)輸出遍歷次序。對于非遞歸的思想，要用到棧這個數(shù)據(jù)結(jié)構(gòu)，但是對于二叉樹遍歷問題來說非遞歸要較遞歸復(fù)雜。程序一開始總是出現(xiàn)語法錯

11、誤，改了很多次也上網(wǎng)查了相關(guān)資料，才最后改為現(xiàn)在可以成功運行的程序。在這個過程中，我體會到開發(fā)工程師的感覺了，就是要用挑剔的眼光想問題并且不斷地改進自己的程序。通過這次課程設(shè)計逐漸提高了自己的程序設(shè)計和調(diào)試能力，通過上機實習(xí)，嚴整自己設(shè)計算法的正確性，學(xué)會了有效利用基本調(diào)試方法，查找出代碼中的錯誤并且修改。我會繼續(xù)我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步和提高。6.附錄#include <stdlib.h>#include <stdio.h>#include<iostream.h>#define MAX 10 /結(jié)點個數(shù)不超過10個typ

12、edef char ElemType;/定義二叉樹結(jié)點值的類型為字符型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;/讀入#時，將相應(yīng)節(jié)點指針置空elseif(!(T=(Bnode *)malloc(sizeof(Bnode) printf("創(chuàng)建失敗

13、!");/生成結(jié)點空間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é)點入隊Qrear=T;rear=(rear+1)%MAX; while(front!=rear)p=Qfront; /隊頭元素出隊front=(front

15、+1)%MAX; printf("%c ",p->data);if(p->lchild) /左孩子不為空，入隊Qrear=p->lchild;rear=(rear+1)%MAX;if(p->rchild) /右孩子不為空，入隊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;/*左子樹為空，進右子樹*/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;/*左子樹為空，進右子樹*/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é)點 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請選擇要執(zhí)行的操作:n");printf("1.創(chuàng)建二叉樹n");printf("2.二叉樹的遞歸遍歷算法（前、中、后）n");printf("3.二叉樹的層次遍歷算法n");printf("4.二叉樹的非遞歸遍歷算法（前、中、后）n"); printf("0.退出n");printf("輸入："); cin>>select;switch(