【NOIP2004普及组题三】FBI树【树的遍历】描述我们可以把由0和1组成的字符串分为三类：全0串称为B串全1串称为I串既含0又含1的串则称为F串。FBI树是一种二叉树1它的结点类型也包括F结点B结点和I结点三种。由一个长度为2N的01串S可以构造出一棵FBI树T递归的构造方法如下：1 T的根结点为R其类型与串S的类型相同；2 若串S的长度大于1将串S从中间分开分为等长的左右子串S1和S2；由左

#include <iostream>
#include <string>

using namespace std;

// 递归构造FBI树
string constructFBITree(string s) {
    // 如果字符串长度为1，则直接返回对应的结点类型
    if (s.length() == 1) {
        if (s == "0") {
            return "B";
        } else {
            return "I";
        }
    }

    // 分割字符串
    int mid = s.length() / 2;
    string leftStr = s.substr(0, mid);
    string rightStr = s.substr(mid);

    // 构造左右子树
    string leftTree = constructFBITree(leftStr);
    string rightTree = constructFBITree(rightStr);

    // 根据左右子树的类型确定根结点的类型
    if (leftTree == rightTree) {
        return leftTree;
    } else {
        return "F";
    }
}

// 后序遍历FBI树
void postOrderTraversal(string tree, string& result) {
    if (tree.length() == 1) {
        result += tree;
        return;
    }

    int mid = tree.length() / 2;
    string leftTree = tree.substr(0, mid);
    string rightTree = tree.substr(mid);

    postOrderTraversal(leftTree, result);
    postOrderTraversal(rightTree, result);
    result += tree;
}

int main() {
    int N;
    string s;
    cin >> N >> s;

    string tree = constructFBITree(s);
    string result = "";
    postOrderTraversal(tree, result);

    cout << result << endl;

    return 0;
}
``