#include using namespace std; //递推思想,然后利用完全二叉树的性质 string s; char tree[65536]; int p; //输出模拟的树,后序 void outhx(int i) { //从上向下递归,注意下面不能越界! //左边 if (2 * i <= 2 * p - 1) outhx(2 * i);//2*p-1为节点总数 //右边 if (2 * i + 1 <= 2 * p - 1) outhx(2 * i + 1); //中间 cout << tree[i]; return; } int main() { int n; //n是树的层数 cin >> n; //小心使的万年船,吃掉回车 cin.get(); //输入字符串 cin >> s; p = 1 << n;//p=2的n次方,这比pow()香太多了!左移一位,就是增大2倍,n位就是2的n次方! //最后一行,注意这里的s是从0开始的 for (int i = 0; i < p; i++) { if (s[i] == '1') tree[i + p] = 'I'; //最底层的元素的位置偏移量,真是牛! else tree[i + p] = 'B'; } // 11011000 // IIBIIBBB //从倒数第二层推到第一层 for (int i = n; i >= 1; i--) { //对应的每一层的结点 for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) { //该节点的左孩子和右孩子是否相等 if (tree[2 * j] == tree[2 * j + 1]) { //孩子啥样,爸爸就啥样 tree[j] = tree[2 * j]; } else { //混搭! tree[j] = 'F'; } } } //从根开始输出后序遍历 outhx(1); cout << endl; //层序输出,tree是从1开始使用的,注意 // for (int i = 1; i <= 2 * p - 1; ++i) { // cout << tree[i]; // } return 0; }