树算法

#include<bits/stdc++.h>
using namespace std;
vector<int>inOrder;
vector<int>postOrder;
int n;
typedef struct node{
	int data;
	struct node* lchild;
	struct node* rchild;
}Node;
// 后序序列的起止下标，中序序列的起止下标
Node* create(int postPre,int postEnd,int inPre,int inEnd)
{
	if(postPre>postEnd) return NULL;
    // 建立根节点
	Node* root = (Node*)malloc(sizeof(Node));
	root->lchild=root->rchild=NULL;

	int data = postOrder[postEnd];
	root->data = data;
	int index;
	for(index=inPre;index<=inEnd;++index)
	{
		if(inOrder[index]==data)
		    break;
	}
    // 递归建立左右子树
	root->lchild=create(postPre,postPre+index-inPre-1,inPre,index-1);
	root->rchild=create(postPre+index-inPre,postEnd-1,index+1,inEnd);
	return root;
}
int main()
{
	cin>>n;
	int temp;
	for(int i=0;i<n;++i)
	{
		cin>>temp;
		postOrder.push_back(temp);

	}
	for(int j=0;j<n;++j)
	{
		cin>>temp;
		inOrder.push_back(temp);
	}
	Node* root = create(0,6,0,6);
	queue<Node*>q;
	q.push(root);
	while(!q.empty())
	{
		Node* p=q.front();
		q.pop();
		cout<<p->data<<" ";
		if(p->lchild)
		   q.push(p->lchild);
		if(p->rchild)
		   q.push(p->rchild);
	}

	return 0;
}