實(shí)驗(yàn) 三 二叉樹(shù)的基本操作實(shí)現(xiàn)及其應(yīng)用

軟件114班李大寶201100834416第數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（三）姓名:李大寶學(xué)院：計(jì)算機(jī)學(xué)院班級(jí)：軟件114班實(shí)驗(yàn)三二叉樹(shù)的基本操作實(shí)現(xiàn)及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?．熟悉二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹(shù)的基本操作。2．掌握對(duì)二叉樹(shù)每一種操作的具體實(shí)現(xiàn)。3．學(xué)會(huì)利用遞歸方法編寫(xiě)對(duì)二叉樹(shù)這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。4.會(huì)用二叉樹(shù)解決簡(jiǎn)單的實(shí)際問(wèn)題。二、實(shí)驗(yàn)內(nèi)容題目一設(shè)計(jì)程序?qū)崿F(xiàn)二叉樹(shù)結(jié)點(diǎn)的類型定義和對(duì)二叉樹(shù)的基本操作。該程序包括二叉樹(shù)結(jié)構(gòu)類型以及每一種操作的具體的函數(shù)定義和主函數(shù)。1按先序次序建立一個(gè)二叉樹(shù)，2按（A:先序B:中序C:后序D:層序）遍歷輸出二叉樹(shù)的所有結(jié)點(diǎn)以上比做，以下選做3求二叉樹(shù)中所有結(jié)點(diǎn)數(shù)4求二叉樹(shù)的深度****************************************************************/*定義DataType為char類型*/typedefcharDataType;/*二叉樹(shù)的結(jié)點(diǎn)類型*/typedefstructBitNode{DataTypedata;structBitNode*lchild,*rchild;}*BitTree;相關(guān)函數(shù)聲明：1、/*初始化二叉樹(shù)，即把樹(shù)根指針置空*/voidBinTreeInit(BitTree&BT)2、/*按先序次序建立一個(gè)二叉樹(shù)*/voidBinTreeCreat(BitTree&BT)3、/*檢查二叉樹(shù)是否為空*/intBinTreeEmpty(BitTreeBT)（包括按、中序、后序、按層次）4、/*按任先序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/voidperordertraverse(BitTreeT)5、/*按任中序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/voidinordertraverse(BitTreeT)6、/*按任后序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/voidenordertraverse(BitTreeT)7、/*按任層序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/voidcengordertraverse(BitTreeT)8、/*求二叉樹(shù)的深度*/intBinTreeDepth(BitTreeBT)9、/*求二叉樹(shù)中所有結(jié)點(diǎn)數(shù)*/intBinTreeCount(BitTreeBT)相關(guān)函數(shù)的實(shí)現(xiàn)：1、/*初始化二叉樹(shù)，即把樹(shù)根指針置空*/voidBinTreeInit(BitTree&BT){if(!(BT=(BitNode*)malloc(sizeof(BitNode)))) exit(0);//為樹(shù)根指針申請(qǐng)空間，申請(qǐng)不到退出。 BT=NULL;}//把樹(shù)根指針置空,完成初始化。2、/*按先序次序建立一個(gè)二叉樹(shù)*/voidBinTreeCreat(BitTree&BT)//遞歸調(diào)用建立二叉樹(shù){charch;ch=getchar();//輸入字符。 if(ch=='')BT=NULL;//空格代表為空 else{//遞歸建立二叉樹(shù)。 if(!(BT=(BitNode*)malloc(sizeof(BitNode)))) exit(0);//為節(jié)點(diǎn)申請(qǐng)空間，申請(qǐng)不到退出。 BT->data=ch;//為節(jié)點(diǎn)賦值 BinTreeCreat(BT->lchild);//先建立左二叉樹(shù)。 BinTreeCreat(BT->rchild);}//再建立右二叉樹(shù)。}3、/*檢查二叉樹(shù)是否為空*/intBinTreeEmpty(BitTreeBT){if(BT)return0;//根節(jié)點(diǎn)不空，二叉樹(shù)就不空。返回0 return1;}//否則二叉樹(shù)就為空，則返回14、/*按任先序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/按遞歸的方法實(shí)現(xiàn)的遍歷。（中序，后序遍歷與此相同略）voidperordertraverse(BitTreeT)//二叉樹(shù)存在時(shí)。{if(T){printf("%c",T->data);//訪問(wèn)節(jié)點(diǎn)的值，把節(jié)點(diǎn)的值輸出 perordertraverse(T->lchild);//遞歸調(diào)用訪問(wèn)左節(jié)點(diǎn) perordertraverse(T->rchild);}//遞歸調(diào)用訪問(wèn)右節(jié)點(diǎn)}5、/*按任層序遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)*/層遍歷運(yùn)用到了STL里的隊(duì)列。//注：前面定義一個(gè)隊(duì)列queue<BitTree>mvoidcengordertraverse(BitTreeT){BitNode*p;//定義一個(gè)節(jié)點(diǎn)。 if(T){//二叉樹(shù)不空時(shí)。 m.push(T);//把節(jié)點(diǎn)放入隊(duì)列中。 while(!m.empty()){//隊(duì)列不空時(shí)。 p=m.front();m.pop();//訪問(wèn)頭結(jié)點(diǎn)的值，并把頭結(jié)點(diǎn)出隊(duì) printf("%c",p->data); if(p->lchild)m.push(p->lchild);//左孩子不空時(shí)把左孩子入隊(duì)。 if(p->rchild)m.push(p->rchild);}//右孩子不空時(shí)把右孩子入隊(duì)。 }}6、/*求二叉樹(shù)的深度*/intBinTreeDepth(BitTreeBT)//運(yùn)用遞歸求二叉樹(shù)的深度。{inta,b,count;//count用來(lái)記二叉樹(shù)的深度 if(BT==NULL)count=0;//二叉樹(shù)為空時(shí)，二叉樹(shù)的深度為0。 else{a=BinTreeDepth(BT->lchild);//遞歸調(diào)用求左子樹(shù)的深度。 b=BinTreeDepth(BT->rchild);//遞歸調(diào)用求右子樹(shù)的深度。 if(a>b)count=a+1;//樹(shù)的深度為左右子樹(shù)中最深的加1。 elsecount=b+1;} returncount;//返回二叉樹(shù)的高度。}7、/*求二叉樹(shù)中所有節(jié)點(diǎn)數(shù)*/intBinTreeCount(BitTreeBT)//運(yùn)用遞歸求二叉樹(shù)的節(jié)點(diǎn)數(shù)。{intcount=0,a,b;//count用來(lái)記二叉樹(shù)的節(jié)點(diǎn)數(shù) if(BT==NULL)count=0;//二叉樹(shù)為空時(shí)節(jié)點(diǎn)數(shù)為0 else{a=BinTreeCount(BT->lchild);//遞歸左子樹(shù)的節(jié)點(diǎn)數(shù) b=BinTreeCount(BT->rchild);//遞歸右子樹(shù)的節(jié)點(diǎn)數(shù) count=a+b+1;}//二叉樹(shù)樹(shù)的節(jié)點(diǎn)數(shù)為左右子樹(shù)的節(jié)點(diǎn)數(shù)之和再加1 returncount;//返回二叉樹(shù)的節(jié)點(diǎn)數(shù)。}8./*主界面讓界面看起來(lái)更美觀*/voidzhujiemian(){ cout<<endl; cout<<"\t\t\t\t數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三"<<endl; cout<<"\t\t"<<endl; cout<<"\t\t1初始化二叉樹(shù)"<<endl; cout<<"\t\t2按先序次序建立二叉樹(shù)"<<endl; cout<<"\t\t3判斷二叉樹(shù)是否為空"<<endl; cout<<"\t\t4遍歷二叉樹(shù)"<<endl; cout<<"\t\t5求二叉樹(shù)的深度"<<endl; cout<<"\t\t6求二叉樹(shù)中所有結(jié)點(diǎn)數(shù)"<<endl; cout<<"\t\t其他鍵退出"<<endl; cout<<"\t\t"<<endl; cout<<"\t請(qǐng)選擇要進(jìn)行操作的序號(hào)（1--6）:";}三、程序調(diào)試及運(yùn)行結(jié)果分析:1、主界面和初始化結(jié)果，運(yùn)行結(jié)果如圖。2、建立如圖所示二叉樹(shù)輸入hda(空格)(空格)c(空格)b(空格)(空格)gf(空格)e(空格)(空格)(空格)運(yùn)行結(jié)果如圖：3、遍歷二叉樹(shù)，運(yùn)行結(jié)果如圖：4、求二叉樹(shù)的深度，運(yùn)行結(jié)果如圖：5、求二叉樹(shù)的節(jié)點(diǎn)數(shù)，運(yùn)行結(jié)果如圖：四、實(shí)驗(yàn)總結(jié)： 通過(guò)這次實(shí)驗(yàn)我基本掌握了有關(guān)二叉樹(shù)的基本操作。例如二叉樹(shù)的建立，二叉樹(shù)的先序、中序、后序和層序的遍歷，二叉樹(shù)的深度，二叉樹(shù)的節(jié)點(diǎn)數(shù)。這些有關(guān)二叉樹(shù)的操作大都是利用遞歸實(shí)現(xiàn)的。通過(guò)這次實(shí)驗(yàn)不僅掌握了二叉樹(shù)的基本操作而且還熟練了有關(guān)遞歸算法的操作，因此對(duì)遞歸算法有了更深的理解，還明白了遞歸算法的實(shí)現(xiàn)的原理和過(guò)程。通過(guò)這次實(shí)驗(yàn)的二叉樹(shù)層序遍歷還復(fù)習(xí)了前面學(xué)過(guò)的有關(guān)關(guān)于隊(duì)列的操作。學(xué)習(xí)知識(shí)就是學(xué)習(xí)新知識(shí)的同時(shí)復(fù)習(xí)前面學(xué)習(xí)的東東西。五、程序清單#include<iostream>#include<cstdio>#include<stdlib.h>#include<malloc.h>#include<windows.h>#include<queue>usingnamespacestd;typedefchardatatype;typedefstructBitNode{datatypedata; structBitNode*lchild,*rchild;}*BitTree;queue<BitTree>m;voidBinTreeInit(BitTree&BT){if(!(BT=(BitNode*)malloc(sizeof(BitNode))))exit(0); BT=NULL;}voidBinTreeCreat(BitTree&BT){charch;ch=getchar();if(ch=='')BT=NULL; else{if(!(BT=(BitNode*)malloc(sizeof(BitNode))))exit(0); BT->data=ch;BinTreeCreat(BT->lchild);BinTreeCreat(BT->rchild);}}intBinTreeEmpty(BitTreeBT){if(BT)return0;elsereturn1;}voidperordertraverse(BitTreeT){if(T){printf("%c",T->data);perordertraverse(T->lchild);perordertraverse(T->rchild);}}voidinordertraverse(BitTreeT){if(T){inordertraverse(T->lchild);printf("%c",T->data); inordertraverse(T->rchild);}}voidenordertraverse(BitTreeT){if(T){enordertraverse(T->lchild);enordertraverse(T->rchild); printf("%c",T->data);}}voidcengordertraverse(BitTreeT){BitNode*p; if(T){m.push(T); while(!m.empty()) {p=m.front();m.pop();printf("%c",p->data);if(p->lchild)m.push(p->lchild); if(p->rchild)m.push(p->rchild);} }}intBinTreeDepth(BitTreeBT){inta,b,count;if(BT==NULL)count=0; else{a=BinTreeDepth(BT->lchild); b=BinTreeDepth(BT->rchild); if(a>b)count=a+1;elsecount=b+1;}returncount;}intBinTreeCount(BitTreeBT){intcount=0,a,b;if(BT==NULL)count=0; else{a=BinTreeCount(BT->lchild);b=BinTreeCount(BT->rchild); count=a+b+1;} returncount;}voidzhujiemian(){cout<<endl; cout<<"\t\t\t\t數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三"<<endl; cout<<"\t\t"<<endl; cout<<"\t\t1初始化二叉樹(shù)"<<endl; cout<<"\t\t2按先序次序建立二叉樹(shù)"<<endl; cout<<"\t\t3判斷二叉樹(shù)是否為空"<<endl; cout<<"\t\t4遍歷二叉樹(shù)"<<endl; cout<<"\t\t5求二叉樹(shù)的深度"<<endl; cout<<"\t\t6求二叉樹(shù)中所有結(jié)點(diǎn)數(shù)"<<endl; cout<<"\t\t其他鍵退出"<<endl; cout<<"\t\t"<<endl; cout<<"\t請(qǐng)選擇要進(jìn)行操作的序號(hào)（1--6）:";}intmain(){BitTreeT;chara;zhujiemian();cin>>a; while(a!='1') {cout<<"輸入錯(cuò)誤，必須先初始化，請(qǐng)重新輸入：";getchar();cin>>a;}cout<<endl; do{switch(a) {case'1':BinTreeInit(T); cout<<"初始化成功！"<<endl;break; case'2':getchar(); cout<<"請(qǐng)輸入字符(空格代表空)："; BinTreeCreat(T);break; case'3': if(BinTreeEmpty(T)==1)cout<<"此二叉樹(shù)為空！"<<endl; elsecout<<"此二叉樹(shù)不空！"<<endl;break; c