我使用了数组
FBI树是一颗完全二叉树 这是数组模拟的前提,因为需要明确下标
样例一的fbi树的最后一行为 i b b b i b i i 不难发现,这是与输入的数一一对应的 1 0 0 0 1 0 1 1
那么我们就可以直接确定fbi树的最后一行,然后倒着向上填即可
思路不难 上代码
#include<bits/stdc++.h> using namespace std; int n; string w;//输入的字符串 char a[100010];// 用于字符串转换 char a1[100010];//树的数组 char f(int x)//fbi树转换函数 { if(x=='1') return 'I'; if(x=='0') return 'B'; } void build(int q)//建立树 { if(q<1) return; if(q%2==0)//向一对左右子树的父亲结点填数 { if(a1[q]==a1[q+1])//相等则不变 a1[q/2]=a1[q]; if(a1[q]!=a1[q+1])//不相等则为f a1[q/2]='F'; build(q-1); } else { build(q-1); } } void ho(int b)//后序输出 { if(b>pow(2,n+1)-1) return; ho(2b); ho(2b+1); cout<<a1[b]; } int main() { cin>>n; cin>>w; //字符串转换成数组 for(int i=1;i<=w.length();i++) a[i]=w[i-1]; //先填输入的数 //x,y为开始指向两个数组最后一格的指针 int x=pow(2,n+1)-1; int y=pow(2,n); while(y>=1) { a1[x]=f(a[y]); y--; x--; } //根据输入的数 填整个树 build(pow(2,n+1)-1); ho(1);//后序输出 return 0; }
共 8 条回复
%%%%%%%%%
牛逼
%%% stO_pyx_Orz stO_pyx_Orz stO_pyx_Orz stO_pyx_Orz
膜拜大佬
资瓷
格式化了一下
%%%Orz
膜!!!