博客

由中序后序序列求前序序列

我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。

用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树

中根序列是9 5 32 67

后根序列9 32 67 5

前根序列5 9 67 32

输入

两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。

输出

一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

样例输入

9 5 32 67

9 32 67 5

样例输出

5 9 67 32

解题思路：用递归，先处理根节点，在处理左子树，再处理右子树，将后序序列作为查找条件，然后将中序序列分成左右子树两部分递归查找输出，要注意递归的结束条件。

#include<iostream>
using namespace std;
int a[100], b[100];
void find(int f1, int e1, int f2, int e2) {
	int i;
	cout << b[e2]<<" ";
	if (f1 == e1)          //递归结束条件
		return;
	for (i = f1; i <= e1; i++)
		if (a[i] == b[e2])
			break;
	if(i>0)
	  find(f1, i-1, f2,f2+(i-1)-f1);
	if(i<e1)
	  find(i + 1, e1, f2+i-f1, e2 - 1);
}
int main() {
	int i=0;
	while (cin  >> a[i++]) {
		if (cin.get() != ' ')
			break;
	}
	int j = 0;
	while (cin >> b[j++]) {
		if (cin.get() != ' ')
			break;
	}
	find(0, i-1, 0, j-1);
	return 0;
}