```cpp #include <stdio.h> #include <stdlib.h> int pre_p=1,pre[1001],in[1001],n,count_print;//pre_p用于遍历前序序列 //pre为前序序列数组,in为后序序列数组，n为二叉树中的元素个数，即序列长度，count_print用于规范输出格式 typedef struct Node { int data; struct Node *lchild; struct Node *rchild; } BTNode; int GetPosition() { int i; for(i=1; i<=n; ++i) { if(in[i]==pre[pre_p]) return i; } return 0; } void CreatBinaryTree(BTNode * &t,int low,int high) { if(high-low<0)//该方向已经到尽头 return; int pb; t=(BTNode *)malloc(sizeof(BTNode)); t->data=pre[pre_p]; t->lchild=t->rchild=NULL; pb=GetPosition();//求得前序序列中第pre_p个元素在中序序列中的位置 ++pre_p; CreatBinaryTree(t->lchild,low,pb-1);//建立左子树 CreatBinaryTree(t->rchild,pb+1,high);//建立右子树 } void PostTravel(BTNode *bt)//后序遍历二叉树并输出后序序列 { if(bt!=NULL) { PostTravel(bt->lchild); PostTravel(bt->rchild); if(count_print!=n-1) { printf("%d ",bt->data); ++count_print; } else printf("%d\n",bt->data); free(bt); } } int main() { int i; BTNode *bt; while(scanf("%d",&n)!=EOF) { count_print=0; pre_p=1; bt=(BTNode *)malloc(sizeof(BTNode)); for(i=1; i<=n; ++i) scanf("%d",&pre[i]); for(i=1; i<=n; ++i) scanf("%d",&in[i]); CreatBinaryTree(bt,1,n); PostTravel(bt); } return 0; } ```