先序遍歴と中序遍歴の後序遍歴を求めることが知られている--二叉樹

思想データ構造の授業では、preから始めます.preを処理するのは連続したセグメントで、頭にあるのはルートノードなので、インタフェース関数は次のようになります.
void solve(tree* root,int low,int high,int rootpos)
rootは現在のノードであり、low、highはmid列に対してである.rootposはルートノードのpre列における位置である
構想は再帰的で、コードは以下の通りである.

#include "iostream"
#include "string"
using namespace std;

struct tree
{
	char name;
	tree* left;
	tree* right;
};
string pre,mid;

//tree* solve(tree* root,int low,int high,int rootpos)
//{
//	if (low>high)
//		return NULL;
//	if(low==high)
//	{
//		tree *temp=(tree*) malloc(sizeof(tree*));
//		temp->left=temp->right=NULL;
//		temp->name=mid[low];
//		return temp;
//	}
//	int rpos=-1;
//	while (mid[++rpos]!=pre[rootpos]);
//	root->name=pre[rootpos];
//	root->left=(tree*) malloc(sizeof(tree*));
//	root->right=(tree*) malloc(sizeof(tree*));
//	root->left=solve(root->left,low,rpos-1,rootpos+1);
//	root->right=solve(root->right,rpos+1,high,rpos+1);
//	return root;
//}

void solve(tree* root,int low,int high,int rootpos)
{
	if(low==high)
	{
		root->left=root->right=NULL;
		root->name=mid[low];
		return;
	}
	int rpos=-1;
	while (mid[++rpos]!=pre[rootpos]);
	root->name=pre[rootpos];
	root->left=root->right=NULL;
	if (low<=rpos-1)
	{
		root->left=(tree*) malloc(sizeof(tree*));
		solve(root->left,low,rpos-1,rootpos+1);
	}
	if(rpos+1<=high)
	{
		root->right=(tree*) malloc(sizeof(tree*));
		solve(root->right,rpos+1,high,rpos+1);
	}
}

void TraversalPost(tree* node)
{
	if (node)
	{
		TraversalPost(node->left);
		TraversalPost(node->right);
		printf("%c ",node->name);
	}
}

void main()
{
	int i,j;
	tree* root=(tree*)malloc(sizeof(tree*));
	while (cin>>pre>>mid)
	{
		root->left=root->right=NULL;
		root->name=mid[0];
		solve(root,0,mid.length()-1,0);
		TraversalPost(root);
		cout<<endl;
	}
}

その中で注釈された部分も使え、以下の同名関数と同じ方法、2つの形式です.
呼び出しはroot=solve(root,0,mid,length(-1,0);
=======================================================================
Hope you enjoy it !