图论模板

 
//s1先序遍历，s2中序遍历，输出后续遍历
void work(string s1, string s2)
{
	int len = s1.size();
	if(len == 1) 
	{
		cout << s1[0];
		return;	
	}	
	//
	//求根在中序遍历中的位置
	int k = s2.find(s1[0]);
	//
	string s3, s4;
	if(k > 0)	//如果位置大于0，表明有左子树
	{
		s3 = s1.substr(1, k);	//左子树的前序遍历
		s4 = s2.substr(0, k);	//左子树的中序遍历
		work(s3, s4);
	}
	if(k < len - 1)	//如果位置小于最后一个字符的下标表明有右子树
	{
		s3 = s1.substr(k+1, len-k-1);	//右子树的前序遍历
		s4 = s2.substr(k+1, len-k-1);	//右子树的中序遍历
		work(s3, s4);
	}
	cout << s1[0];
}