题目链接：http://codevs.cn/problem/1013/
题目描述 Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入描述 Input Description
两个字符串，分别是中序和后序（每行一个）
输出描述 Output Description
一个字符串，先序
样例输入 Sample Input
BADC
BDCA
样例输出 Sample Output
ABCD
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 5 #define MaxSize 100 6 7 typedef char ElemType; 8 typedef struct node 9 { 10 ElemType data; //数据元素 11 struct node *lchild; //指向左孩子结点 12 struct node *rchild; //指向右孩子结点 13 } BTNode; 14 15 BTNode *CreateBT2(char *post,char *in,int n) 16 /*post存放后序序列,in存放中序序列,n为二叉树结点个数, 17 本算法执行后返回构造的二叉链的根结点指针*/ 18 { 19 BTNode *s; 20 char r,*p; 21 int k; 22 if (n<=0) return NULL; 23 r=*(post+n-1); //根结点值 24 s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s 25 s->data=r; 26 for (p=in;p<in+n;p++) //在in中查找根结点 27 if (*p==r) 28 break; 29 k=p-in; //k为根结点在in中的下标 30 s->lchild=CreateBT2(post,in,k); //递归构造左子树 31 s->rchild=CreateBT2(post+k,p+1,n-k-1); //递归构造右子树 32 return s; 33 } 34 void PreOrder1(BTNode *b) //先序非递归遍历算法 35 { 36 BTNode *St[MaxSize],*p; 37 int top=-1; 38 if (b!=NULL) 39 { 40 top++; //根结点进栈 41 St[top]=b; 42 while (top>-1) //栈不为空时循环 43 { 44 p=St[top]; //退栈并访问该结点 45 top--; 46 printf("%c",p->data); 47 if (p->rchild!=NULL) //右孩子结点进栈 48 { 49 top++; 50 St[top]=p->rchild; 51 } 52 if (p->lchild!=NULL) //左孩子结点进栈 53 { 54 top++; 55 St[top]=p->lchild; 56 } 57 } 58 printf("\n"); 59 } 60 } 61 int main(int argc, char *argv[]) 62 { 63 char str1[MaxSize],str2[MaxSize];//str1:中序序列，str2：后序序列 64 BTNode *bt; 65 scanf("%s%s",str1,str2); 66 bt=CreateBT2(str2,str1,strlen(str1)); 67 PreOrder1(bt); 68 return 0; 69 }
