数据结构实验之求二叉树后序遍历和层次遍历
Time Limit: 1000MS Memory limit: 65536K
题目描述
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历。输入
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。输出
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列示例输入
2abdegcfdbgeafcxnliulnixu
示例输出
dgebfcaabcdefglinuxxnuli
第一种方法：根据字符串的递推， 由先序、中序直接计算后序串！ 在建树，进行层次遍历！
代码：
#include <iostream>#include <iomanip>#include <string>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#include <vector>using namespace std;typedef struct node{char a;struct node *ll;struct node *rr;}Binode, *tree;void build(int len, char *s1, char *s2, char *s) //先序中序 推 后序{if(len<=0)return;int pos; //位置int i;for(i=0; i<len; i++){if(s2[i]==s1[0]){pos=i;break;}}build(pos, s1+1, s2, s );build(len-pos-1, s1+pos+1, s2+pos+1, s+pos );s[len-1]=s1[0];}//根据先序中序建树struct node*creat(struct node *root, char *s, char *s1, int n){if(n<=0)return NULL;root=new node;root->a=s[0];int p=strchr(s1, s[0] )-s1;root->ll=creat( root->ll, s+1, s1, p );root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 );return root;}//层次遍历 二叉树void Level_Order(tree root){queue<tree>q;tree qq;if(root==NULL)return ;Binode *p=root;cout<<(p->a);if(p->ll)q.push( p->ll );if(p->rr)q.push( p->rr );while(!q.empty()){qq=q.front();q.pop();cout<<qq->a;if(qq->ll)q.push(qq->ll);if(qq->rr)q.push(qq->rr);}return;}int main(){int t;cin>>t;char s1[100], s2[100];char s3[100];while(t--){memset(s3, '\0', sizeof(s3));scanf("%s", s1); //中序scanf("%s", s2); //后序int len=strlen(s1);build(len, s1, s2, s3);printf("%s\n", s3); //输出后序遍历//计算层次遍历tree root, tt;root=creat(tt, s1, s2, len);Level_Order( root);cout<<endl;}return 0;}
第二种方法：先根据先序、中序建树，在进行后序遍历和层次遍历
代码：
#include <iostream>#include <iomanip>#include <string>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#include <vector>using namespace std;typedef struct node{char a;struct node *ll;struct node *rr;}Binode, *tree;//根据先序中序建树struct node*creat(struct node *root, char *s, char *s1, int n){if(n<=0)return NULL;root=new node;root->a=s[0];int p=strchr(s1, s[0] )-s1;root->ll=creat( root->ll, s+1, s1, p );root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 );return root;}void postorder(tree p){if(p){postorder(p->ll);postorder(p->rr);printf("%c", p->a );}}//层次遍历 二叉树void Level_Order(tree root){queue<tree>q;tree qq;if(root==NULL)return ;Binode *p=root;cout<<(p->a);if(p->ll)q.push( p->ll );if(p->rr)q.push( p->rr );while(!q.empty()){qq=q.front();q.pop();cout<<qq->a;if(qq->ll)q.push(qq->ll);if(qq->rr)q.push(qq->rr);}return;}int main(){int t;cin>>t;char s1[100], s2[100];char s3[100];while(t--){memset(s3, '\0', sizeof(s3));scanf("%s", s1); //中序scanf("%s", s2); //后序int len=strlen(s1);//计算层次遍历tree root, tt;root=creat(tt, s1, s2, len);postorder(root);cout<<endl;Level_Order( root);cout<<endl;}return 0;}
