首页 > 代码库 > 美国血统
美国血统
【题目描述】
农夫约翰把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母（你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树）。显然，这里的树不会有多余26个的顶点。
这是在样例输入和样例输出中的树的图形表达方式：
C
/ \
B G
/ \ /
A D H
/ \
E F
树的中序遍历是打印左子树、根和右子树；
树的前序遍历是打印根、左子树和右子树；
树的后序遍历是打印左子树、右子树和根。
【输入描述】
第一行：树的中序遍历；
第二行：树的前序遍历。
【输出描述】
输出单独的一行，表示该树的后序遍历。
【样例输入】
ABEDFCHG
CBADEFGH
【样例输出】
AEFDBHGC
源代码：#include<cstdio>#include<cstring>char Front[101],Middle[101];void Solve(int Left,int Right,int t){ if (Left>Right) return; int T=Left; while (Middle[T]!=Front[t]) T++; Solve(Left,T-1,t+1); Solve(T+1,Right,t+T-Left+1); printf("%c",Front[t]); //没有儿子就输出，自然为后序遍历。}int main(){ scanf("%s%s",Middle+1,Front+1); //读入方式值得学习。 int Length=strlen(Middle+1); Solve(1,Length,1); return 0;}/* 古董题也还是很难绕过来。 解题思路： 取前序遍历的首字母，在中序遍历中查找，找到后将其分为左右子树，依次递归。*/
美国血统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。