洛谷:P1087 FBI树 P1030 求先序排列 P1305 新二叉树

时间:2022-04-25 09:38:00

洛谷:P1087 FBI树   P1030 求先序排列  P1305 新二叉树

至于为啥把这三个题放到一起,大概是因为洛谷的试炼场吧,三道树的水题,首先要理解

先序中序后序遍历方法。

fbi树由于数量小,在递归每个区间时,暴力跑一遍区间里的数,看看是否有0和1。至于递归的方法,二分递归就行。

新二叉树就是现根据题意建树,然后求先序遍历时看一下子节点不是‘*’不是才继续向下走

求先序遍历就是用地贵的方式实现,从后序遍历我们可以找出根节点,从中序遍历我们可以找到左右子树。

/*FBI树*/
#include
<cstdio>
#include
<cstring>
#include
<iostream>
#include
<algorithm>
#define maxn 56281
using namespace std;
int n;
char nam[maxn];
int qq[maxn];
void build(int l,int r)
{
int mid=(l+r)/2;
if(l!=r)
{
build(l,mid);
build(mid
+1,r);
}
int n0=0,n1=0;
for(int i=l;i<=r;i++)
{
if(qq[i]==1)n1++;
if(qq[i]==0)n0++;
if(n1&&n0)
{
printf(
"F");
return;
}
}
printf(n1
==0?"B":"I");
}
int main()
{
scanf(
"%d",&n);
scanf(
"%s",nam);
int len=strlen(nam);
for(int i=1;i<=len;i++)
{
qq[i]
=nam[i-1]-'0';
}
build(
1,len);
return 0;
}
/*新二叉树*/
#include
<cstdio>
#include
<iostream>
#include
<algorithm>
using namespace std;
struct root
{
char father;
char rc;
char lc;
root()
{
father
='?';
lc
='?';
rc
='?';
}
}tree[
2001];
void dfs(char x)
{
printf(
"%c",x);
if(tree[x].lc!='*')dfs(tree[x].lc);
if(tree[x].rc!='*')dfs(tree[x].rc);
}
int main()
{
int n;
scanf(
"%d",&n);
for(int i=1;i<=n;i++)
{
char a,b,c;
cin
>>a>>b>>c;
tree[a].lc
=b;
tree[a].rc
=c;
tree[b].father
=a;
tree[c].father
=a;
}
for(int i=1;i<=2000;i++)
{
if(tree[i].father=='?'&&tree[i].lc!='?'&&tree[i].rc!='?')
{
dfs(i);
break;
}
}
return 0;
}
/*求先序遍历*/
#include
<cstdio>
#include
<iostream>
#include
<string>
using namespace std;
string a,b;
void qla(int ln,int rn,int l,int r)
{
int place=a.find(b[r]);
cout
<<b[r];
if(place>ln)qla(ln,place-1,l,place-ln+l-1);//两棵子树
if(place<rn)qla(place+1,rn,place-ln+l,r-1);
}
int main()
{
cin
>>a>>b;
int len=a.size();
qla(
0,len-1,0,len-1);
return 0;
}
/*
BADC
BDCA
*/