實驗十叉樹的進步操作

浙江大學城市學院實驗報告課程名稱數(shù)據(jù)結構基礎實驗項目名稱實驗^一二義樹的進一步操作學生姓名專業(yè)班級學號實驗成績指導老師(簽名)日期2014-12-25一.實驗目的和要求1、熟練掌握二義樹二義鏈表的存儲結構。2、進一步掌握在二義鏈表上的二義樹操作的實現(xiàn)原理與方法3、掌握中序遍歷的非遞歸算法。二.實驗內容1、實現(xiàn)以下說明的操作函數(shù)，添加到實驗十所寫的頭文件binary_tree.h中,并建立主函數(shù)文件test4_2.cpp,編寫測試語句加以驗證。操作函數(shù)如下：voidInOrder2(BTreeNode*BT);〃非遞歸中序遍歷二義樹BTvoidChangeBTree(BTreeNode*&BT);〃將二義樹中的所有結點的左右子樹進行交換：IntCountBTree(BTreeNode*BT);〃統(tǒng)計二義樹中的所有結點數(shù)并返回BTreeNode*CopyBTree(BTreeNode*BT);〃復制一棵二義樹，并返回復制得到的二義樹根結點指針2、選做：實現(xiàn)以下說明的操作函數(shù)，添加到頭文件binary_tree.h中，并在主函數(shù)文件test4_2.cpp中添加相應語句進行測試。intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2)〃判斷兩棵二義樹是否相似。所謂相似是指如果兩棵二義樹具有相同的樹型，則稱它們是相似的，否則不是。BTreeNode*RemoveLeaves(BTreeNode*BT1)〃摘樹葉：摘除一棵二義樹上的所有葉子結點后返回一棵新的二義樹。3、填寫實驗報告，實驗報告文件取名為report11.doc。4、上傳實驗報告文件report11.doc、源程序文件test4_2.cpp及binary_tree.h到Ftp服務器上自己的文件夾下。--.函數(shù)的功能說明及算法思路(包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路)結構定義：二義樹：structBTreeNode(ElemTypedata;BTreeNode*lchild;BTreeNode*rchild;}；順序棧：structStack(BTreeNode**stack;//存棧元素inttop;intMaxSize;};Operations:二義樹：voidInitBTree(BTreeNode*&BT)//初始化二義樹BTvoidCreateBTree(BTreeNode*&BT,char*a)//根據(jù)字符申a所給出的廣義表表示的二義樹建立二義鏈表存儲結構voidPrintBTree(BTreeNode*BT)//輸出二義樹BTvoidClearBTree(BTreeNode*&BT)//活除二義樹BTvoidInOrder2(BTreeNode*BT)//非遞歸中序遍歷二義樹BTvoidChangeBTree(BTreeNode*&BT)//將二義樹中的所有結點的左右子樹進行交換intCountBTree(BTreeNode*BT)//統(tǒng)計二義樹中的所有結點數(shù)并返回BTreeNode*CopyBTree(BTreeNode*BT)//復制一棵二義樹，并返回復制得到的二義樹根結點指針intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2)//判斷兩棵二義樹是否相似。所謂相似是指如果兩棵二義樹具有相同的樹型，則稱它們是相似的，否則不是。BTreeNode*RemoveLeaves(BTreeNode*BT1)//摘樹葉：摘除一棵二義樹上的所有葉子結點后返回一棵新的二義樹。順序棧：voidInitStack(Stack&S)//初始化棧為空，把棧設置為空并完成?？臻g的動態(tài)存儲分配voidPush(Stack&S,BTreeNode*item)//元素item進棧，即插入到棧頂BTreeNode*Pop(Stack&S)//刪除棧頂元素并返回boolEmptyStack(Stack&S)//判斷毗否為空，若為空則返回true,否則返回falsevoidClearStack(Stack&S)//清除棧S中的所有元素，釋放動態(tài)存儲空間endGeneralTree算法：voidInOrder2（BTreeNode*BT）//非遞歸中序遍歷二義樹BT（定義堆棧s定義樹結點P初始化棧swhile（p不為空或者s不為空）（if（p不為空）將p進棧；P的值重新賦為p的左孩子if（s不為空）將出棧的值賦給p;輸出p的根的值；P等于p的右邊孩子;}}voidChangeBTree（BTreeNode*&BT）（//將二義樹中的所有結點的左右子樹進行交換定義樹結點P//用作中間值防止樹被破壞if（BT不為空）{if（BT的左、右孩子都不為空）定義樹結點P，將p的左孩子賦值給PBT的左孩子等于BT的右孩子BT的右孩子等于p遞歸調用交換左子樹；遞歸調用交換右子樹；}}intCountBTree（BTreeNode*BT）//統(tǒng)計二義樹中的所有結點數(shù)并返回{if（樹為空）返回0;elseif（BT的左、右孩子等于空）返回1;elsereturn遞歸調用左孩子個數(shù)+遞歸調用右孩子個數(shù)+1;}BTreeNode*CopyBTree（BTreeNode*BT）{//復制一棵二義樹，并返回復制得到的二義樹根結點指針定義樹結點Pif（BT為空）返回空else{定義樹結點P,并給以內存為將BT的根結點，左結點，右結點復制給p返回p；}}intSimilarTrees（BTreeNode*BT1,BTreeNode*BT2）（//判斷兩棵二義樹是否相似。所謂相似是指如果兩棵二義樹具有相同的樹型,則稱它們是相似的，否則不是。設置變量likel以及l(fā)ike2用丁保留左子樹以及右子樹是否相似的值if（BT1和BT2為空）返回1;elseif（BT1和BT2中有一個為空）返回0;else返回遞歸調用左孩子相似函數(shù)&&!歸調用右孩子相似函數(shù)}BTreeNode*RemoveLeaves（BTreeNode*BT1）（//摘樹葉：摘除一棵二義樹上的所有葉子結點后返回一棵新的二義樹if（BT1為空）返回空；elseif（BT1左孩子和右孩子為空值）刪除BT1，并且返回NULLelse（BT1->lchild=遞歸調用BT1的左孩子；BT1->rchild=遞歸調用BT1的右孩子；}返回BT1;}四.實驗結果與分析（包括運行結果截圖、結果分析等）。我*E:\report1l\Debug\report11.exe*司輸入二叉樹BT1的廣義表:~a<b,c<d,e>>請輸入二叉樹BT2的廣義表：中序序列《非遞歸〉:hadce交換二叉樹BT1中的所有結點的左右子樹:a<c<e,d>,b>二叉樹BT1共有S個結點復制二叉樹BT"原二叉割里:LWc","!））復制后的二叉樹BT3：a<c<e,d>,b>二叉樹BT1與二叉樹BT2相似箱樹葉:摘除二叉樹BT1的所有葉子結點:輸出摘除葉子結點的二叉樹BT1:a<c>Pressanykeytocontinue.g我*E:\report1l\Debug\report11.exe*隋輸入二叉樹BTl的廣義表:~^<b<d,eCf>>,c<,g>>情輸入二叉樹BT2的廣義表：j>中序序列《非逢歸〉=dbfeacg交換二叉樹BT1中的所有結點的左右子樹:^<cC,g>,b<e<f>,d>>二叉樹BT1共有?個結點復制二叉樹BT"^SJ^pBTl：a<c<,g>,b<e<f>,d>>復制后的二叉樹BT3：a<c<,g>,b<e<f>,d>>二叉樹BT1與二叉樹BT2不相似后樹葉:摘除二叉樹BT1的所有葉子結點:輸出摘除葉子結點的二叉樹ET1:a<c,b<e>>Pressanykeytocontinue五.心得體會（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）做二義樹相似的時候，條件（BT1和BT2為空）和（BT1和BT2中有一個為空）沒有分出來，認為||就將兩個條件概括了。之后才找出來錯誤【附錄----源程序】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);cout<<"請輸入二義樹BT1的廣義表："<<endl;gets(a);CreateBTree(BT1,a);cout<<"請輸入二義樹BT2的廣義表："<<endl;gets(a);CreateBTree(BT2,a);cout<<"中序序列(非遞歸):"；InOrder2(BT1);cout<<endl<<endl;cout<<"交換二義樹BT1中的所有結點的左右子樹:"<<endl;ChangeBTree(BT1);PrintBTree(BT1);cout<<endl<<endl;cout<<"二義樹BT1共有"<<CountBTree(BT1)<<"個結點"<<endl<<endl;InitBTree(BT3);cout<<"復制二義樹BT1:"<<endl;cout<<"原二義樹BT1:";PrintBTree(BT1);cout<<endl;cout<<"復制后的二義樹BT3:";BT3=CopyBTree(BT1);PrintBTree(BT3);cout<<endl<<endl;if(SimilarTrees(BT1,BT2))cout<<"二義樹BT1與二義樹BT2相似"<<endl<<endl;elsecout<<"二義樹BT1與二義樹BT2不相似"<<endl<<endl;cout<<"摘樹葉：摘除二義樹BT1的所有葉子結點:";RemoveLeaves(BT1);cout<<"輸出摘除葉子結點的二義樹BT1:"<<endl;PrintBTree(BT1);cout<<endl;ClearBTree(BT1);ClearBTree(BT2);ClearBTree(BT3);}binary_tree.h//棧操作structBTreeNode{ElemTypedata;BTreeNode*lchild;BTreeNode*rchild;}；structStack(BTreeNode**stack;〃存棧元素inttop;intMaxSize;};voidInitStack(Stack&S)//初始化棧為空，把棧設置為空并完成?？臻g的動態(tài)存儲分配(S.MaxSize=10;//?？臻g大小為10S.stack=newBTreeNode*[S.MaxSize];if(!S.stack){cerr<<"動態(tài)存儲分配失??！"<<endl;exit(1);}S.top=-1;}voidPush(Stack&S,BTreeNode*item)//元素item進棧，即插入到棧頂{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){cerr<<"?？?！"<<endl;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所給出的廣義表表示的二義樹建立二義鏈表存儲結構constintMaxSize=10;〃棧數(shù)組長度〉=二義樹的深度減1BTreeNode*s[MaxSize];//s數(shù)組作為存儲根結點指針的棧使用inttop=-1;//top為棧頂指針，表示?？誃TreeNode*p;〃二義樹結點指針intk,i=0;//k=1時處理左子樹，k=2處理右子樹while(a[i]){switch(a[i]){case'':break;case'(':if(top==MaxSize-1){cout<<"棧空間太小，請增加MaxSize的值！"<<endl;exit(1);}top++;s[top]=p;k=1;break;case')':if(top==-1){cout<<”二義樹廣義表字符申錯！"<<endl;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;〃輸出根結點if(BT->lchild!=NULL||BT->rchild!=NULL){//若非葉子結點,則遞歸調用輸出左右子樹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)//將二義樹中的所有結點的左右子樹進行交換{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)計二義樹中的所有結點數(shù)并返回{if(BT==NULL)return0;elseif(BT->lchild==NULL&&BT->rchild==NULL)return1;elsereturnCountBTree(BT->lchild)+CountBTree(BT->rchild)+