首页 > 代码库 > codevs 1013 求先序排列(二叉树遍历)
codevs 1013 求先序排列(二叉树遍历)
传送门
Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
Input
两个字符串,分别是中序和后序(每行一个)
Output
一个字符串,为二叉树的先序序列
Sample Input
BADC
BDCA
Sample Output
ABCD
思路
我们知道,前序遍历(PreOrder):根节点->左子树->右子树;中序遍历(InOrder):左子树->根节点->右子树;(PostOrder)后序遍历:左子树->右子数->根节点。故PostOrder的最后一个数为树根。由PostOrder找出树根后,可根据InOrder中分出树根的左右子树。InOrder中,树根左边为其左子树,右边为右子树。例如样例中:
in : BADC
post:BDCA
左子树为B,右子树为DC;在InOrder中找根的位置pos;
则左子树中序序列为In.substr(0,pos),后序序列为Post.substr(0,pos)
右子树的先序序列为In.subst(pos+1,len-pos-1),后序序列为post.substr(pos,len-pos-1)
通过递归不断重复以后步骤,当串为空时退出
#include<bits/stdc++.h>using namespace std;string in,post;void pre(string in,string post){ if (post.empty()) return; int pos,len = post.size(); char ch = post[len-1]; cout << ch; pos = in.find(ch); pre(in.substr(0,pos),post.substr(0,pos)); pre(in.substr(pos + 1,len - pos - 1),post.substr(pos,len - pos - 1));}int main(){ cin >> in >> post; pre(in,post); return 0;}
#include<bits/stdc++.h>using namespace std;const int maxn = 15;void pre(int N,char a[],char b[]){ if (N <= 0) return; int pos; for (int i = 0;i < N;i++) if (a[i] == b[N-1]) pos = i; printf("%c",b[N-1]); pre(pos,a,b); pre(N - pos - 1,a + pos + 1,b + pos);}int main(){ char a[maxn],b[maxn]; scanf("%s %s",a,b); int len = strlen(a); pre(len,a,b); return 0;}
codevs 1013 求先序排列(二叉树遍历)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。