已知树的中序遍历和树的先序遍历，求树的后序遍历。原题
思路
1、树的先序遍历的第一个元素一定是当前节点的根，然后在中序中找到根的位置，分别递归左右子树，直到只有一个元素或者零个元素为止。
2、关于递归中数组的下标问题：首先可以确定的是左子树中，先序遍历和中序遍历所含的元素一定是相等的，然后很容易得到在中序遍历中，首尾元素下标之差是index-1-in_begin,然后先序遍历的起点是pre_begin+1（要把根那个元素挖掉），所以将以上两者相加，就得到左子树了先序遍历的终点。而右子树先序遍历的起点就是左子树先序遍历的终点加一，因为先序遍历两子树之间不存在根节点隔开。
3、在遍历左子树，遍历右子树之后直接输出当前根节点就是后序遍历的值。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
using namespace std;
string pre, in;
void get_tree(int pre_begin, int pre_end, int in_begin, int in_end)
{
if (pre_begin > pre_end || in_begin > in_end)
return;
int index = in.find(pre[pre_begin]);
get_tree(pre_begin + 1, pre_begin + index -in_begin, in_begin, index - 1);//注意这里第一个参数是pre_begin+1,不要忘记加一
get_tree(pre_begin + index - in_begin + 1, pre_end, index + 1, in_end);
cout << pre[pre_begin];
}
int main()
{
cin >> in;
cin >> pre;
int size = in.size() - 1;
get_tree(0, size, 0, size);
return 0;
}
|