1   2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5  6 typedef struct Node{ 7     char data; 8     struct Node *lchild, *rchild; 9 }Node, *PNode;10 11 void buildTree(PNode *root, char *post, char *in, int len)/*root表示根节点， 12 post表示后序遍历的结果，in表示中序遍历的结果，len表示当前子树的长度*/ 13 {14     if(len == 0)15     {16         *root = NULL;17         return;18     }19     PNode node = (PNode)malloc(sizeof(Node));20     node->data = http://www.mamicode.com/post[len - 1];21     node->lchild = node->rchild = NULL;22     *root = node;23     char *ptr = strchr(in, node->data);//找到根节点在中序遍历中的位置 24     int leftlen = strlen(in) - strlen(ptr);//左子树的长度 25     int rightlen = len - leftlen - 1;//右子树的长度 26     buildTree(&(*root)->lchild, post, in, leftlen);//递归建左子树 27     buildTree(&(*root)->rchild, post + leftlen, ptr + 1, rightlen);//递归建立右子树 28 }29 30 void preOrderTraverse(PNode root)//前序遍历 31 {32     if(root == NULL)33         return ;34     printf("%c", root->data);35     preOrderTraverse(root->lchild);36     preOrderTraverse(root->rchild);37 }38 int main()39 {40     char post[100], in[100];41     while(scanf("%s %s", post, in) != EOF)42     {43         PNode root = NULL;44         buildTree(&root, post, in, strlen(in));45         preOrderTraverse(root);46         printf("\n");47     }48     return 0;49 }         

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 //这里是不建树的方式，代码比较简洁  5 //post代表后序遍历的结果， in代表中序遍历的结果，ans存放前序遍历的结果， n是当前节点的个数  6 void Traverse(int n, char *post, char *in, char *ans) 7 { 8     if(n <= 0) 9         return;10     int p = strchr(in, post[n - 1]) - in;/*因为后序的最后一个是当前子树的根节点，11     所以找到根节点在中序遍历中的位置 让它减去in获得它在中序遍历中的位置 */ 12     13     Traverse(p, post, in, ans + 1);/*递归它的左子树，左子树的长度为p, 14     后序的开始位置为还是为post，中序的开始位置也是一样，把保存前序的数组加一 */ 15     16     Traverse(n - p - 1, post + p, in + p + 1, ans + p + 1);/*递归它的右子树，17     其中后序的开始位置就是post+p，因为后续的根节点在最后，所以不用加一，但是中序的要加一，因为中间有个根节点要跳过它，ans当然是+p+1了*/ 18     ans[0] = post[n - 1];//将当前子树的根节点赋值给ans， 19 }20 int main()21 {22     char str1[100], str2[100]; 23     while(scanf("%s %s", str1, str2) != EOF)24     {25         char ans[100];26         int len = strlen(str2);27         Traverse(len, str1, str2, ans);28         ans[len] = ‘\0‘;29         puts(ans);30     }31     return 0;32 }