题目
FBI Tree
|
||||||
| Description | ||||||
| FBI Tree的描述如下： 我们可以把由0和1组成的字符串分为3类，全0的串成为B串，全1的串成为I串，既含0又含1的串则称为F串。FBI树是一种二叉树，它的节点类型也包括F串节点、B串节点和I串节点三种。由一个长度为2^N的01串S可以构造出一颗FBI树T,递归的构造方法如下： （1） T的根节点为R，其类型与串S的类型相同。 （2） 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给出一个长度为2^N的01串，请用上述构造方法构造出一棵FBI树，并输出它的后续遍历序列。 |
||||||
| Input | ||||||
| 第一行为一个正整数T，表示测试数据组数。 每组测试数据第一行为一个整数N（0 <= N <= 10），第二行是一个长度为2^N的01串。 |
||||||
| Output | ||||||
| 输出FBI树的后续遍历序列。 |
||||||
| Sample Input | ||||||
| 2 1 10 3 10001011
|
||||||
| Sample Output | ||||||
| IBF IBFBBBFIBFIIIFF
|
||||||
| Source | ||||||
| 2016级新生程序设计全国邀请赛 |
总的来说，水题。递归（可以体现递归的真正含义）。已经说了是递归，这个题就是把字符串分成两段，左右两段都进入递归。因为题中的根节点要最后判断。所以左右节点递归的返回值进行比较，再输出根节点的字母。这是一棵树，中规中矩的用二叉可以解决，但代码量不少。个人更认可递归的方法
递归代码：
#include<iostream>
#include<cstdio>
using namespace std;
char s[1005];
char ans(int l,int r){ char x,y;int mid=(l+r)/2;if(l==r){if(s[l]=='0'){printf("B");return 'B';}else{printf("I");return 'I';}}else{x=ans(l,mid);y=ans(mid+1,r);if(x==y){if(x=='B'){printf("B");return 'B';}else if(x=='I'){printf("I");return 'I';}else if(x=='F'){printf("F");return 'F';}}else{printf("F");return 'F';}}
}
int main(){int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);n=1<<n;getchar();gets(s);ans(0,n-1);cout<<endl;}return 0;
}
/***官方标程***/
/*利用指针建立二叉树，再进行后续遍历。
直接构造一棵二叉树即可，可以用最后一层节点来保存2^N个值，
则他们的父亲结点的字符值就已经由左右儿子的B,I决定了，故不用保存串，只需要记录字符值。
*/#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
char s1[2]="0",s2[2]="1";
char s[1200];
struct FBI
{
char s;
FBI *lchild,*rchild;
};
void showtree(FBI *head)//后序遍历树
{
if(head==NULL) return;
showtree(head->lchild);
showtree(head->rchild);
printf("%c",head->s);
}
void maketree(FBI *node,char *p,int len)
{
if(len==1)
{
if(strstr(p,s1)&&strstr(p,s2)) node->s='F';
else if(strstr(p,s1)&&!strstr(p,s2)) node->s='B';
else if(!strstr(p,s1)&&strstr(p,s2)) node->s='I';
node->lchild=NULL;
node->rchild=NULL;
return;
}
char q[520],*r=new char;
FBI *z=new FBI;
strncpy(q,p,len/2);
r=p;
int i=len/2;
while(i--) r++; //将p一分为二 q和r两个字符串
if(strstr(q,s1)&&strstr(q,s2)) //判断左儿子的类型
z->s='F';
else if(strstr(q,s1)&&!strstr(q,s2)) z->s='B';
else if(!strstr(q,s1)&&strstr(q,s2)) z->s='I';
node->lchild=z;
FBI *c=new FBI;
if(strstr(r,s1)&&strstr(r,s2)) //判断右儿子的类型
c->s='F';
else if(strstr(r,s1)&&!strstr(r,s2)) c->s='B';
else if(!strstr(r,s1)&&strstr(r,s2)) c->s='I';
node->rchild=c;
maketree(z,q,len/2); //递归构建
maketree(c,r,len/2);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
scanf("%s",&s);
if(strlen(s)==1)
{
if(!strcmp(s,"0")) printf("B\n");
else if(!strcmp(s,"1")) printf("I\n");
continue;
}
FBI *head=new FBI;
char s1[2]="0",s2[2]="1";
if(strstr(s,s1)&&strstr(s,s2)) head->s='F';
else if(strstr(s,s1)&&!strstr(s,s2)) head->s='B';
else if(!strstr(s,s1)&&strstr(s,s2)) head->s='I';
maketree(head,s,(int)pow(2.0,(double)n));
showtree(head);
printf("\n");
}
return 0;
}
革命尚未成功！