大意：告诉你一棵二叉树的先序遍历和中序遍历求该二叉树的后续遍历
代码：
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 30; 7 char pr[maxn], mi[maxn]; 8 9 struct Node {10 int left;11 int right;12 }tr[maxn];13 14 int root;15 16 void init(int p) {17 tr[p].left = -1;18 tr[p].right = -1;19 }20 21 void fason(int pa, int son) {22 if(son < pa) {23 if(tr[pa].left == -1) {24 init(son);25 tr[pa].left = son;26 } else fason(tr[pa].left, son);27 } else {28 if(tr[pa].right == -1) {29 init(son);30 tr[pa].right = son;31 } else fason(tr[pa].right, son);32 }33 }34 35 void build_tree() {36 for(int i = 0; mi[i]; i++) {37 if(mi[i] == pr[0]) {38 root = i;39 init(root);40 break;41 }42 }43 for(int i =1; pr[i]; i++) {44 for(int j = 0; mi[j]; j++) {45 if(mi[j] == pr[i]) {46 fason(root, j);47 break;48 }49 }50 }51 }52 void pre_out(int p) {53 printf("%c", mi[p]);54 if(tr[p].left != -1) pre_out(tr[p].left);55 if(tr[p].right != -1) pre_out(tr[p].right);56 }57 void mid_out(int p) {58 if(tr[p].left != -1) mid_out(tr[p].left);59 printf("%c", mi[p]);60 if(tr[p].right != -1) mid_out(tr[p].right);61 }62 63 void back_out(int p) {64 if(tr[p].left != -1) back_out(tr[p].left);65 if(tr[p].right != -1) back_out(tr[p].right);66 printf("%c", mi[p]);67 }68 69 int main() {70 while(EOF != scanf("%s %s",pr, mi) ) {71 build_tree();72 pre_out(root);73 puts("");74 mid_out(root);75 puts("");76 back_out(root);77 puts("");78 }79 return 0;80 }