洛谷问题美国血统 American Heritage、新二叉树题解（关于二叉树的遍历问题）
目录
一.美国血统 American Heritage
二.新二叉树
一.美国血统 American Heritage
P1827 [USACO3.4] 美国血统 American Heritage - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 26 个的顶点。
这是在样例输入和样例输出中的树的图形表达方式：
C
/ \
/ \
B G
/ \ /
A D H
/ \
E F
附注：
- 树的中序遍历是按照左子树，根，右子树的顺序访问节点；
- 树的前序遍历是按照根，左子树，右子树的顺序访问节点；
- 树的后序遍历是按照左子树，右子树，根的顺序访问节点。
输入格式
第一行一个字符串，表示该树的中序遍历。
第二行一个字符串，表示该树的前序遍历。
输出格式
单独的一行表示该树的后序遍历。
输入输出样例
输入 #1
ABEDFCHG CBADEFGH
输出 #1
AEFDBHGC
首先，我们知道
先序遍历是：根左右
中序遍历是：左根右
后序遍历是：左右根
那么先序遍历的第一个就是树的根节点，那么我们在中序遍历可以找出树的左子树和右子树。
为了求出后序遍历，我们需要按照左右根的遍历方式，所以我们递归先将左子树递归完再将右子树递归完，再输出。
我们在分好的左子树区继续找根节点，根节点后面再分左子树和右子树，当左子树找不到根节点，即head>=tail，那么递归右边，当递归完所有节点，最后输出。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int head_a,int tail_a,int head_b,int tail_b)
{
if(head_a>tail_a||head_b>tail_b) return;
for(int i=head_a;i<=tail_a;i++){
if(a[i]==b[head_b])//在中序遍历找到根节点
{
dfs(head_a,i-1,head_b+1,head_b+i-head_a);//左子树区，找下一个根节点
dfs(i+1,tail_a,head_b+1+i-head_a,tail_b);//右子树区
cout<<a[i];//输出
}
}
}
int main()
{
cin>>a>>b;
int len=a.size();
dfs(0,len-1,0,len-1);
return 0;
}P1030 [NOIP2001 普及组] 求先序排列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题目非常相似，可以练习一下。
二.新二叉树
P1305 新二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
输入一串二叉树，输出其前序遍历。
输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，每一个字母为节点，后两个字母分别为其左儿子。特别地，数据保证第一行读入的节点必为根节点。
空节点用 * 表示
输出格式
二叉树的前序遍历。
输入输出样例
输入 #1
6 abc bdi cj* d** i** j**
输出 #1
abdicj
由于题目规定输入的第一行为根节点，那么我们便可以继续往下递归，我们可以先找出第一行的第二个节点，如果不为’*‘，那么此树有左子树，由于是求先序遍历，按照根左右的遍历方式，先输出遍历到的节点，再递归左子树，最后递归右子树，当遇到’*‘就return。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
string a[30];
int n;
void dfs(char k)
{
if(k=='*') return ;//遇到*表示当前节点为NULL，直接return
cout<<k;//直接输出
for(int i=1;i<=n;i++){
if(a[i][0]==k)//找到对应的节点
{
dfs(a[i][1]);//递归左子树
dfs(a[i][2]);//递归右子树
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(a[1][0]);//第一个就是根节点，从这里开始递归
return 0;
}