【模板】【建树】前序+中序 后序+中序

建树：已知一棵树的 前序+中序 或 后序+中序 即可以递归的建立一棵树。

#include<iostream>
#include<cstdlib>
using namespace std;

const int N = 100;
int n;
int mind[N], prio[N], post[N];

struct Tree {
	int data;
	Tree* lchild, * rchild;
};

//先序 + 中序
Tree* CreateByPrio(int x,int y,int z)// x:子树中序起点 y:子树先序起点 z:子树长度
{
	if (z == 0) return NULL;
	Tree* root = new Tree;
	root->data = prio[y];
	int len;
	for (int i = x; i < x + z; i++)
	{
		if (mind[i] == prio[y]) {
			len = i - x;
			break;
		}
	}
	root->lchild = CreateByPrio(x, y + 1, len);
	root->rchild = CreateByPrio(x + len + 1, y + len + 1, z - len - 1);
	return root;
}

//后序 + 中序
Tree* CreateByPost(int x, int y, int z)// x:子树中序起点 y:子树后序起点 z:子树长度
{
	if (z == 0) return NULL;
	Tree* root = new Tree;
	root->data = post[y + z - 1];
	int len;
	for (int i = x; i < x + z; i++)
	{
		if (mind[i] == post[y + x - 1])
		{
			len = i - x;
			break;
		}
	}
	root->lchild = CreateByPost(x, y, len);
	root->rchild = CreateByPost(x + len + 1, y + len, z - len - 1);
	return root;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> mind[i];
	for (int i = 0; i < n; i++)
		cin >> prio[i];
	return 0;
}