1366：二叉樹輸出(btout)(樹的經典題)

http://ybt.ssoier.cn:8088/problem_show.php?pid=1366

【題目描述】
樹的凹入表示法主要用于樹的螢幕或列印輸出，其表示的基本思想是兄弟間等長，一個結點的長度要不小于其子結點的長度。二叉樹也可以這樣表示，假設葉結點的長度為1，一個非葉結點的長度等于它的左右子樹的長度之和。

一棵二叉樹的一個結點用一個字母表示（無重複），輸出時從根結點開始：

每行輸出若幹個結點字元（相同字元的個數等于該結點長度），

如果該結點有左子樹就遞歸輸出左子樹；

如果該結點有右子樹就遞歸輸出右子樹。

假定一棵二叉樹一個結點用一個字元描述，現在給出先序和中序周遊的字元串，用樹的凹入表示法輸出該二叉樹。

【輸入】
兩行，每行是由字母組成的字元串（一行的每個字元都是唯一的），分别表示二叉樹的先序周遊和中序周遊的序列。

【輸出】
行數等于該樹的結點數，每行的字母相同。

【輸入樣例】
ABCDEFG
CBDAFEG
【輸出樣例】
AAAA
BB
C
D
EE
F
G

           

純自己思路寫過的，内心簡直是無比開心~~~~

下面，我來講講這個二叉樹輸出是怎麼做的，假裝你已經看完了題目 。

題目給定了先序和中序周遊的字元串，求用樹的凹入表示法輸出該二叉樹

問題來了，凹入表示法是什麼？(小朋友，你是不是有很多問号？ )

凹入表示法：

1.首先需要知道每個結點的長度，結點長度的計算分為葉子結點和非葉子結點，其中葉子結點的長度為1，而非葉子結點的長度等于它左右子樹的長度之和；

2.然後按照先序周遊的順序每行輸出，每個結點輸出的個數取決于該結點的長度。

根據以上分析，可以得知，應該從葉子結點開始計算結點長度，然後非葉子結點的長度就等于其已計算出的左右子樹的長度之和。那麼這種方法和後序周遊的順序是一樣的。

如果以上分析你已經懂了，那麼就可以借助已知先序和中序，求後序的代碼改改就能做出這題啦。(溫馨提醒：不要運作逾時噢，我一開始送出時超了一個測試點，就是結構體的數組開小了，要是考試這樣，就很虧了。是以一定要注意！)

#include<bits/stdc++.h>
using namespace std;
string before, between;
//左子樹長度:pos-l2
//右子樹長度:r2-pos
struct node{
	int s;
	int p;
}a[100];
int F[1005][1005];
void dg(int l1, int r1, int l2, int r2, int l, int r){//l r:表示結點的x y坐标 
	int pos = between.find(before[l1]);
	if(pos > l2) dg(l1+1, r1-(r2-pos), l2, pos-1, l+1, r);//遞歸左子樹 l+1:因為是左子樹，是以x坐标+1 
	if(pos < r2) dg(r1-(r2-pos)+1, r1, pos+1, r2, l, r+1);//遞歸右子樹 r+1:因為是右子樹，是以y坐标+1
	if(F[l+1][r] + F[l][r+1])//計算目前l、r位置結點的長度  非葉子結點等于左右子樹的長度之和
		F[l][r] = F[l+1][r] + F[l][r+1];
	else
		F[l][r] = 1;//葉子結點的長度為1 
	a[between[pos]-'A'+1].p = between[pos];
	a[between[pos]-'A'+1].s = F[l][r];
}
int main(){
	cin >> before >> between;
	dg(0, before.size()-1, 0, between.size()-1, 0, 0);
	for(int i=0; i<before.size(); i++){//輸出 
		cout << before[i];
		while(--a[before[i]-'A'+1].s)
			cout << before[i];
		cout << endl;
	}
	return 0;
}
           

關于後序周遊中的遞歸左子樹和遞歸右子樹的寫法，如果有疑問的可以看我的上一篇文章，良心推薦，記得點個贊~~~~歡迎指點

1339：【例3-4】求後序周遊https://blog.csdn.net/qq_39053800/article/details/108182882