数据结构实验之求二叉树后序遍历和层次遍历
Time Limit:1000MSMemory Limit:65536KB SubmitStatisticDiscussProblem Description
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历和层序遍历。
Input
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。
Output
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。
Example Input
2abdegcfdbgeafcxnliulnixu
Example Output
dgebfcaabcdefglinuxxnuli
Hint
Author
#include <iostream>#include <string.h>#include <queue>#include <stack>#include <malloc.h>using namespace std;char pre[51],in[51];typedef struct btree{char date;btree *lchild,*rchild;}btree;btree *root;btree *createbtree(char pre[],char in[],int n){btree *b;for(int i=0;i<n;++i){if(in[i]==pre[0]){b=(btree*)malloc(sizeof(btree));b->date=pre[0];b->lchild=createbtree(pre+1,in,i);b->rchild=createbtree(pre+i+1,in+i+1,n-i-1);return b;}}return NULL;}void postbtree()//非递归{stack<btree *>Stack;btree *p=root;do{while(p!=NULL){Stack.push(p);p=p->lchild;}bool flag=true;btree *r=NULL;while(!Stack.empty()&&flag){p=Stack.top();if(p->rchild==r){Stack.pop();cout<<p->date;r=p;}else{flag=false;p=p->rchild;}}}while(!Stack.empty());cout<<endl;}void levelorder(){btree *b=root;queue<btree*>Queue;Queue.push(b);while(!Queue.empty()){b=Queue.front();Queue.pop();//这个没有返回值cout<<b->date;if(b->lchild!=NULL)Queue.push(b->lchild);if(b->rchild!=NULL)Queue.push(b->rchild);}cout<<endl;}int main(){int n;cin>>n;while(n--){cin>>pre>>in;root=(btree *)malloc(sizeof(btree));root=createbtree(pre,in,strlen(pre));postbtree();levelorder();}return 0;}
后序的遍历时对应的递归代码（main函数和postorder函数：
void postbtree(btree *root)//递归{btree *b=root;if(b!=NULL){postbtree(b->lchild);postbtree(b->rchild);cout<<b->date;}}int main(){int n;cin>>n;while(n--){cin>>pre>>in;root=(btree *)malloc(sizeof(btree));root=createbtree(pre,in,strlen(pre));postbtree(root);cout<<endl;levelorder();}return 0;}
