根据前序中序写后序（正确写法）
题⽬描述
已知⼆叉树的前序和中序遍历，输出该⼆叉树的后序遍历。例如下⾯⼆叉树的前序和中序遍历为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 E
D 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("", "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("\n");
}
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("", "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("\n");
}
return 0;
}
// 中序：CBEDAFG
// 后序：CEDBGFA
// 前序：ABCDEFG
----------------------------------------------------------------------------------------------------------------------len + 1+ i - left;;;;;; len - 1 +i -right;;;;;;
其实⽆论怎么写代码，看别⼈的代码也好，，
⼀定要有⾃⼰的想法也许别⼈的代码很渣
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论