二叉树遍历例题补充

基于上一篇文章的补充，详细原因见上篇文章末

P1030 [NOIP 2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

输入输出样例 #1

输入 #1

BADC
BDCA

输出 #1

ABCD

说明/提示

【题目来源】

NOIP 2001 普及组第三题

分析

题目给出2行字符串，
分别是中序排列和后序排列

根据上文的结论得：

1. 前序遍历先访问根节点，然后前序遍历左子树，再前序遍历右子树
2. 中序遍历从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树
3. 后序遍历从左到右先叶子节点后父节点的方式遍历访问左右子树，最后是访问根节点

若有后序遍历可以先找根，看样例
中序BADC
后序BDCA
得出A为根，
用中序遍历找出左子树和右子树
得出左子树为B,右子树为CD
再综合得出前序=根+左+右=A+B+CD
前序排列为ABCD
样例中的二叉树示例图

      A//根节点
    /   \
   B     C
        /
       D
前序：根(A)->左子树(B)->右子树(CD)
中序：左子树(B)->根(A)->右子树(DC)
后序：左子树(B)->右子树(DC)->根(A)

代码

#include <iostream>
#include <cstring>
using namespace std;
int len;
string mid_,end_;
int find(char ch){
	for(int i=0;i<len;i++)
		if(mid_[i]==ch)//中序遍历中寻找根
			return i;//返回根的坐标
}
void dfs(int l1,int r1,int l2,int r2){
	char a;
	a=end_[r2];
	int b=find(a);
	cout <<end_[r2];//找到就输出
	if(b>l1)dfs(l1,b-1,l2,r2-r1+b-1);//向左寻找左子树
	if(b<r1)dfs(b+1,r1,l2+b-l1,r2-1);//向右寻找右子树
}
int main(){
	cin>>mid_;//中序
	cin>>end_;//后序
	len=mid_.size();//长度
	dfs(0,len-1,0,len-1);//搜索
	return 0;
}

类似例题：点这里
解法：前序+中序找后序

$题单推荐$

$洛谷题单$ - 二叉树

~ $完结撒花$ ~

附:推荐$洛谷$作为你的刷题区域
题目来自$洛谷$