满二叉树做法

结构体存左右节点，数组存所有节点和叶。

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<cctype>
using namespace std;
int n,s;
int a[1505];
int ch[1500];
struct node{
    int x,y;   
}q[1500];
void tree_last(int k){
    if(q[k].x != 0)tree_last(q[k].x);
    if(q[k].y != 0)tree_last(q[k].y);
    cout<<(char)ch[k];
}
int main(){
    cin>>n;
    s = pow(2,n);
    for(int i = 1;i <= pow(2,n); ++i){
        scanf("%1d",&a[i]);
        if(a[i] == 0) ch[s++] = (int) 'B';
        else ch[s++] = (int) 'I';
    }
    s = pow(2,n) * 2 - 1;
    for(int i = s;i >= 1; i -= 2){
        if(ch[i] == ch[i - 1]) ch[(i + (i - 1)) / 4] = ch[i];
        else ch[(i + (i - 1)) / 4] = (int) 'F';
    }
    s = pow(2,n) - 1;
    for(int i = 1;i <= s; ++i){
        q[i].x = (int) ch[i * 2];
        q[i].y = (int) ch[i * 2 + 1];
    }
    ch[0] = 0;
    //for(int i = 1;i <= 15;++i) cout<<q[i].x<<" "<<q[i].y<<endl;
    //cout<<q[9].x;
    tree_last(1);
    puts(" ");
    return 0;
}

样例输出

F