二叉木遍歴-既知の前序と中序遍歴後序、配列方法

1009:ツリー遍歴

時間制限:1 Secメモリ制限:2 MB

タイトル記述は1本の二叉木の前序遍歴シーケンスと中序遍歴シーケンスを与え,前序と中序シーケンスに基づいて二叉木を還元した後,二叉木の後序遍歴シーケンスを得る
長さnが26以下の2つの文字列を入力します.第1の動作の前順序は遍歴し、第2の動作の中で順序は遍歴する.ツリーのノード名は、A,B,C...最大26個のノードを大文字で表します.
出力入力サンプルには複数のグループがあり、各テストサンプルについて、後順に遍歴する文字列として1行出力されます.
サンプル入力ABC CBA ABCDEFG DCBAEFG GDAFEMHZ ADEFGHMZ
サンプル出力CBA DCBGFEA AEFDHZMG

解題構想の前順は最初のノードがサブツリーのルートノードであるに違いないことを遍歴し、中順遍歴の中でこのノードheadを探し、位置iが見つかったと仮定すると、iの前はheadをルートノードとする左サブツリーであり、iの後ろはheadをルートノードとする右サブツリーである.前序と中序を遍歴して得られた2つの文字列s 1,s 2の長さはいずれもlenであり,s 1を左サブツリー(s 1,1,i)【s 1の最初のノードがルートノードであるため,使用すると捨てる】右サブツリー(s 1,i+1,len−1)【このブロックが右サブツリーである】に分けることができる.同様にs 2を(s 2,0,i−1)と(s 2,i+1,len−1)の2つの部分に分けた.s 1[0]は、後順に遍歴するs 3[len-1]【後順が最後にルートノードを遍歴するため、s 1の最初のノードがs 3の最後のノードである】である.ここで、s 3も2つの部分(s 3,0,i−1)と(s 3,i,(len−1)−1)に分割する.その後,再帰を繰り返すと,後順に遍歴する文字列が得られる.(具体的にはコードを見てみましょう)

なぜ配列を使うのかは一般的に木を建てて、それから遍歴すればいいのですが、配列を使うのは私が配列コードが簡単だと思って、少し字を打つことができて、それからはっきり見えて、更に空間を節約して最後に遍歴した過程を省くことができて、配列が木を復元する時すでに遍歴しているからです.

もしあなたに役に立つなら、勝手にコメントを残して、自分のブログが寂しいと感じて、今日からJavaを勉強して、各段階の学習の心得とどのように学んだのも一緒にブログに送ります

#include
#include
#include
#define rep(i, a, b) for(int i=(a); i(b); i--)
#define reqs(i, a, b) for(int i=(a); i>=(b); i--)
#define ull unsigned __int64
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d
",(t))
#define pf printf
#define prk printf("
")
#define pi acos(-1.0)
#define ms(a,b) memset((a),(b),sizeof((a)))
#define mc(a,b) memcpy((a),(b),sizeof((a)))
#define w while
#define vr vector
#define gr greater
typedef long long ll;
//reverse       
//map::iterator it
//FILE *fp, *os;

char pre[30], mid[30], post[30];
int len;

void _post(int l1,int r1,int l2,int r2,int l3,int r3)
{
	//puts("aaa");
	//printf("post[%d] = pre[%d] = %c
",r3, l1,pre[l1]);
	post[r3] = pre[l1];
	if(l1 == r1)
	return;
	int pos = 0;
	req(i, l2, r2)
	{
		pos++;
		if(pre[l1] == mid[i])
		{
			break;
		}
	}
	//post[r3] = pre[l1];
	//printf("l1 = %d   r1 = %d   l2 = %d   r2 = %d   l3 = %d   r3 = %d    pos = %d
",l1,r1,l2,r2,l3,r3,pos);
	if(l1+1<=l1+pos-1 && l1+pos-1<=r1)
	 _post(l1+1,l1+pos-1,l2,l2+pos-2,l3,l3+pos-2);
	if(l1+pos<=r1)
	 _post(l1+pos,r1,l2+pos,r2,l3+pos-1,r3-1);
	
}

int main()
{
//	fp = fopen("","w+");
//	os = fopen("","r+");
//	ifstream in("fp.txt");
//	ofstream out;
//	out.open("res.txt");
	w(~scanf("%s",pre))
	{
		scanf("%s",mid);
		int len = strlen(pre);
		//printf("len = %d
",len);
		_post(0,len-1,0,len-1,0,len-1);
		post[len] = '\0';
		printf("%s
",post);
	}
	return 0;
}