數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)綜合實(shí)驗(yàn)報(bào)告(共14頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上武 漢 工 程 大 學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2專(zhuān)業(yè)班級(jí)智能01實(shí)驗(yàn)地點(diǎn)機(jī)電大樓4 樓 419 機(jī)房學(xué)生學(xué)號(hào)指導(dǎo)教師學(xué)生姓名實(shí)驗(yàn)時(shí)間第 12 周第14 周 星期2 實(shí)驗(yàn)項(xiàng)目樹(shù)性結(jié)構(gòu)的綜合使用實(shí)驗(yàn)類(lèi)別操作性（） 驗(yàn)證性（ ） 設(shè)計(jì)性（ ） 綜合性（ ） 其它（ ）實(shí)驗(yàn)?zāi)康募耙?.實(shí)現(xiàn)二叉樹(shù)的先序，中序與后序遍歷的遞歸算法與非遞歸算法。2.求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，葉子結(jié)點(diǎn)個(gè)數(shù)，二叉樹(shù)的高度，度為2的結(jié)點(diǎn)個(gè)數(shù)。成 績(jī) 評(píng) 定 表類(lèi) 別評(píng) 分 標(biāo) 準(zhǔn)分值得分合 計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律認(rèn)真完成設(shè)計(jì)任務(wù)30分報(bào)告質(zhì)量操作規(guī)范、功能正確填寫(xiě)完整、體現(xiàn)收獲70分說(shuō)明：

2、 評(píng)閱教師： 日 期： 20 年 月 日實(shí) 驗(yàn) 內(nèi) 容一實(shí)驗(yàn)內(nèi)容1.實(shí)現(xiàn)二叉樹(shù)的先序，中序與后序遍歷的遞歸算法與非遞歸算法。2.求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，葉子結(jié)點(diǎn)個(gè)數(shù)，二叉樹(shù)的高度，度為2的結(jié)點(diǎn)個(gè)數(shù)。二程序的設(shè)計(jì)思想1實(shí)現(xiàn)二叉樹(shù)的先序，中序與后序遍歷的遞歸算法與非遞歸算法。先構(gòu)造二叉樹(shù)，根據(jù)先序遍歷的思想，輸入根后，再輸入左子樹(shù)，直至左子樹(shù)為空則輸入上一層右字樹(shù)。（1）二叉樹(shù)的非遞歸遍歷是用顯示棧來(lái)存儲(chǔ)二叉樹(shù)的結(jié)點(diǎn)指針，先序遍歷時(shí)，按二叉樹(shù)前序遍歷的順序訪問(wèn)結(jié)點(diǎn)，并將結(jié)點(diǎn)的指針入棧，直到棧頂指針指向結(jié)點(diǎn)的左指針域?yàn)榭諘r(shí)取出棧頂指針并刪除棧頂指針，訪問(wèn)剛?cè)〕龅闹羔樦赶虻慕Y(jié)點(diǎn)的右指針指向的結(jié)點(diǎn)并將其指針

3、入棧，如此反復(fù)執(zhí)行則為非遞歸操作。（2）二叉樹(shù)的遞歸遍歷：若二叉樹(shù)為空，則空操作先序遍歷：（a）訪問(wèn)根結(jié)點(diǎn)； （b）先序遍歷左子樹(shù)；（c）先序遍歷右子樹(shù)。中序遍歷 ： （a）中序遍歷左子樹(shù)； （b）訪問(wèn)根結(jié)點(diǎn)；（c）中序遍歷右子樹(shù)后序遍歷： （a）后序遍歷左子樹(shù)； （b）后序遍歷右子樹(shù)； （c）訪問(wèn)根結(jié)點(diǎn)。2.求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，葉子結(jié)點(diǎn)個(gè)數(shù)，二叉樹(shù)的高度，度為2的結(jié)點(diǎn)個(gè)數(shù)。（1）求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)：先分別求得左右子樹(shù)中個(gè)葉子結(jié)點(diǎn)的個(gè)數(shù)，再計(jì)算出兩者之和即為二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)。（2）二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)之和：先分別求得左子樹(shù)右子樹(shù)中結(jié)點(diǎn)之和，再計(jì)算兩者之和即為所求。（3）二叉樹(shù)的高度：首先判斷

4、二叉樹(shù)是否為空，若為空則此二叉樹(shù)高度為0,。否則，就先分別求出左右子樹(shù)的深度進(jìn)行比較，取較大的樹(shù)加一即為所求。（4）二叉樹(shù)的度為2的結(jié)點(diǎn)個(gè)數(shù)：計(jì)算有左右孩子的結(jié)點(diǎn)個(gè)數(shù)，即為度為2的結(jié)點(diǎn)個(gè)實(shí) 驗(yàn) 內(nèi) 容數(shù)。三編程過(guò)程中遇到的問(wèn)題及解決辦法（1）后續(xù)遍歷的非遞歸函數(shù)涉及到回溯的方法，開(kāi)始設(shè)計(jì)的方案想的太過(guò)于簡(jiǎn)單，所以形成了死循環(huán)，總是在最后的節(jié)點(diǎn)處不停地循環(huán)，后改成回溯后，該問(wèn)題得到解決。（2）計(jì)算二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)中，返回循環(huán)的時(shí)候不論根結(jié)點(diǎn)有沒(méi)有左右子樹(shù)，但個(gè)人設(shè)計(jì)時(shí)，根總是會(huì)將自己默認(rèn)為有左右子樹(shù)，自行增加1.后在同學(xué)幫助下才看到自己的這個(gè)失誤。四程序的閃光點(diǎn)(自我評(píng)價(jià))1.程序模塊化

5、，各個(gè)函數(shù)分開(kāi)描述，方便觀察2.關(guān)鍵處有注釋3.建立二叉樹(shù)時(shí)，用先序提示輸入，比較人性化。 五程序源代碼(以文件為單位提供)#include<iostream.h>#include<malloc.h>#define Maxsize 100typedef struct TREEstruct TREE *lTree;struct TREE *rTree;char data;Tree;void InitTree(Tree*);/初始化樹(shù)void CreatTree(Tree*);/創(chuàng)建二叉樹(shù)void PreTraverse(Tree*);/先序遍歷遞歸void PreOrde

6、rTraverse(Tree*);/先序遍歷非遞歸void InTraverse(Tree *tree);/中序遍歷遞歸void InOrderTraverse(Tree *tree);/中序遍歷非遞歸void PostTraverse(Tree *tree);/后序遍歷遞歸void LastOrderTraverse(Tree *tree);/后序遍歷非遞歸int DepthTree(Tree *tree);/計(jì)算樹(shù)的深度int LeafsTree(Tree *tree);/計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)int NodesTree(Tree *tree);/計(jì)算結(jié)點(diǎn)個(gè)數(shù)int Twochild(Tree*

7、tree);/計(jì)算度為二的結(jié)點(diǎn)個(gè)數(shù)void main()int H,L;Tree tree;/Tree m;InitTree(&tree);CreatTree(&tree);cout<<"先序遍歷遞歸為:"PreTraverse(&tree);/先序遍歷遞歸cout<<"先序遍歷非遞歸:"PreOrderTraverse(&tree);/先序遍歷非遞歸cout<<endl;cout<<"中序遍歷遞歸為:"InTraverse(&tree);/中序遍

8、歷遞歸cout<<"中序遍歷非遞歸:"InOrderTraverse(&tree);/中序遍歷非遞歸cout<<endl;cout<<"后序遍歷遞歸為:"PostTraverse(&tree);/后序遍歷遞歸cout<<"后序遍歷非遞歸:"LastOrderTraverse(&tree);/后序遍歷非遞歸cout<<endl; cout<<"樹(shù)的深度為:" H=DepthTree(&tree);cout<&

9、lt;H<<endl;cout<<"葉子結(jié)點(diǎn)個(gè)數(shù):"L=LeafsTree(&tree); cout<<L<<endl;cout<<"結(jié)點(diǎn)個(gè)數(shù)："cout<<NodesTree(&tree)<<endl;cout<<"度為二的結(jié)點(diǎn)個(gè)數(shù)"L=Twochild(&tree);cout<<L<<endl;void InitTree(Tree *tree)/初始化樹(shù)tree->lTree=NUL

10、L;tree->rTree=NULL;tree->data='0'void CreatTree(Tree *tree)/創(chuàng)建樹(shù)int n=0,m=0,i=0;if(tree->data='0')cout<<"請(qǐng)輸入該節(jié)點(diǎn)的數(shù)據(jù)："cin>>tree->data;cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有左子樹(shù)（0：沒(méi)有 1：有）："cin>>n;if(n=1)Tree *lTree=(Tr

11、ee*)malloc(sizeof(Tree);tree->lTree=lTree;lTree->lTree=NULL;lTree->rTree=NULL;lTree->data='0'CreatTree(tree->lTree);cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有右子樹(shù)（0：沒(méi)有 1：有）："cin>>i;if(i=0);else if(i=1)Tree *rTree=(Tree*)malloc(sizeof(Tree);tree-

12、>rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);else if(n=0)cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有右子樹(shù)（0：沒(méi)有 1：有）："cin>>m; if(m=0);else if(m=1)Tree *rTree=(Tree*)malloc(sizeof(Tree);tree->rTree=rTree;

13、rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);void PreTraverse(Tree*tree)/先序遍歷遞歸if(tree!=NULL)cout<<tree->data<<" "if(tree->lTree!=NULL)PreTraverse(tree->lTree);PreTraverse(tree->rTree);else if(tree->rTree!=NULL)Pre

14、Traverse(tree->rTree);else;void PreOrderTraverse(Tree *tree)/先序遍歷非遞歸Tree *S80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)cout<<tree->data<<" "top+;Stop = tree; tree = tree->lTree;elsetree = Stop;top-;tree = tree->rTree;void InTraverse(Tree *tree)/中序遍歷遞歸i

15、f(tree!=NULL)if(tree->lTree!=NULL)InTraverse(tree->lTree);cout<<tree->data<<" "InTraverse(tree->rTree);else if(tree->rTree!=NULL)cout<<tree->data<<" "InTraverse(tree->rTree);elsecout<<tree->data<<" "void InOrde

16、rTraverse(Tree *tree)/中序遍歷非遞歸Tree *D80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)top+;Dtop = tree; tree = tree->lTree;elsetree = Dtop;top-;cout<<tree->data<<" "tree = tree->rTree;void PostTraverse(Tree *tree)/后序遍歷遞歸if(tree!=NULL)if(tree->lTree!=NULL)Pos

17、tTraverse(tree->lTree);PostTraverse(tree->rTree);cout<<tree->data<<" "else if(tree->rTree!=NULL)PostTraverse(tree->rTree);cout<<tree->data<<" "elsecout<<tree->data<<" "void LastOrderTraverse(Tree *tree)/后序遍歷非遞歸Tre

18、e *stackMaxsize=NULL,*p;p=tree;int top=0,tag=1,i=0,k=0;while(p!=NULL | top)i=1;while(p!=NULL)stack+top=p;p=p->lTree;if(top!=0)p=stacktop->rTree;if(p=NULL)cout<<stacktop->data<<" "if(stacktop!=NULL)while(i)if(stacktop!=NULL)if(stacktop->rTree!=NULL)if(stacktop->rT

19、ree->data=stacktop+1->data)cout<<stacktop->data<<" "elsei=0;elsei=0;elsei=0;if(top!=0)p=stacktop->rTree;elsep=NULL;int DepthTree(Tree *tree) /深度函數(shù) int u,v; if (tree=NULL) return 0; u=DepthTree(tree->lTree); v=DepthTree(tree->rTree); if (u>v) return (u+1); return (v+1); int LeafsTree(Tree *tree)/子葉個(gè)數(shù)函數(shù) int num1,num2; if(tree=NULL) return 0; else if(tree->lTree=NULL&