给定前序遍历和中序遍历求后序遍历
两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示，最多26个结点。对于每组测试样例，输出一行为后序遍历的字符串。
递归：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void getpost(char *, char *, char *, int, int, int, int, int, int);//由先序遍历和中序遍历得到后序遍历
int main()
{
char pre = {0}, in = {0}, post = {0};
//pre，in，post分别记录前序遍历，中序遍历和后序遍历
while(scanf("%s", pre) != EOF)
{
scanf("%s", in);
int len = strlen(pre);
getpost(pre, in, post, 0, len - 1, 0, len - 1, 0, len - 1);
//参数：前、中、后序遍历，前、中、后序遍历记录数组的当前处理段的首尾
printf("%s", post);
printf("\n");
}
}
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)
{
if(pre_start > pre_end)
return;
int i = 0;
while(in != pre)//找到各个子树的中序遍历中的根
i++;
post = pre;
getpost(pre, in, post, pre_start + 1, pre_start + i, in_start, in_start + i - 1, post_start, post_start + i - 1);//处理左子树
getpost(pre, in, post, pre_start + i + 1, pre_end, in_start + i + 1, in_end, post_start + i, post_end - 1 );//处理右子树
}
画一棵树之后写出来先序中序后序遍历序列就很容易了
非递归方式得到后序遍历的方式想不太清楚没写出来，就放弃了
页:
[1]