#include using namespace std; char s[1050]; /** #本题主要考查树的遍历方法 1.建树。按照题意是在递归过程中建立树,建树的方法实际上就是树的先序遍历(先根节点,再左右子树)。 当本节点长度大于1时递归建立子树。 2.输出。而输出过程是对树的后序遍历(先左右子树,再根节点),这里有个技巧就是可以和建树过程集成在一起。 只需将代码放在递归调用之后就可以了。 3.判断。最后是判断当前节点的FBI树类型,可以用B(初始值为1)保存全是‘0’的情况,如果遇到‘1’就将B置为0, 用I(初始值为1)保存全是‘1’的情况,如果遇到‘0’就将I置为0。最后判断B和I中的值,如果两个都为0则输出F (不全为‘0’,不全为‘1’)。 黄海感悟:这段代码简短,很好理解, (1)递归的思想 (2)左右边界的处理 (3) 后序的思路 (4)判断节点是什么的思路 */ //递归建树 void buildTree(int x, int y){ if(y>x){ buildTree(x, (x + y) / 2); //这个左孩子的边界判定有意思 buildTree((x + y + 1) / 2, y); //这个右孩子的边界判定有意思 } //不管x,y是不是一样,都执行下面的代码,应该是后序的意思 int B=1,I=1; //是不是全是1,或者全是0 for(int i=0;i<=y-x;i++){ if(s[x+i]=='1'){ B=0; }else if(s[x+i]=='0'){ I=0; } } //全是0,输出B if(B){ cout<<'B'; }else if(I){ //全是1,输出I cout<<'I'; }else{ //输出F,表示是混合的 cout<<'F'; } } int main() { int n; cin>>n>>s; buildTree(0, (1 << n) - 1); return 0; }