二叉树遍历,先序序列+中序序列=后序序列,Poj(2255)
2024-08-29 18:54:18
这里我参考了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 ;
}
最新文章
- (转)如何将本地git仓库上传到GitHub中托管+实践心得
- HDU 4857 逃生 (反向拓扑排序 &; 容器实现)
- C# WebApi 请求方式Post,返回Response
- Ecshop 单选按钮组功能 颜色多选
- IIS7 经典模式和集成模式的区别(转载)
- 算法实践——Twitter算法面试题(积水问题)的线性时间解法
- iOS开发——项目实战OC篇&;类QQ黏性按钮(封装)
- MySQL索引详解
- Resharper 8.0 的最实用的功能
- progressbar样式
- java的静态代理
- 基于visual Studio2013解决C语言竞赛题之0401阶乘
- 由于losf引起的pxc启动报错处理
- 201521123029《Java程序设计》第六周学习总结
- WebP 的前世今生
- Linux下修改Oracle数据库字符集命令
- 小程序组件中有bindinput监听报异常
- Linux环境变量和本地变量
- web项目与jsp有关的三个jar的依赖
- JavaScript学习总结(二、隐式类型转换、eval())