【題解】ZeroJudge b148: NOIP2004 3.FBI树

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b148
【解題想法】二元搜索樹 (Bineary Search Tree, BST)

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 2048
int power, N;
string s;
char FBI[maxn];

void build_FBI(){
    memset(FBI, '\0', sizeof(FBI));
    // store the binary tree in an array
    for (int i=N; i<2*N; i++){
        if (s[i-N] == '1') FBI[i] = 'I';
        else FBI[i] = 'B';
    }
    int n = N;
    while (n >= 2){
        n /= 2;
        for (int i=n; i<2*n; i++){
            if (FBI[2*i] == FBI[2*i+1]) FBI[i] = FBI[2*i];
            else FBI[i] = 'F';
        }
    }
}

void post_order(int idx){
    //后序遍历:先后序遍历左子树,再后序遍历右子树,最后访问根。
    if ((int)log2(idx) > power) return;
    post_order(idx * 2);
    post_order(idx * 2 + 1);
    cout << FBI[idx];
}

int main() {
    while (cin >> power >> s){
        N = (int)s.length();
        build_FBI();
        post_order(1);
        cout << endl;
    }
    return 0;
}
分享本文 Share with friends