數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實(shí)驗(yàn)10

浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)十二叉樹的基本操作學(xué)生姓名專業(yè)班級學(xué)號(hào)實(shí)驗(yàn)成績指導(dǎo)老師（簽名）日期實(shí)驗(yàn)?zāi)康暮鸵?、掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2、掌握在二叉鏈表上的二叉樹操作的實(shí)現(xiàn)原理與方法。3、進(jìn)一步掌握遞歸算法的設(shè)計(jì)方法。實(shí)驗(yàn)內(nèi)容1、建立頭文件test10.h，定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并編寫二叉樹的各種基本操作實(shí)現(xiàn)函數(shù)。同時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件test10.cpp，編譯并調(diào)試程序，直到正確運(yùn)行。說明：二叉樹的基本操作可包括：(1)voidInitBTree(BTreeNode*&BT)//初始化二叉樹BT(2)voidCreateBTree(BTreeNode*&BT,char*a)//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲(chǔ)結(jié)構(gòu)(3)intEmptyBTree(BTreeNode*BT)//檢查二叉樹BT是否為空，空返回1，否則返回0(4)intDepthBTree(BTreeNode*BT)//求二叉樹BT的深度并返回該值(5)intFindBTree(BTreeNode*BT,ElemTypex)//查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回1，否則返回0(6)voidPreOrder(BTreeNode*BT)//先序遍歷二叉樹BT(7)voidInOrder(BTreeNode*BT)//中序遍歷二叉樹BT(8)voidPostOrder(BTreeNode*BT)//后序遍歷二叉樹BT(9)voidLevelOrder(BTreeNode*BT)//按層次遍歷二叉樹BT(10)voidPrintBTree(BTreeNode*BT)//輸出二叉樹BT(11)voidClearBTree(BTreeNode*&BT)//清除二叉樹BT2、以下內(nèi)容為第二次實(shí)驗(yàn)完成：(1)請編寫函數(shù)實(shí)現(xiàn)中序遍歷的非遞歸算法。將此函數(shù)輸入到前述頭文件test10.h中，并在主函數(shù)文件test10.cpp中增加測試語句測試這個(gè)函數(shù)的正確性。注意需要用到棧的有關(guān)操作，可使用已編制過的棧的基本操作文件test9_stack.h來實(shí)現(xiàn)。提示：二叉樹中序遍歷的非遞歸算法就是運(yùn)用棧這種數(shù)據(jù)結(jié)構(gòu)將遞歸的中序遍歷轉(zhuǎn)換成非遞歸的中序遍歷，采用的是間接轉(zhuǎn)換方式。中序遍歷非遞歸算法的N-S流程圖如下：注意：棧中存放的應(yīng)該是指向結(jié)點(diǎn)的指針，即結(jié)點(diǎn)的地址，而不是結(jié)點(diǎn)的值。因?yàn)?，只有根?jù)結(jié)點(diǎn)的地址才能在二叉樹中查找到該結(jié)點(diǎn)。(2)完成以下算法的設(shè)計(jì)，并將這些函數(shù)輸入到前述頭文件test10.h中，在主函數(shù)文件test10.cpp中增加測試語句測試其正確性。(a)將二叉樹中的所有結(jié)點(diǎn)的左右子樹進(jìn)行交換，函數(shù)原型如下：IntChangeBTree(BTreeNode*BT);(b)統(tǒng)計(jì)二叉樹中的所有結(jié)點(diǎn)數(shù)，函數(shù)原型如下：IntCountBTree(BTreeNode*BT);(c)復(fù)制一棵二叉樹，并返回復(fù)制得到的二叉樹根結(jié)點(diǎn)指針，函數(shù)原型如下：BTreeNode*CopyBTree(BTreeNode*BT);3、填寫實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告文件取名為report10.doc。4、上傳實(shí)驗(yàn)報(bào)告文件report10.doc、源程序文件test10.cpp及test10.h到Ftp服務(wù)器上（40:5000）自己的文件夾下。三.函數(shù)的功能說明及算法思路（包括每個(gè)函數(shù)的功能說明，及一些重要函數(shù)的算法實(shí)現(xiàn)思路）voidInitBTree(BTreeNode*&BT)//初始化二叉樹BT{ BT=NULL;}voidCreateBTree(BTreeNode*&BT,char*a)//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲(chǔ)結(jié)構(gòu){ constintMaxSize=10; BTreeNode*s[MaxSize]; inttop=-1; BT=NULL; BTreeNode*p; intk; inti=0; while(a[i]){ switch(a[i]){ case'':break; case'(': if(top==MaxSize-1){ cout<<"?？臻g太小，請?jiān)黾覯axSize的值！"<<endl; exit(2); } top++;s[top]=p;k=1; break; case',':k=2;break; default: p=newBTreeNode; p->data=a[i];p->left=p->right=NULL; if(BT==NULL)BT=p; else{ if(k==1)s[top]->left=p; elses[top]->right=p; } } i++; }}intEmptyBTree(BTreeNode*BT)//檢查二叉樹BT是否為空，空返回1，否則返回0{ returnBT==NULL;}intDepthBTree(BTreeNode*BT)//求二叉樹BT的深度并返回該值{ if(BT==NULL) return0; else{ intdep1=DepthBTree(BT->left); intdep2=DepthBTree(BT->right); if(dep1>dep2) returndep1+1; elsereturndep2+1;}intFindBTree(BTreeNode*BT,ElemTypex)//查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回1，否則返回0{ if(BT==NULL)returnfalse; else{ if(BT->data==x){ x=BT->data;returntrue; } else{ if(FindBTree(BT->left,x))returntrue; if(FindBTree(BT->right,x))returntrue; returnfalse; } }}voidPreOrder(BTreeNode*BT)//先序遍歷二叉樹BT{ if(BT!=NULL){ cout<<BT->data<<''; PreOrder(BT->left); PreOrder(BT->right); }}voidInOrder(BTreeNode*BT)//中序遍歷二叉樹BT{ if(BT!=NULL){ InOrder(BT->left); cout<<BT->data<<''; InOrder(BT->right); }}voidPostOrder(BTreeNode*BT)//后序遍歷二叉樹BT{ if(BT!=NULL){ PostOrder(BT->left); PostOrder(BT->right); cout<<BT->data<<''; }}voidLevelOrder(BTreeNode*BT)//按層次遍歷二叉樹BT{ constintMaxSize=30; BTreeNode*q[MaxSize]; intfront=0,rear=0; BTreeNode*p; if(BT!=NULL){ rear=(rear+1)%MaxSize; q[rear]=BT; } while(front!=rear){ front=(front+1)%MaxSize; p=q[front]; cout<<p->data<<''; if(p->left!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->right; } }}voidPrintBTree(BTreeNode*BT)//輸出二叉樹BT{ if(BT!=NULL){ cout<<BT->data; if(BT->left!=NULL||BT->right!=NULL){ cout<<'('; PrintBTree(BT->left); if(BT->right!=NULL) cout<<','; PrintBTree(BT->right); cout<<'('; } }} voidClearBTree(BTreeNode*&BT)//清除二叉樹BT{ if(BT!=NULL){ ClearBTree(BT->left); ClearBTree(BT->right); deleteBT; BT=NULL; }}四.實(shí)驗(yàn)結(jié)果與分析（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）五.心得體會(huì)（記錄實(shí)驗(yàn)感受、上機(jī)過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）【附錄----源程序】Test10.hvoidInitBTree(BTreeNode*&BT)//初始化二叉樹BT{ BT=NULL;}voidCreateBTree(BTreeNode*&BT,char*a){//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲(chǔ)結(jié)構(gòu) constintMaxSize=10; BTreeNode*s[MaxSize]; inttop=-1; BT=NULL; BTreeNode*p; intk; inti=0; while(a[i]){ switch(a[i]){ case'': break; case'(': if(top==MaxSize-1){ cout<<"?？臻g太小，請?jiān)黾覯axSize的值！"<<endl; exit(1); } top++;s[top]=p;k=1; break; case')': if(top==-1){ cout<<"二叉樹廣義表字符串錯(cuò)！"<<endl;exit(1); } top--;break; case',': k=2;break; default: p=newBTreeNode; p->data=a[i];p->left=p->right=NULL; if(BT==NULL)BT=p; else{ if(k==1)s[top]->left=p; elses[top]->right=p; } } i++; }}intEmptyBTree(BTreeNode*BT){//檢查二叉樹BT是否為空，空返回1，否則返回0 returnBT==NULL;}intDepthBTree(BTreeNode*BT)//求二叉樹BT的深度并返回該值{ if(BT==NULL) return0; else{ intdep1=DepthBTree(BT->left); intdep2=DepthBTree(BT->right); if(dep1>dep2) returndep1+1; else returndep2+1; }}intFindBTree(BTreeNode*BT,ElemTypex){//查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回1，否則返回0 if(BT==NULL)returnfalse; else{ if(BT->data==x){ x=BT->data;returntrue; } else{ if(FindBTree(BT->left,x))returntrue; if(FindBTree(BT->right,x))returntrue; returnfalse; } }}voidPreOrder(BTreeNode*BT)//先序遍歷二叉樹BT{ if(BT!=NULL){ cout<<BT->data<<''; PreOrder(BT->left); PreOrder(BT->right); }}voidInOrder(BTreeNode*BT)//中序遍歷二叉樹BT{ if(BT!=NULL){ InOrder(BT->left); cout<<BT->data<<''; InOrder(BT->right); }}voidPostOrder(BTreeNode*BT)//后序遍歷二叉樹BT{ if(BT!=NULL){ PostOrder(BT->left); PostOrder(BT->right); cout<<BT->data<<''; }}voidLevelOrder(BTreeNode*BT)//按層次遍歷二叉樹BT{ constintMaxSize=30; BTreeNode*q[MaxSize]; intfront=0,rear=0; BTreeNode*p; if(BT!=NULL){ rear=(rear+1)%MaxSize; q[rear]=BT; } while(front!=rear){ front=(front+1)%MaxSize; p=q[front]; cout<<p->data<<''; if(p->left!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->right; } }}voidPrintBTree(BTreeNode*BT)//輸出二叉樹BT{ if(BT!=NULL){ cout<<BT->data; if(BT->left!=NULL||BT->right!=NULL){ cout<<','; PrintBTree(BT->right); cout<<')'; } }}voidClearBTree(BTreeNode*&BT)//清除二叉樹BT{ if(BT!=NULL){ ClearBTree(BT->le