甘肃省水利厅引洮工程建设管理局网站,手机网站建设 小程序,湛江市工程建设领域网站,大连营销团队题目
给出一棵二叉树的中序与后序排列。求出它的先序排列。#xff08;约定树结点用不同的大写字母表示#xff0c;且二叉树的节点个数≤8#xff09;。
输入输出格式
输入格式
共两行#xff0c;均为大写字母组成的字符串#xff0c;表示一棵二叉树的中序与后序排列。…题目
给出一棵二叉树的中序与后序排列。求出它的先序排列。约定树结点用不同的大写字母表示且二叉树的节点个数≤8。
输入输出格式
输入格式
共两行均为大写字母组成的字符串表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串表示一棵二叉树的先序。
输入输出样例
输入样例
BADC
BDCA
输出样例
ABCD
解析
基本知识给你一个后序遍历那么最后一个就是根如ABCD则根为D。因为题目求先序意味着要不断找根。
那么我们来看这道题方法示例
中序ACGDBHZKX后序CDGAHXKZB首先可找到主根B
那么我们找到中序遍历中的B由这种遍历的性质可将中序遍历分为ACGD和HZKX两棵子树
那么对应可找到后序遍历CDGA和HXKZ从头找即可
从而问题就变成求
1.中序遍历ACGD后序遍历CDGA的树
2.中序遍历HZKX后序遍历HXKZ的树
接着递归按照原先方法找到1.子根A再分为两棵子树2.子根Z再分为两棵子树。
就按这样一直做下去先输出根再递归
模板概括为step1:找到根并输出
step2:将中序后序各分为左右两棵子树
step3:递归重复step1,2。
#includeiostream
#includecstring
using namespace std;
void beford(string in,string after){if(in.size()0){char chafter[after.size()-1];coutch;int kin.find(ch);beford(in.substr(0,k),after.substr(0,k));//substr功能为复制子字符串要求从指定位置开始并具有指定的长度。如果没有指定长度或超出了源字符串的长度则子字符串将延续到源字符串的结尾beford(in.substr(k1),after.substr(k,in.size()-k-1));//递归左右两个子树}
}
int main(){string inord,aftord;cininordaftord;beford(inord,aftord);coutendl;return 0;
}
