首页 > 代码库 > NOIP 求前序排列
NOIP 求前序排列
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
输入格式
每个测试文件只包含一组测试数据,每组输入包含两行,第一行输入一个字符串表示二叉树的中序排列,第二行输入一个字符串表示二叉树的后序排列。
输出
对于每组输入数据,输出二叉树的先序排列。
样例输入
BADC
BDCA
样例输出
ABCD
通过后序排列确定最后一个节点是根节点
然后再通过中序排列找到根节点的左右 找到左子树和右子树的范围
而它们的范围又和后序排列左右子树的范围相同
再找左右子树的根节点 递归下去
通过前序排列输出即可。。。。。
#include<iostream> #include<cstring> using namespace std; char q[10],w[10]; void dfs(int pre_sta,int pre_end,int aft_sta,int aft_end) //分别是中序排列的起点终点 后序排列的起点终点 { int i; char node; int range; if(pre_end<pre_sta||aft_end<aft_sta) return; if(pre_sta==pre_end) //左子树或右子树只有一个节点 { cout<<q[pre_sta]; return; } node=w[aft_end]; for(i=pre_sta;i<=pre_end;i++) //找根节点再中序排列的位置 { if(q[i]==node) break; } range=i-pre_sta; cout<<node; dfs(pre_sta,i-1,aft_sta,aft_sta+range-1); //左子树 dfs(i+1,pre_end,aft_sta+range,aft_end-1); //右子树 } int main() { int len; while(cin>>q>>w) { len=strlen(q); dfs(0,len-1,0,len-1); cout<<endl; } return 0; }
NOIP 求前序排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。