树遍历的应用——树的重建

需要用到的概念
- 有根二叉树：如果一根树拥有一个根结点，且所有结点的子结点数都不超过2，那么这棵树称为有根二叉树。
- 树的遍历：
  - 前序遍历（Preorder Tree Walk）：按照根结点、左子树、右子树的顺序输出结点编号。
  - 中序遍历（Inorder Tree Walk）：按照左子树、根结点、右子树的顺序输出结点编号。
  - 后序遍历（PostOrder Tree Walk）：按照左子树、右子树、根结点的顺序输出结点编号。
  - （可以发现左子树、右子树的先后顺序没有改变，而根结点的位置对应了“前”“中”“后”三个位置）
题目描述
树的重建（Reconstruction of the tree）
- 现有两个结点序列，分别是对同一个二叉树进行前序遍历和中序遍历的结果。请编写一个程序，输出该二叉树按后序遍历时的结果。
- 输入
  - 第1行输入二叉树的结点数n。
  - 第2行输入前序遍历的结点编号序列，相邻编号用空格隔开。
  - 第3行输入中序遍历的结点编号序列，相邻编号用空格隔开。
  - 结点编号为从1至n的整数。请注意，1不一定是根结点。
- 输出
  - 在1行中输出按后序遍历时的结点编号序列。相邻结点编号之间用1个空格隔开。
- 限制
  - 1≤结点数≤100
解题思路
输出未知二叉树的后序遍历
这个问题可以变形为：
- 输出当前二叉树左子树的后序遍历；
- 输出当前二叉树右子树的后序遍历；
- 输出当前二叉树的根结点。
根据已知的前序遍历和后序遍历，我们可以知道：
- 当前二叉树的根结点 -> 二叉树的前序遍历的首元素；
- 当前二叉树的左右子树 -> 二叉树的中序遍历的位于根结点左右两边的元素集合。
找到根结点的过程我们可以通过前序遍历的特性O(1)的查询。
对于寻找左右子树的过程，我们也可以通过预处理O(1)的查询。
- 预处理：将中序遍历中的元素下标记录下来，排序后便可以O(1)的查询了。
代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int size = 150;
int n,Preorder[size],Inorder[size];
struct data {
    int k,i;
    data() {
    }
    data(int a,int b) {
	k = a; i = b;
    }//结构体的构造函数 
} temp[size];
bool cmp(data a,data b) {
    return a.k < b.k;
}//结构体的比较函数 
void make_Postorder(int l1,int r1,int l2,int r2) {
    if(l1 == r1) cout << Preorder[l1] << ' ';//递归出口:如果到达叶结点则退出 
    else {
	int root = Preorder[l1];
	int divide = temp[root].i;//记录此子树中根在中序遍历中的位置 
	int size1 = divide - l2;//记录此子树中左子树的结点个数 
	make_Postorder(l1 + 1,l1 + size1,l2,divide - 1);
	make_Postorder(l1 + size1 + 1,r1,divide + 1,r2);
	cout << root << ' ';
    }
    return;
}
int main() {
    memset(Preorder,0,sizeof(Preorder));//初始化 
    memset(Inorder,0,sizeof(Inorder));
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> Preorder[i];
    for(int i = 1;i <= n;i++) {
    	cin >> Inorder[i];
		temp[i] = data(Inorder[i],i);
    }	
    sort(temp + 1,temp + 1 + n,cmp);
    make_Postorder(1,n,1,n);
    return 0; 
}

NOIP 2018 RP++

树遍历的应用——树的重建

需要用到的概念

题目描述

解题思路

代码实现