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