#include using namespace std; //说白了,一切递归都是通过这个字符串进行构建树的,只不过在一直玩子串 string s; // 还需要反复思考,体会其中的意思 // 本题目录入错误,不是2N,应该是2^N /** * 功能:递归构建的核心函数 * @param x 从第几个开始 * @param y 到第几个结束 */ void BuildTree(int x, int y) { //cout << "x=" << x << ",y=" << y << endl; //如果一样,代表是叶子节点,就是同一个位置,这个是递归的终点,也可以理解为出口 if (x == y) { if (s[x] == '0') cout << "B"; else cout << "I"; } else { //进入这里,代表子串还够长,需要继续递归下去~ // 找到字符串的中点,注意这里面二分法的起止点选择办法 // x是从0开始的,y是长度-1 // 数字:1 2 3 4 5 6 7 8 // 索引:0 1 2 3 4 5 6 7 // 上面的序列是偶数个,那么 (y-x-1)/2= (7-0-1)/2=3,即索引为3的是一半的位置,0-3,4-7,这是真正的一家一半 int mid = (y - x - 1) / 2; //构建前一半 BuildTree(x, x + mid); // 0+3=3,0--->3 就是 0,1,2,3,正好是4个。 //构建后一半 BuildTree(x + mid + 1, y); // 7-3=4,4--->7 就是 4,5,6,7,也是正好4个。 // 如果是奇数个数字的序列 // 数字: 1 2 3 4 5 6 7 8 9 // 索引: 0 1 2 3 4 5 6 7 8 // 那么 (y-x-1)/2= (8-0-1)/2=3,即索引为3的是一半的位置,0-3,4-8 // x---> x+mid 0--->3 // x+mid+1---->y 0+3+1--->8 4--->8 // 后序遍历开始,其实是要输出了,那么需要怎么输出呢?这取决于它的左右孩子是不是省心! // 啥样是省心呢?1孩子数和0孩子数一样就是省心,否则就是不省心。 // 那怎么才能知道左边的孩子数和右边的孩子数呢?这个也不掌握啊~,这需要从原始的、已有的信息中获取了,在递归中无法知道,原始已有的信息是那个字符串s~~~ //中间节点最后输出,也就意味着是后序输出 int cnt0 = 0, cnt1 = 0; //cnt0:0的个数 cnt1:1的个数, //计算这段子串中有几个0,几个1 for (int i = x; i <= y; ++i) { if (s[i] == '0') cnt0++; else cnt1++; } //全是1,那么输出I if (cnt0 == 0) cout << "I"; else if (cnt1 == 0) //如果全是0,那么输出B cout << "B"; else //都有的话,输出F cout << "F"; } } int main() { int n; //这个n是个废物 //读入多组数据,以0为截止符 cin >> n >> s; //调用递归函数进行构建,x->y代表字符串的起止位置,因为用到了折半递归,一般的思路是写一个递归函数,将开始和结束的索引号传入,在递归中折半进行。 BuildTree(0, s.size() - 1); return 0; }