测试数据：
7 4 1 3 2 6 5 7 1 2 3 4 5 6 7 2 3 1 5 7 6 4 4 1 6 3 5 7 2
代码：
#include<cstdio> #include<stdlib.h> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> #include<stack> #include<string> using namespace std; const int maxn=31; int n; int pre[maxn]; int post[maxn]; int inorder[maxn]; int layer[maxn]; struct node{ int index; int data; }; bool cmp1(node a,node b){ return a.index<b.index; } //序列里的数字不能重复 //后序和中序转先序 ToPre(n-1,0,n-1) void ToPre(int root,int start,int end){ if(start>end)return; int k; for(k=start;k<=end;k++){ if(post[root]==inorder[k])break; } printf("%d ",post[root]); int rightNum=end-k; ToPre(root-1-rightNum,start,k-1);//左子树的根节点以及左子树的中序序列 ToPre(root-1,k+1,end); } //后序中序转层序 ? vector<node> ans;//存放层序的序列 void ToLayer(int root,int start,int end,int index){ if(start>end)return; int k; for(k=start;k<=end;k++){ if(post[root]==inorder[k])break; } ans.push_back({index,post[root]});//后序根据index排列 :和结构体属性定义顺序得一致 int rightNum=end-k; //只要保证右节点的index永远比左节点的index大后序即可排序得到正确序列 ToLayer(root-1-rightNum,start,k-1,2*index+1);//左子树的根节点以及左子树的中序序列 ToLayer(root-1,k+1,end,2*index+2); } //中序先序转后序 preToPost(0,0,n-1) void preToPost(int root,int start,int end){ if(start>end)return; int data=pre[root];//根节点 int k; for(k=start;k<=end;k++){ if(inorder[k]==data)break; } //k是根节点在中序序列的位置 int leftNum=k-start; preToPost(root+1,start,k-1); preToPost(root+1+leftNum,k+1,end); printf("%d ",data); } //中序先序转层序:其实是一样的：省略了 // int main() { printf("请输入序列大小:"); scanf("%d",&n); printf("请输入先序序列：\n"); //先序 for(int i=0;i<n;i++){ cin>>pre[i]; } printf("请输入中序序列：\n"); //中序 for(int i=0;i<n;i++){ cin>>inorder[i]; } printf("请输入后序序列：\n"); //后序 for(int i=0;i<n;i++){ cin>>post[i]; } printf("请输入层次序列：\n"); //层次 for(int i=0;i<n;i++){ cin>>layer[i]; } printf("-------------\n"); printf("后序和中序转先序\n"); ToPre(n-1,0,n-1); printf("\n"); printf("后序和中序转层序\n"); ToLayer(n-1,0,n-1,0); sort(ans.begin(),ans.end(),cmp1);//容器的排序法只能用begin和end for(int i=0;i<ans.size();i++){ printf("%d ",ans[i].data); } printf("\n"); printf("先和中序转后序\n"); preToPost(0,0,n-1); return 0; }
