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 ;
}

最新文章

  1. Highcharts——让你的网页上图表画的飞起
  2. Html 开发工具 之Hbulider
  3. SQL Server 2008安装过程中的一些问题和心得
  4. Core Data数据操作
  5. win8或win8.1修改注册表失败的原因
  6. HTMLEncode httpencode UTF8Encode
  7. jQuery开发技术笔记
  8. Hadoop MultipleOutputs 结果输出到多个文件夹 出现数据不全,部分文件为空
  9. Longest Substring Without Repeating Characters - 哈希与双指针
  10. 页面loading提示效果
  11. Angularjs通过$http与服务器通信
  12. java面向对象(四)之重写、重载
  13. Oracle集合操作
  14. 【安卓开发】Android系统中Parcelable和Serializable的区别
  15. Java自学总结--简介
  16. POJ.2750.Potted Flower(线段树 最大环状子段和)
  17. Oracle特殊字符转义:&amp;amp;和&amp;#39;
  18. CS229 4.Logistic Regression
  19. testlogin
  20. Spring MVC 异常处理 - DefaultHandlerExceptionResolver

热门文章

  1. B2C
  2. log4j_自定义样式参数意义
  3. YTU 2958: 代码填充--雨昕学画画
  4. C# mouse keyboard monitor
  5. BZOJ_2819_Nim_树状数组维护出栈入栈序
  6. python requests 调用restful api
  7. angularJs 之deferred
  8. 【性能测试】服务器资源监测工具sar安装
  9. Ubuntu安装配置vsftpd
  10. ROS学习笔记十一:创建URDF 文件并在RVIZ中查看模型