1365：FBI树(fbi)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 string s; //输入字符串 
 5 int id=1;//用于节点标记 
 6 struct node{
 7     char data;
 8     int lchild, rchild;
 9 };
10 node fbi[12000];
11 int sum(int l, int r){//计算区间[l, r]的和，以此判断是否相等 
12     int ret=0;
13     for(int i=l; i<=r; i++)
14         ret+=s[i]-‘0‘;
15     return ret;
16 }
17 void build(int root, int l, int r)//区间[l, r]的信息存放在root ， 自上往下建树 
18 {
19     if(l==r){//叶子节点判断 
20         if(s[l]==‘0‘)
21             fbi[root].data=‘B‘;
22         if(s[l]==‘1‘)
23             fbi[root].data=‘I‘;
24     }
25     else {//非叶子节点 
26         if(sum(l, r) == 0){//区间[l, r]全是0 
27             fbi[root].data=‘B‘;
28         }
29         else if(sum(l, r) == r-l+1){//区间[l, r]全是1 
30             fbi[root].data=‘I‘;
31         }
32         else{//区间[l, r]由0和1构成 
33             fbi[root].data=‘F‘;
34         }
35         int mid=(l+r)/2;//取中间位置 
36         fbi[root].lchild=++id;//左儿子指向新节点 
37         build(id, l, mid);//递归左儿子 
38         fbi[root].rchild=++id;//右儿子指向新节点
39         build(id, mid+1, r);//递归右儿子 
40     }
41 }
42 void hxprint(int root)
43 {
44     if(fbi[root].data==‘F‘ || fbi[root].data==‘B‘ || fbi[root].data==‘I‘){
45         hxprint(fbi[root].lchild);
46         hxprint(fbi[root].rchild);
47         cout<<fbi[root].data;
48     }
49 }
50 int main()
51 {
52     cin>>n;
53     cin>>s;
54     build(1, 0, (1<<n)-1);//建树 
55 //    for(int i=1; i<=16; i++)
56 //        cout<<i<<":"<<fbi[i].data<<" "<<fbi[i].lchild<<" "<<fbi[i].rchild<<endl;
57     hxprint(1);//后序输出 
58     cout<<endl;
59     return 0;
60  }