799
WIKIOI-1094 FBI树(未完成)
1094 FBI树
题目描述 Description
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树[1]，它的结点类型也包括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树，并输出它的后序遍历[2]序列。
输入描述 Input Description
输入的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2^N的“01”串。
输出描述 Output Description
输出t包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
样例输入 Sample Input
3
10001011
样例输出 Sample Output
IBFBBBFIBFIIIFF
数据范围及提示 Data Size & Hint
对于40%的数据，N <= 2；
对于全部的数据，N <= 10。
不知道为什么WA，所有数据都能通过.....有空回来继续解决
思路是对的
#include<stdio.h>
#include<string.h>
#include<math.h>
char a[3000];
struct node
{
char flag;
int L;
int R;
}b[10000];
int n,m,k,x=0;
char Sure(int x,int m)//确定子串类型
{
//printf("@1\n");
int i,f1=0,f2=0;
if(x==m)
{
if(a[x]=='1')
return 'I';
else
return 'B';
}
else
{
for(i=x;i<=m;i++)
{
if(a[i]=='0') f1=1;
else
if(a[i]=='1') f2=1;
}
if(f1==1&&f2==1)
return 'F';
else if(f1==0&&f2==1)
return 'I';
else
return 'B';
}
}
void BuildTree(int k,int x,int m)//建立二叉树
{
//printf("@2 x=%d m=%d\n",x,m);
b[k].flag=Sure(x,m);
if(m==x)
return;
else
{
b[k].L=2*k;
BuildTree(2*k,x,(m+x)/2);
b[k].R=2*k+1;
BuildTree(2*k+1,(m+x)/2+1,m);
}
}
void Ergodic(int u)//后续遍历二叉树
{
//printf("@3\n");
if(b[u].L!=0)
Ergodic(b[u].L);
if(b[u].R!=0)
Ergodic(b[u].R);
printf("%c",b[u].flag);
}
int main()
{
int i,v1=0,v2=0;
scanf("%d",&n);
memset(b,0,sizeof(b));//清零
m=(int)pow(2,n);
getchar();
for(i=1;i<=m;i++)
scanf("%c",&a[i]);
k=1;
BuildTree(k,1,m);
Ergodic(1);
printf("\n");
return 0;
}
最后更新：2017-04-03 12:56:00