二叉树的遍历实验报告

实验报告题目：编写一个二叉树遍历演示程序。班级：软件（2）姓名：===学号：0925115025完成日期：2011.5.11需求分析1.（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。测试数据如下：已知二叉树的中序与后序序列，求先序序列，请先输入中序序列，回车后输入后序序列：例如输入：DGBAECHFGDBEHFCA输出：先序遍历结果：ABDGCEFH中序遍历结果：DGBAECHF后序遍历结果：GDBEHFCA已知二叉树的先序与中序序列，求后序序列，请先输入先序序列，回车后输入中序序列：例如输入：abdefgcdebgfac输出：先序遍历结果：abdefgc中序遍历结果：debgfac后序遍历结果：edgfbca详细设计构造二叉树结点voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp){//构造二叉树结点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)//有左孩子，递归构造左子树{TreeFromMidPost(lpNode->pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);}if(pos<rm)//有右孩子，递归构造右子树{TreeFromMidPost(lpNode->pRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);}}二叉树的操作//先序遍历voidPreOrder(LPBINARY_TREE_NODEp){if(p!=NULL){cout<<p->data;//输出该结点PreOrder(p->pLeftChild);//遍历左子树PreOrder(p->pRightChild);//遍历右子树}}//中序遍历voidMidOrder(LPBINARY_TREE_NODEp){if(p!=NULL){MidOrder(p->pLeftChild);//遍历左子树cout<<p->data;//输出该结点MidOrder(p->pRightChild);//遍历右子树}}//后序遍历voidPostOrder(LPBINARY_TREE_NODEp){if(p!=NULL){PostOrder(p->pLeftChild);//遍历左子树PostOrder(p->pRightChild);//遍历右子树cout<<p->data;//输出该结点}}//释放二叉树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;//节点数据LPBINARY_TREE_NODEpLeftChild;//左孩子指针LPBINARY_TREE_NODEpRightChild;//右孩子指针};//函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。//输入参数：LPBINARY_TREE_NODE&lpNode：二叉树的结点//stringmid：存储了二叉树的中序序列的字符串//stringpost：存储了二叉树的后序序列的字符串//intlm,intrm：二叉树的中序序列在数组mid中的左右边界//intlp,intrp：二叉树的后序序列在数组post中的左右边界//voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp){//构造二叉树结点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)//有左孩子，递归构造左子树{TreeFromMidPost(lpNode->pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);}if(pos<rm)//有右孩子，递归构造右子树{TreeFromMidPost(lpNode->pRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);}}//函数功能：给出一棵二叉树的先序与中序序列，构造这棵二叉树。//输入参数:BINARY_TREE_NODE&lpNode：二叉树的结点//stringmid：存储了二叉树的中序序列的字符串//stringpre：存储了二叉树的先序序列的字符串//intlm,intrm：二叉树的中序序列在数组mid中的左右边界//intlp,intrp：二叉树的先序序列在数组pre中的左右边界//voidTreeFromMidPre(LPBINARY_TREE_NODE&lpNode,stringmid,stringpre,intlm,intrm,intlp,intrp){//构造二叉树结点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)//有左孩子，递归构造左子树{TreeFromMidPre(lpNode->pLeftChild,mid,pre,lm,pos-1,lp+1,lp+iLeftChildLen);}if(pos<rm)//有右孩子，递归构造右子树{TreeFromMidPre(lpNode->pRightChild,mid,pre,pos+1,rm,lp+iLeftChildLen+1,rp);}}//先序遍历voidPreOrder(LPBINARY_TREE_NODEp){if(p!=NULL){cout<<p->data;//输出该结点PreOrder(p->pLeftChild);//遍历左子树PreOrder(p->pRightChild);//遍历右子树}}//中序遍历voidMidOrder(LPBINARY_TREE_NODEp){if(p!=NULL){MidOrder(p->pLeftChild);//遍历左子树cout<<p->data;//输出该结点MidOrder(p->pRightChild);//遍历右子树}}//后序遍历voidPostOrder(LPBINARY_TREE_NODEp){if(p!=NULL){PostOrder(p->pLeftChild);//遍历左子树PostOrder(p->pRightChild);//遍历右子树cout<<p->data;//输出该结点}}//释放二叉树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;//二叉树根节点指针cout<<"程序１已知二叉树的中序与后序序列，求先序序列"<<endl;cout<<"请先输入中序序列，回车后输入后序序列："<<endl;cin>>mid;cin>>post;TreeFromMidPost(lpRoot,mid,post,0,mid.size()-1,0,post.size()-1);cout<<"先序遍历结果：";PreOrder(lpRoot);cout<<endl;cout<<"中序遍历结果：";MidOrder(lp