實驗十一 二叉樹的進(jìn)一步操作

浙江大學(xué)城市學(xué)院實驗報告課程名稱 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 實驗項目名稱 實驗十一二叉樹的進(jìn)一步操作 學(xué)生姓名 專業(yè)班級 學(xué)號—實驗成績 指導(dǎo)老師(簽名) 日期2014-12-25實驗?zāi)康暮鸵?、 熟練掌握二叉樹二叉鏈表的存儲結(jié)構(gòu)。2、 進(jìn)一步掌握在二叉鏈表上的二叉樹操作的實現(xiàn)原理與方法。3、 掌握中序遍歷的非遞歸算法。實驗內(nèi)容1、 實現(xiàn)以下說明的操作函數(shù)，添加到實驗十所寫的頭文件binary_tree.h中，并建立主函數(shù)文件test4_2?cpp,編寫測試語句加以驗證。操作函數(shù)如下：VoidInOrder2(BTreeNode*BT);//非遞歸中序遍歷二叉樹BTVoidChangeBTree(BTreeNode*&BT);//將二叉樹中的所有結(jié)點的左右子樹進(jìn)行交換：ntCountBTree(BTreeNode*BT);//統(tǒng)計二叉樹中的所有結(jié)點數(shù)并返回BTreeNode*CopyBTree(BTreeNode*BT);//復(fù)制一棵二叉樹,并返回復(fù)制得到的二叉樹根結(jié)點指針2、 選做：實現(xiàn)以下說明的操作函數(shù),添加到頭文件binary_tree.h中,并在主函數(shù)文件test4_2?cpp中添加相應(yīng)語句進(jìn)行測試。ntSimilarTrees(BTreeNode*BT1，BTreeNode*BT2)//判斷兩棵二叉樹是否相似。所謂相似是指如果兩棵二叉樹具有相同的樹型,則稱它們是相似的,否則不是。BTreeNode*RemoveLeaves(BTreeNode*BT1)//摘樹葉：摘除一棵二叉樹上的所有葉子結(jié)點后返回一棵新的二叉樹。3、 填寫實驗報告,實驗報告文件取名為report11.doc。4、 上傳實驗報告文件report11.doc、源程序文件test4_2?cpp及binary_tree?h到Ftp服務(wù)器上自己的文件夾下。函數(shù)的功能說明及算法思路(包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路)結(jié)構(gòu)定義：二叉樹：structBTreeNode{ElemTypedata;BTreeNode*lchild;BTreeNode*rchild;};順序棧：structStack{BTreeNode**stack;//存棧元素inttop;intMaxSize;};Operations:二叉樹：voidInitBTree(BTreeNode*&BT)//初始化二叉樹BTvoidCreateBTree(BTreeNode*&BT,char*a)//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲結(jié)構(gòu)voidPrintBTree(BTreeNode*BT)//輸出二叉樹BTvoidClearBTree(BTreeNode*&BT)//清除二叉樹BTvoidInOrder2(BTreeNode*BT)//非遞歸中序遍歷二叉樹BTvoidChangeBTree(BTreeNode*&BT)//將二叉樹中的所有結(jié)點的左右子樹進(jìn)行交換intCountBTree(BTreeNode*BT)//統(tǒng)計二叉樹中的所有結(jié)點數(shù)并返回BTreeNode*CopyBTree(BTreeNode*BT)//復(fù)制一棵二叉樹，并返回復(fù)制得到的二叉樹根結(jié)點指針intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2)//判斷兩棵二叉樹是否相似。所謂相似是指如果兩棵二叉樹具有相同的樹型，則稱它們是相似的，否則不是。BTreeNode*RemoveLeaves(BTreeNode*BT1)//摘樹葉：摘除一棵二叉樹上的所有葉子結(jié)點后返回一棵新的二叉樹。順序棧：voidInitstack(Stack&S)//初始化棧為空，把棧設(shè)置為空并完成?？臻g的動態(tài)存儲分配voidPush(Stack&S,BTreeNode*item)//元素item進(jìn)棧，即插入到棧頂BTreeNode*Pop(Stack&S)//刪除棧頂元素并返回boolEmptyStack(Stack&S)//判斷S是否為空，若為空則返回true，否則返回falsevoidClearStack(Stack&S)//清除棧S中的所有元素，釋放動態(tài)存儲空間endGeneralTree算法:voidInOrder2（BTreeNode*BT）//非遞歸中序遍歷二叉樹BT{定義堆棧s定義樹結(jié)點P初始化棧swhile（p不為空或者s不為空）{if（p不為空）將p進(jìn)棧；P的值重新賦為p的左孩子if（s不為空）將出棧的值賦給P;輸出p的根的值；P等于p的右邊孩子;}}voidChangeBTree（BTreeNode*&BT）{//將二叉樹中的所有結(jié)點的左右子樹進(jìn)行交換定義樹結(jié)點P//用作中間值防止樹被破壞if（BT不為空）{if（BT的左、右孩子都不為空）定義樹結(jié)點P，將p的左孩子賦值給PBT的左孩子等于BT的右孩子BT的右孩子等于p遞歸調(diào)用交換左子樹；遞歸調(diào)用交換右子樹；}}intCountBTree（BTreeNode*BT）〃統(tǒng)計二叉樹中的所有結(jié)點數(shù)并返回{if（樹為空）返回0；elseif（BT的左、右孩子等于空）返回1；elsereturn遞歸調(diào)用左孩子個數(shù)+遞歸調(diào)用右孩子個數(shù)+1；}BTreeNode*CopyBTree（BTreeNode*BT）{//復(fù)制一棵二叉樹，并返回復(fù)制得到的二叉樹根結(jié)點指針定義樹結(jié)點Pif（BT為空）返回空else{定義樹結(jié)點P,并給以內(nèi)存為將BT的根結(jié)點，左結(jié)點，右結(jié)點復(fù)制給p返回p；}intSimilarTrees（BTreeNode*BT1,BTreeNode*BT2）{//判斷兩棵二叉樹是否相似。所謂相似是指如果兩棵二叉樹具有相同的樹型則稱它們是相似的，否則不是。設(shè)置變量like1以及l(fā)ike2用于保留左子樹以及右子樹是否相似的值if（BT1和BT2為空）返回1；elseif（BTl和BT2中有一個為空）返回0；else返回遞歸調(diào)用左孩子相似函數(shù)&&遞歸調(diào)用右孩子相似函數(shù)}BTreeNode*RemoveLeaves（BTreeNode*BT1）{//摘樹葉：摘除一棵二叉樹上的所有葉子結(jié)點后返回一棵新的二叉樹if（BT1為空）返回空;elseif（BT1左孩子和右孩子為空值）刪除BT1,并且返回NULLelse{BTl->lchild=遞歸調(diào)用BT1的左孩子；BTl->rchild二遞歸調(diào)用BT1的右孩子；}返回BT1；}實驗結(jié)果與分析（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）

五.心得體會（記錄實驗感受、上機(jī)過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）做二叉樹相似的時候，條件（BT1和BT2為空）和（BT1和BT2中有一個為空）沒有分出來，認(rèn)為||就將兩個條件概括了。之后才找出來錯誤【附錄 源程序】test4_2.cpp：#include<iostream.h>#include<stdio.h>#include<stdlib.h>typedefcharElemType;#include"binary_tree.h"voidmain(){BTreeNode*BT1,*BT2,*BT3;chara[50];InitBTree(BT1);InitBTree(BT2);coutvv”請輸入二叉樹BT1的廣義表：”vvendl;gets(a);CreateBTree(BT1,a);coutvv”請輸入二叉樹BT2的廣義表：”vvendl;gets(a);CreateBTree(BT2,a);coutvv"中序序列(非遞歸):"；InOrder2(BT1);coutvvendlvvendl;coutvv"交換二叉樹BT1中的所有結(jié)點的左右子樹:"vvendl;ChangeBTree(BT1);PrintBTree(BT1);coutvvendlvvendl;coutvv"二叉樹BT1共有"vvCountBTree(BT1)vv”個結(jié)點”vvendlvvendl;InitBTree(BT3);coutvv"復(fù)制二叉樹BT1:"vvendl;coutvv"原二叉樹BT1:";PrintBTree(BT1);coutvvendl;coutvv"復(fù)制后的二叉樹BT3:";BT3=CopyBTree(BT1);PrintBTree(BT3);coutvvendlvvendl;if(SimilarTrees(BT1,BT2))coutvv"二叉樹BT1與二叉樹BT2相似"vvendlvvendl;elsecoutvv"二叉樹BT1與二叉樹BT2不相似"vvendlvvendl;coutvv"摘樹葉：摘除二叉樹BT1的所有葉子結(jié)點:"；RemoveLeaves(BT1);coutvv"輸出摘除葉子結(jié)點的二叉樹BT1:"vvendl;PrintBTree(BT1);coutvvendl;ClearBTree(BT1);ClearBTree(BT2);ClearBTree(BT3);}binary_tree.h：// 棧操作 structBTreeNode{ElemTypedata;BTreeNode*lchild;BTreeNode*rchild;};structStack{BTreeNode**stack;//存棧元素inttop;intMaxSize;};voidInitStack(Stack&S)〃初始化棧為空，把棧設(shè)置為空并完成?？臻g的動態(tài)存儲分配{S.MaxSize=10;〃?？臻g大小為10S.stack=newBTreeNode*[S.MaxSize];if(!S.stack){cerrvv”動態(tài)存儲分配失敗！”vvendl;exit(1);}S.top=-1;}voidPush(Stack&S,BTreeNode*item)〃元素item進(jìn)棧，即插入到棧頂{if(S.top==S.MaxSize-1){intk=sizeof(BTreeNode);S.stack=(BTreeNode**)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}S.top++;〃棧頂指針加1表示后移一個位置S.stack[S.top]=item;}BTreeNode*Pop(Stack&S)//刪除棧頂元素并返回{if(S.top==-1){cerrvv”?？?！”vvendl;exit(1);}S.top--;//棧頂指針減1表示退棧returnS.stack[S.top+1];}boolEmptyStack(Stack&S)〃判斷S是否為空，若為空則返回true，否則返回false{returnS.top==-1;voidClearStack(Stack&S)//青除棧S中的所有元素，釋放動態(tài)存儲空間{if(S.stack){delete[]S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}// 二叉樹基本操作 voidInitBTree(BTreeNode*&BT){//初始化二叉樹BTBT=NULL;}voidCreateBTree(BTreeNode*&BT,char*a){//根據(jù)字符串a(chǎn)所給出的廣義表表示的二叉樹建立二叉鏈表存儲結(jié)構(gòu)constintMaxSize=10; //棧數(shù)組長度＞=二叉樹的深度減1BTreeNode*s[MaxSize]; //s數(shù)組作為存儲根結(jié)點指針的棧使用inttop=-1; //top為棧頂指針，表示?？誃TreeNode*p; //二叉樹結(jié)點指針intk,i=0; //k=1時處理左子樹，k=2處理右子樹while(a[i]){switch(a[i]){case'':break;case'(':if(top==MaxSize-1){coutvv”?？臻g太小，請增加MaxSize的值！”vvendl;exit(1);}top++;s[top]=p;k=1;break;case')':if(top==-1){coutvv"二叉樹廣義表字符串錯！"vvendl;exit(1);}top--;break;case',':k=2;break;default:p=newBTreeNode;p->data=a[i];p->lchild=p->rchild=NULL;if(BT==NULL)BT=p;else{if(k==1)s[top]->lchild=p;elses[top]->rchild=p;}}i++;}}voidPrintBTree(BTreeNode*BT){//輸出二叉樹BTif(BT!=NULL){cout<<BT->data; //輸出根結(jié)點if(BT->lchild!=NULL||BT->rchild!=NULL){/若非葉子結(jié)點，則遞歸調(diào)用輸出左右子樹cout<<'(';PrintBTree(BT->lchild);if(BT->rchild!=NULL){cout<<',';PrintBTree(BT->rchild);}cout<<')';}}}voidClearBTree(BTreeNode*&BT){//清除二叉樹BTif(BT!=NULL){ClearBTree(BT->lchild);ClearBTree(BT->rchild);free(BT);BT=NULL;}}// 二叉樹操作 voidInOrder2(BTreeNode*BT)//非遞歸中序遍歷二叉樹BT{Stacks;BTreeNode*p=BT;InitStack(s);while(p!=NULL||!EmptyStack(s)){while(p!=NULL){Push(s,p);p=p->lchild;}if(!EmptyStack(s)){p=Pop(s);cout<<p->data<<'';p=p->rchild;}}ClearStack(s);}voidChangeBTree(BTreeNode*&BT)〃將二叉樹中的所有結(jié)點的左右子樹進(jìn)行交換{if(BT!=NULL){if(BT->lchild!=NULL&&BT->rchild!=NULL){BTreeNode*p=BT->lchild;BT->lchild=BT->rchild;BT->rchild=p;}ChangeBTree(BT->lchild);ChangeBTree(BT->rchild);}}intCountBTree(BTreeNode*BT)〃統(tǒng)計二叉樹中的所有結(jié)點數(shù)并返回{if(BT==NULL)return0;elseif(BT->lchild==NULL&&BT->rchild==NULL)return1;elsereturnCountBTree(BT->lchild)+CountBTree(BT->rchild)+1;}BTreeNode*CopyBTree(BTreeNode*BT)/復(fù)制一棵二叉樹，并返