HDU_1710_二叉树前序中序确定后序
2024-08-30 19:35:18
2018-3-6
按照王道机试书上的思路再做了一遍,先根据先序和中序建树,然后后序遍历。
静态分配数组用于建树,可以返回数组地址当作结点指针。
#include<iostream>
#include<cstdio>
using namespace std; int pre[],in[],n; struct Node
{
Node *lson,*rson;
int num;
}node[]; //静态分配一个数组用于建树 int cntn; Node *create(int num)
{
node[cntn].lson=node[cntn].rson=NULL;
node[cntn].num=num;
return &node[cntn++]; //返回数组元素的地址
} Node *build(int ph,int ih,int len)
{
Node *now=create(pre[ph]);
int i;
for(i=;pre[ph]!=in[i];i++);
if(i!=ih)
now->lson=build(ph+,ih,i-ih);
if(i!=ih+len-)
now->rson=build(ph+i-ih+,i+,len-(i-ih)-);
return now;
} int cnt;
void postOrder(Node *rt)
{
if(rt==NULL)
return;
postOrder(rt->lson);
postOrder(rt->rson);
printf("%d",rt->num);
if(++cnt==n)
printf("\n");
else
printf(" ");
} int main()
{
while(scanf("%d",&n)!=EOF)
{
cntn=cnt=;
for(int i=; i<=n; i++)
scanf("%d",&pre[i]);
for(int i=; i<=n; i++)
scanf("%d",&in[i]);
Node *rt=build(,,n);
postOrder(rt);
}
return ;
}
2018-3-3
又做了一遍,这次是自己根据思想自己码了一遍
看了上次的代码,感觉还是上次的好一点
#include<iostream>
#include<cstdio>
using namespace std; int pre[],in[],cnt,n; void getPost(int pl,int pr,int il,int ir)
{
if(pr<pl||ir<il)
return;
int loc;
for(int i=il; i<=ir; i++)
if(in[i]==pre[pl])
{
loc=i;
break;
}
if(<loc-il)
getPost(pl+,pl+loc-il,il,loc-);
if(<ir-loc)
getPost(pr-(ir-loc)+,pr,loc+,ir);
printf("%d",pre[pl]);
cnt++;
if(cnt==n)
printf("\n");
else
printf(" "); }
int main()
{
while(scanf("%d",&n)!=EOF)
{
cnt=;
for(int i=; i<=n; i++)
scanf("%d",&pre[i]);
for(int i=; i<=n; i++)
scanf("%d",&in[i]);
getPost(,n,,n);
}
return ;
}
2018-1-3
研究生考试初试结束一个周了,开始准备复试了,又要开始刷题了。
给定一个二叉树前序和中序,确定后序。
#include<iostream>
#include<cstdio>
using namespace std; int pre[],in[]; void getPostOrder(int ph,int ih,int len,int flag)
{
if(len<)
return;
int i;
for(i=; pre[ph]!=in[ih+i]; i++); //在中序中找到根节点
getPostOrder(ph+,ih,i,); //处理左子树
getPostOrder(ph+i+,ih+i+,len-i-,); //处理右子树
if(flag)
printf("%d\n",pre[ph]);
else
printf("%d ",pre[ph]);
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<n; i++)
scanf("%d",&pre[i]);
for(int i=; i<n; i++)
scanf("%d",&in[i]);
//cout<<"*"<<endl;
getPostOrder(,,n,);
}
return ;
}
最新文章
- Highcharts——让你的网页上图表画的飞起
- Html 开发工具 之Hbulider
- SQL Server 2008安装过程中的一些问题和心得
- Core Data数据操作
- win8或win8.1修改注册表失败的原因
- HTMLEncode httpencode UTF8Encode
- jQuery开发技术笔记
- Hadoop MultipleOutputs 结果输出到多个文件夹 出现数据不全,部分文件为空
- Longest Substring Without Repeating Characters - 哈希与双指针
- 页面loading提示效果
- Angularjs通过$http与服务器通信
- java面向对象(四)之重写、重载
- Oracle集合操作
- 【安卓开发】Android系统中Parcelable和Serializable的区别
- Java自学总结--简介
- POJ.2750.Potted Flower(线段树 最大环状子段和)
- Oracle特殊字符转义:&;amp;和&;#39;
- CS229 4.Logistic Regression
- testlogin
- Spring MVC 异常处理 - DefaultHandlerExceptionResolver