若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1458: 3.4.2 American Heritage 美国血统

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,081

题目描述

农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树,并且把二叉树以更线性 的”树的中序遍历“和”树的前序遍历“的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的”树中序遍历“和”树前序遍历“的符号后,创建奶牛家谱的”树的后序遍历“的符号。每一头奶牛的姓名被 译为一个唯一的字母。(你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树。)显然,这里的树不会有多余26个的顶点。这是在样例输入和样例输出中的树的图形表达方式:

C
/ \
/ \
B G
/ \ /
A D H
/ \
E F

树的中序遍历是打印左子树,根和右子树。树的前序遍历是打印根,左子树和右子树。树的后序遍历是打印左子树,右子树和根。

输入

第一行: 树的中序遍历 第二行: 同样的树的前序遍历

输出

单独的一行表示该树的后序遍历。

样例输入

ABEDFCHG
CBADEFGH

样例输出

AEFDBHGC

参考代码

#include<stdio.h>
#include<string.h>
char a[1000];
char b[1000];
int n;
int search(int x1,int y1,int x2,int y2) 
{
    if(x1>y1) 
    {
        return 0;
    } else if(x1==y1) 
    {
        printf("%c",a[x1]);
        return 0;
    } else 
    {
        int mid;
        for (int i=x2;i<=y2;i++)//寻找分割点 
        {
            if(b[i]==a[x1])
                        mid=i;
        }
        search(x1+1,x1+mid-x2,x2,mid-1);
        search(x1+mid-x2+1,y1,mid+1,y2);
        printf("%c",a[x1]);
        //a[x1]表示首节点
    }
}
int main() 
{
    gets(b);
    gets(a);
    n=strlen(a);
    search(0,n-1,0,n-1);
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist