1492 - 二叉树遍历2
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
Input
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
Output
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。
Examples
Input
ABC CBA ABCDEFG DCBAEFG
Output
CBA DCBGFEA
Solution C
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct BTNode{ char data; struct BTNode *left,*right; }BTNode,*BTree; void build(BTree *t,char *pre,char *in,int len){ if (len<=0) { *t=NULL; return; } int pos=strchr(in,pre[0])-in; *t=(BTNode *)malloc(sizeof(BTNode)); (*t)->data=*pre; build(&(*t)->left,pre+1,in,pos); build(&(*t)->right,pre+pos+1,in+pos+1,len-pos-1); } void postorder(BTree t){ if (t) { postorder(t->left); postorder(t->right); printf("%c",t->data); } } void clean(BTree *t){ if (*t) { clean(&(*t)->left); clean(&(*t)->right); free(*t); } } int main(){ BTree root; char pre[30],in[30]; // freopen("1.txt","r",stdin); while (scanf("%s %s",pre,in)!=EOF) { build(&root,pre,in,strlen(pre)); postorder(root); clean(&root); printf("\n"); } // fclose(stdin); return 0; }
Solution C++
#include <stdio.h> #include <string.h> void run(char a[],char b[]) { int i,n,j; char c[33],d[33]; n=strlen(a)-1; if(n<=0) { printf("%s",a); return; } i=0; while(b[i]!=a[0]) i++; for(j=0;j<i;j++) { c[j]=a[j+1]; d[j]=b[j]; } c[i]=0; d[i]=0; run(c,d); for(j=0;j<n-i;j++) { c[j]=a[j+i+1]; d[j]=b[j+i+1]; } c[n-i]=0; d[n-i]=0; run(c,d); printf("%c",a[0]); } int main() { char a[33],b[33]; scanf("%s",a); while(strcmp(a,"")!=0) { scanf("%s",b); run(a,b); printf("\n"); strcpy(a,""); scanf("%s",a); } return 0; }