P1087 FBI树

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1087


题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“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树，并输出它的后序遍历序列。

输入输出格式
输入格式：
第一行是一个整数N(0≤N≤10)，

第二行是一个长度为2^N的“01”串。

输出格式：
一个字符串，即FBI树的后序遍历序列。

输入输出样例
输入样例#1：
3
10001011
输出样例#1：
IBFBBBFIBFIIIFF
说明
对于40%的数据，N≤2；

对于全部的数据，N≤10。

noip2004普及组第3题

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. string s1;
   
4. int pi;
   
5. struct tree
   
6. {
   
7.     string s;
   
8.     char k;
   
9.     tree *left,*right;
   
10. }*h;
    
11. bool flag0,flag1;
    
12. char j(string x)
    
13. {
    
14.     flag0=0;flag1=0;
    
15.     for(int i=0;i<x.size();i++)
    
16.     {
    
17.         if(x[i]=='0')flag0=1;
    
18.         if(x[i]=='1') flag1=1;
    
19.     }
    
20.     if(flag1)
    
21.     {
    
22.         if(flag0)return 'F';
    
23.         else return 'I';
    
24.     }
    
25.     else return 'B';
    
26. }
    
27. void bt(tree *&q,string x)
    
28. {
    
29.     if(x.size()<=1)return;
    
30.     string x1,x2;
    
31.     int n=x.size()/2;
    
32.     for(int i=0;i<=n-1;i++)
    
33.     {
    
34.         x1+=x[i];
    
35.         x2+=x[i+n];
    
36.     }
    
37.     tree *ls,*rs;
    
38.     ls=new tree;
    
39.     rs=new tree;
    
40.     ls->left=NULL;
    
41.     ls->right=NULL;
    
42.     rs->left=NULL;
    
43.     rs->right=NULL;
    
44.     q->left=ls;
    
45.     q->right=rs;
    
46.     ls->s=x1;
    
47.     rs->s=x2;
    
48.     ls->k=j(x1);
    
49.     rs->k=j(x2);
    
50.     bt(ls,x1);
    
51.     bt(rs,x2);
    
52. }
    
53. void hx(tree *x)
    
54. {
    
55.     if(x!=NULL)
    
56.     {
    
57.         hx(x->left);
    
58.         hx(x->right);
    
59.         cout<<x->k;
    
60.     }
    
61. }
    
62. int main()
    
63. {
    
64.     cin>>pi;
    
65.     cin>>s1;
    
66.     h=new tree;
    
67.     h->s=s1;
    
68.     h->k=j(s1);
    
69.     bt(h,s1);
    
70.     hx(h);
    
71.     return 0;
    
72. }
    

复制代码

黄煦喆

1. #include<iostream>//10001011
   
2. using namespace std;
   
3. int n;
   
4. string s;
   
5. char kk(string m)
   
6. {
   
7.     if(m.find('0')==string::npos)return 'I';
   
8.     else if(m.find('1')==string::npos)return 'B';
   
9.     else return 'F';
   
10. }
    
11. void ms(string x)
    
12. {
    
13.     if(x.size()>0)
    
14.     {
    
15.         int l=x.size()/2;
    
16.         ms(x.substr(0,l));
    
17.         ms(x.substr(l,l));
    
18.         cout<<kk(x);
    
19.     }
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>n>>s;
    
24.     ms(s);
    
25.     return 0;
    
26. }
    

复制代码