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

#include #include using namespace std;

struct Node{ char type; Node* left; Node* right; };

Node* buildTree(string s){ int n = s.length(); if(n == 1){ Node* node = new Node(); if(s[0] == '0'){ node->type = 'B'; }else{ node->type = 'I'; } node->left = nullptr; node->right = nullptr; return node; }

int mid = n/2;
string s1 = s.substr(0, mid);
string s2 = s.substr(mid, n-mid);

Node* node = new Node();
node->type = 'F';
node->left = buildTree(s1);
node->right = buildTree(s2);

return node;

}

void postOrderTraversal(Node* root){ if(root == nullptr){ return; }

postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->type;

}

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

Node* root = buildTree(s);
postOrderTraversal(root);

return 0;