二叉樹的遍歷實驗報告

實驗報告題目：編寫一個二叉樹遍歷演示程序。班級：軟件（2）姓名：===學(xué)號：0925115025完成日期：2011.5.11需求分析1.（1）給出一棵二叉樹的中序與后序遍歷序列，求出它的先序遍歷序列。（2）給出一棵二叉樹的中序與先序遍歷序列，求出它的后序遍歷序列。測試數(shù)據(jù)如下：已知二叉樹的中序與后序序列，求先序序列，請先輸入中序序列，回車后輸入后序序列：例如輸入：DGBAECHFGDBEHFCA輸出：先序遍歷結(jié)果：ABDGCEFH中序遍歷結(jié)果：DGBAECHF后序遍歷結(jié)果：GDBEHFCA已知二叉樹的先序與中序序列，求后序序列，請先輸入先序序列，回車后輸入中序序列：例如輸入：abdefgcdebgfac輸出：先序遍歷結(jié)果：abdefgc中序遍歷結(jié)果：debgfac后序遍歷結(jié)果：edgfbca詳細設(shè)計構(gòu)造二叉樹結(jié)點voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp){//構(gòu)造二叉樹結(jié)點lpNode=newBINARY_TREE_NODE;lpNode->data=post[rp];lpNode->pLeftChild=NULL;lpNode->pRightChild=NULL;intpos=lm;while(mid[pos]!=post[rp]){pos++;}intiLeftChildLen=pos-lm;if(pos>lm)//有左孩子，遞歸構(gòu)造左子樹{TreeFromMidPost(lpNode->pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);}if(pos<rm)//有右孩子，遞歸構(gòu)造右子樹{TreeFromMidPost(lpNode->pRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);}}二叉樹的操作//先序遍歷voidPreOrder(LPBINARY_TREE_NODEp){if(p!=NULL){cout<<p->data;//輸出該結(jié)點PreOrder(p->pLeftChild);//遍歷左子樹PreOrder(p->pRightChild);//遍歷右子樹}}//中序遍歷voidMidOrder(LPBINARY_TREE_NODEp){if(p!=NULL){MidOrder(p->pLeftChild);//遍歷左子樹cout<<p->data;//輸出該結(jié)點MidOrder(p->pRightChild);//遍歷右子樹}}//后序遍歷voidPostOrder(LPBINARY_TREE_NODEp){if(p!=NULL){PostOrder(p->pLeftChild);//遍歷左子樹PostOrder(p->pRightChild);//遍歷右子樹cout<<p->data;//輸出該結(jié)點}}//釋放二叉樹voidRelease(LPBINARY_TREE_NODElpNode){if(lpNode!=NULL){Release(lpNode->pLeftChild);Release(lpNode->pRightChild);deletelpNode;lpNode=NULL;}}完整的程序代碼#include<iostream>#include<string>usingnamespacestd;typedefcharDATA_TYPE;typedefstructtagBINARY_TREE_NODEBINARY_TREE_NODE,*LPBINARY_TREE_NODE;structtagBINARY_TREE_NODE{DATA_TYPEdata;//節(jié)點數(shù)據(jù)LPBINARY_TREE_NODEpLeftChild;//左孩子指針LPBINARY_TREE_NODEpRightChild;//右孩子指針};//函數(shù)功能：給出一棵二叉樹的中序與后序序列，構(gòu)造這棵二叉樹。//輸入?yún)?shù)：LPBINARY_TREE_NODE&lpNode：二叉樹的結(jié)點//stringmid：存儲了二叉樹的中序序列的字符串//stringpost：存儲了二叉樹的后序序列的字符串//intlm,intrm：二叉樹的中序序列在數(shù)組mid中的左右邊界//intlp,intrp：二叉樹的后序序列在數(shù)組post中的左右邊界//voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp){//構(gòu)造二叉樹結(jié)點lpNode=newBINARY_TREE_NODE;lpNode->data=post[rp];lpNode->pLeftChild=NULL;lpNode->pRightChild=NULL;intpos=lm;while(mid[pos]!=post[rp]){pos++;}intiLeftChildLen=pos-lm;if(pos>lm)//有左孩子，遞歸構(gòu)造左子樹{TreeFromMidPost(lpNode->pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);}if(pos<rm)//有右孩子，遞歸構(gòu)造右子樹{TreeFromMidPost(lpNode->pRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);}}//函數(shù)功能：給出一棵二叉樹的先序與中序序列，構(gòu)造這棵二叉樹。//輸入?yún)?shù):BINARY_TREE_NODE&lpNode：二叉樹的結(jié)點//stringmid：存儲了二叉樹的中序序列的字符串//stringpre：存儲了二叉樹的先序序列的字符串//intlm,intrm：二叉樹的中序序列在數(shù)組mid中的左右邊界//intlp,intrp：二叉樹的先序序列在數(shù)組pre中的左右邊界//voidTreeFromMidPre(LPBINARY_TREE_NODE&lpNode,stringmid,stringpre,intlm,intrm,intlp,intrp){//構(gòu)造二叉樹結(jié)點lpNode=newBINARY_TREE_NODE;lpNode->data=pre[lp];lpNode->pLeftChild=NULL;lpNode->pRightChild=NULL;intpos=lm;while(mid[pos]!=pre[lp]){pos++;}intiLeftChildLen=pos-lm;if(pos>lm)//有左孩子，遞歸構(gòu)造左子樹{TreeFromMidPre(lpNode->pLeftChild,mid,pre,lm,pos-1,lp+1,lp+iLeftChildLen);}if(pos<rm)//有右孩子，遞歸構(gòu)造右子樹{TreeFromMidPre(lpNode->pRightChild,mid,pre,pos+1,rm,lp+iLeftChildLen+1,rp);}}//先序遍歷voidPreOrder(LPBINARY_TREE_NODEp){if(p!=NULL){cout<<p->data;//輸出該結(jié)點PreOrder(p->pLeftChild);//遍歷左子樹PreOrder(p->pRightChild);//遍歷右子樹}}//中序遍歷voidMidOrder(LPBINARY_TREE_NODEp){if(p!=NULL){MidOrder(p->pLeftChild);//遍歷左子樹cout<<p->data;//輸出該結(jié)點MidOrder(p->pRightChild);//遍歷右子樹}}//后序遍歷voidPostOrder(LPBINARY_TREE_NODEp){if(p!=NULL){PostOrder(p->pLeftChild);//遍歷左子樹PostOrder(p->pRightChild);//遍歷右子樹cout<<p->data;//輸出該結(jié)點}}//釋放二叉樹voidRelease(LPBINARY_TREE_NODElpNode){if(lpNode!=NULL){Release(lpNode->pLeftChild);Release(lpNode->pRightChild);deletelpNode;lpNode=NULL;}}intmain(intargc,char*argv[]){stringpre;//存儲先序序列stringmid;//存儲中序序列stringpost;//存儲后序序列LPBINARY_TREE_NODElpRoot;//二叉樹根節(jié)點指針cout<<"程序１已知二叉樹的中序與后序序列，求先序序列"<<endl;cout<<"請先輸入中序序列，回車后輸入后序序列："<<endl;cin>>mid;cin>>post;TreeFromMidPost(lpRoot,mid,post,0,mid.size()-1,0,post.size()-1);cout<<"先序遍歷結(jié)果：";PreOrder(lpRoot);cout<<endl;cout<<"中序遍歷結(jié)果：";MidOrder(lp