给定前序遍历和中序遍历求后序遍历

Ranbo_

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示，最多26个结点。

对于每组测试样例，输出一行为后序遍历的字符串。

递归：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. void getpost(char *, char *, char *, int, int, int, int, int, int);//由先序遍历和中序遍历得到后序遍历
   
6. 
   
7. int main()
   
8. {
   
9.     char pre[30] = {0}, in[30] = {0}, post[30] = {0};
   
10.     //pre，in，post分别记录前序遍历，中序遍历和后序遍历
    
11.    
    
12.     while(scanf("%s", pre) != EOF)
    
13.     {
    
14.         scanf("%s", in);
    
15.         int len = strlen(pre);
    
16.         getpost(pre, in, post, 0, len - 1, 0, len - 1, 0, len - 1);
    
17.         //参数：前、中、后序遍历，前、中、后序遍历记录数组的当前处理段的首尾
    
18.         printf("%s", post);
    
19.         printf("\n");
    
20.     }
    
21. }
    
22. 
    
23. void getpost(char pre[], char in[], char post[], int pre_start, int pre_end, int in_start, int in_end, int post_start, int post_end)
    
24. {
    
25.     if(pre_start > pre_end)
    
26.         return;
    
27.     int i = 0;
    
28.     while(in[in_start + i] != pre[pre_start])//找到各个子树的中序遍历中的根
    
29.         i++;
    
30.     post[post_end] = pre[pre_start];
    
31.     getpost(pre, in, post, pre_start + 1,      pre_start + i, in_start,           in_start + i - 1, post_start,      post_start + i - 1);//处理左子树
    
32.     getpost(pre, in, post, pre_start + i + 1, pre_end,       in_start + i + 1, in_end,           post_start + i, post_end - 1      );//处理右子树
    
33. }
    

复制代码

画一棵树之后写出来先序中序后序遍历序列就很容易了

非递归方式得到后序遍历的方式想不太清楚没写出来，就放弃了