这里我参考了JHF大神的写法啦,直接把输出写在了建树的过程中了。

思路:

先根据先序序列找到根节点,在找该节点在中序序列中的位置,这样,左右子树有分开了。
这里的细节值得注意一下,不然很容易建树出错。(要减去inl,inl之前的已经成为别的子树的一部分了)

左树:make(prel+1,prel+1+pos-inl,inl,pos);

右树:make(prel+1+pos-inl,prer,pos+1,inr);

#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std; const int maxn = ; char pre[maxn],in[maxn],post[maxn];
int len; ///找根节点在中序中的位置
int find(int l,int r,char ch)
{
for(int i=l;i<r;i++)
if(in[i] == ch)
return i;
return -;
} ///当前树在先序序列中的左端点,右端点,
///中序中的左端点,右端点
void make(int prel,int prer,int inl,int inr)
{
if(prel>=prer)
return ;
if(prel==prer-)
{
printf("%c",pre[prel]);
return ;
} int pos = find(inl,inr,pre[prel]); make(prel+,prel+pos-inl+,inl,pos);
make(prel+pos-inl+,prer,pos+,inr);
printf("%c",pre[prel]);
} int main()
{
while(scanf("%s%s",pre,in)!=EOF)
{
len=strlen(pre);
make(,len,,len);
printf("\n");
}
return ;
}

最新文章

  1. (转)如何将本地git仓库上传到GitHub中托管+实践心得
  2. HDU 4857 逃生 (反向拓扑排序 &amp; 容器实现)
  3. C# WebApi 请求方式Post,返回Response
  4. Ecshop 单选按钮组功能 颜色多选
  5. IIS7 经典模式和集成模式的区别(转载)
  6. 算法实践——Twitter算法面试题(积水问题)的线性时间解法
  7. iOS开发——项目实战OC篇&amp;类QQ黏性按钮(封装)
  8. MySQL索引详解
  9. Resharper 8.0 的最实用的功能
  10. progressbar样式
  11. java的静态代理
  12. 基于visual Studio2013解决C语言竞赛题之0401阶乘
  13. 由于losf引起的pxc启动报错处理
  14. 201521123029《Java程序设计》第六周学习总结
  15. WebP 的前世今生
  16. Linux下修改Oracle数据库字符集命令
  17. 小程序组件中有bindinput监听报异常
  18. Linux环境变量和本地变量
  19. web项目与jsp有关的三个jar的依赖
  20. JavaScript学习总结(二、隐式类型转换、eval())

热门文章

  1. ZPL打印机公用代码
  2. Java 类型转换(int-&gt;String)
  3. HDFS配额查询
  4. spring mvc 自定义handler不拦截静态资源
  5. AsyncLocal 与 ThreadLocal ThreadStatic特性简介
  6. thinkPHP 模板操作
  7. 转 mysql front安装与使用教程 mysql 工具
  8. Checkstyle的配置详解
  9. 修改Matlab打开时的默认路径
  10. Unity3d 破解