Time Limit: 10 second
Memory Limit: 2 MB
问题描述
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
Input
输入文件共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。
Output
输出文件仅一行，表示树的后序遍历的序列。
Sample Input
abdec dbeac
Sample Output
debca
【题解】
先序遍历。
是先输出当前访问到的节点。
然后访问左儿子。然后访问右儿子。
这也就是说先序遍历的第一个节点肯定是根节点。
然后中序遍历。是先访问左儿子。然后输出访问的节点。然后输出右儿子。
我们可以先根据先序遍历。找到这个树的根节点。
假设根节点root在中序遍历中的位置为pos.
则1..pos-1为根的左子树。
pos+1..max为根的右子树。
然后1..pos-1这个左子树。它的根节点是什么呢？
当然就是先序遍历的第二个节点。
因为先序遍历是先访问了根节点。且先输出根节点。
然后访问根节点的左子树。当然第一个访问的是左子树的根节点。然后输出这个左子树的根节点。然后。。
对！就在第二个节点。它就是我们需要的左子树的根节点。
然后我们依然用中序遍历。找到这个<左子树的根节点>的左子树和右子树。
依次类推。根节点的左子树的左子树的根节点为先序遍历的第3个节点..
这些子树可以用区间先表示出来。
如果区间的大小{上限减去下限为1}则这个节点为最下面一层的节点。叶子节点。那么就不要继续操作了。
然后每层递归(什么？你还看不出来这里要用递归？？)都要返回当前这段区间的根节点。给这个根节点
的爸爸。
然后根据得到的l[]和r[]数组(表示某个节点的左儿子和右儿子)。从根节点开始进行后序遍历。
(后序遍历:先访问左儿子。后访问右儿子。最后输出当前访问的这个节点)；
【代码】
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
string s1, s2;
int tot,ll[29],rr[29],root;
int xianxu[29], zhongxu[29];
int now = 1;
void input_data() //输入有这么多行。是为了在字符串前面加一个空格。
{ //因为C++的字符串从0开始计数。有点不习惯。然后把字母转换成相应的数字。a-z对应1..26
string temp;
getline(cin, temp);
s1 = " ";
s1 += temp;
getline(cin, temp);
s2 = " ";
s2 += temp;
for (int i = 1; i <= s1.size() - 1; i++) //字符转数字。
xianxu[i] = s1[i] - 'a' + 1;
xianxu[0] = s1.size() - 1;
for (int i = 1; i <= s2.size() - 1; i++)
zhongxu[i] = s2[i] - 'a' + 1;
zhongxu[0] = s2.size() - 1;
}
int sear_ch(int l, int r) //返回l..r这段区间的根节点。
{
if (r < l) //如果出现右界小于左界的情况。则返回0.表示这个节点不存在。
return 0;
if (l == r)//如果左界和右界相同。则说明这里只有一个节点。则返回这个节点。
return xianxu[now++];//我们要靠先序来判断l..r这个子树的根节点
else//对于只有一个元素来说。我们认为这个xianxu[now]是一个根节点。
{
int pp;
int key2 = xianxu[now];//这是l..r这个子树的根节点
for (int i = l; i <= r; i++)//找到根节点在中序中的位置pp
if (zhongxu[i] == key2) //中序遍历中L..pp-1,和pp+1.。R分别为key2的左子树和右子树。
{
pp = i;
break;
}
now++;//寻找先序遍历中出现的下一个元素即该根节点key2的左子树的根节点。
ll[key2] = sear_ch(l, pp - 1); //注意我们每一段区间的根节点都有记录下来(key2)。然后返回即可。
rr[key2] = sear_ch(pp + 1, r); //先序是先访问完左子树再访问右子树的。要遵循其规律。
return key2;//返回l..r这个区间的根节点。
}
}
void output_ans(int t) //这是后序遍历一棵树的递归程序。
{
if (ll[t] != 0)
output_ans(ll[t]);
if (rr[t] != 0)
output_ans(rr[t]);
char aa = t + 'a' - 1;//要输出的是字母；
putchar(aa);//输出单个字符。
}
void get_ans()
{
int root = xianxu[now];//先找到整棵树的根节点。
int pos = 0;
for (int i = 1;i <= zhongxu[0];i++) //找到其在中序遍历中的位置
if (zhongxu[i] == root)
{
pos = i;
break;
}
now++;//接下来xianxu[now]指向根节点的左子树的根节点。
ll[root] = sear_ch(1, pos - 1);//这是其左子树 sear_ch(l,r)函数会返回l..r这段区间的根节点。
rr[root] = sear_ch(pos + 1, xianxu[0]);//这是其右子树。
output_ans(root);
}
int main()
{
input_data();
get_ans();
return 0;
}