题目描述
已知二叉树的前序和中序遍历，输出该二叉树的后序遍历。例如下面二叉树的前序和中序遍历为ABDC、DBAC，后序遍历为DBCA。
A
/
/
B C
/
/
D
输入
包括多组测试数据。
每组1行，包含两个字符串，分别为叉树的前序和中序遍历。
输出
二叉树的后序遍历。
样例输入
ABDC DBAC
BCAD CBAD
样例输出
DBCA CDAB
-----------------------------------------------------------------------------------------------
举个栗子
前序：ABCDEFG
中序：CBEDAFG
思想：一步一步划分，将其存入两个数组中；从第一个根开始划分；；；；
看图：
--------------------------------------------------------------------------------------------
left = 1 CBEDAFG right = 7
↓
left = 1 CBED right = 4 A left = 6 FG right = 7
↓ ↓
C B ED left = 6 right = 6
↓ ↓
left = 1 right = 1 left = 3, right = 4
↓
left = 3, right = 3
1.如果left < right 那么继续递归
2，如果left == right 说明它是一个叶子节点，则T->lchild = T->right = null;
3,如果 left > right 说明它是一个null, T=null;
----------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#define _OJ_
typedef struct tree1
{
char data;
struct tree1 *lchild;
struct tree1 *rchild;
} tree1, *tree;
tree
creat_tree(tree T, int len, int left, int right, char *t1, char *t2)
{
if(left < right) {
int i = 1;
T = (tree) malloc (sizeof(tree1)); T->data = t1[len];
while (t1[len] != t2[i])
i++;
T->lchild = creat_tree(T->lchild, len + 1, left, i - 1, t1, t2);
// 递归遍历左子树 left不变， i - 1；
T->rchild = creat_tree(T->rchild, len + i + 1 - left, i + 1, right, t1, t2);
// 递归遍历左子树 right 不变， i + 1;len + i + 1 - left,
}//难点在于参数的传递
else if(left == right) {
T = (tree) malloc (sizeof(tree1)); T->data = t1[len];
T->lchild = T->rchild = NULL;
}
else if(left > right) T = NULL;
return T;
}
void
travers(tree T)
//递归遍历一棵树
{
if(T) {travers(T->lchild);
travers(T->rchild);
printf("%c", T->data);
}
}
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
tree T;
char t1[20], t2[20];
int i, len;
while(scanf("%s", t1) != EOF) {
scanf("%s", t2);
len = strlen(t1);//0号位不用
for(i = len;i >= 0; i--) {
t1[i + 1] = t1[i];
t2[i + 1] = t2[i];
}
T = creat_tree(T, 1, 1, len, t1, t2);
travers(T);
printf("
");
}
return 0;
}
-----------------------------------------------------------------------------------------------------------------------
通过举一反三我们可以同理可得通过中序和后序写前序
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#define _OJ_
typedef struct tree1
{
char data;
struct tree1 *lchild;
struct tree1 *rchild;
} tree1, *tree;
tree
creat_tree(tree T, int len, int left, int right, char *t1, char *t2)
{
if(left < right) {
int i = 1;
T = (tree) malloc (sizeof(tree1)); T->data = t2[len];
while (t2[len] != t1[i])
i++;
//对于右子树，ｉ ＋ 1 , right不变
T->rchild = creat_tree(T->rchild, len - 1, i + 1, right, t1, t2);
T->lchild = creat_tree(T->lchild, len + i - 1 - right, left, i - 1, t1, t2);
}//对于左子树left不变， i - 1, 特别注意 参数len + i - 1 - right
else if(left == right) {
T = (tree) malloc (sizeof(tree1)); T->data = t2[len];
T->lchild = T->rchild = NULL;
}
else if(left > right)
T = NULL;
return T;
}
void
travers(tree T)
//递归遍历一棵树
{
if(T) {
printf("%c", T->data);
travers(T->lchild);
travers(T->rchild);
}
}
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
tree T;
char t1[20], t2[20];
int i, len;
while(scanf("%s", t1) != EOF) {
scanf("%s", t2);
len = strlen(t1);//0号位不用
for(i = len;i >= 0; i--) {
t1[i + 1] = t1[i];
t2[i + 1] = t2[i];
}
T = creat_tree(T, len, 1, 7, t1, t2);
travers(T);
printf("
");
}
return 0;
}
// 中序：CBEDAFG
// 后序：CEDBGFA
// 前序：ABCDEFG
----------------------------------------------------------------------------------------------------------------------
len + 1+ i - left;;;;;; len - 1 +i -right;;;;;;
其实无论怎么写代码，看别人的代码也好，，
一定要有自己的想法！！！也许别人的代码很渣！！！