SDNUOJ——1168.FBI树

Description 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

T的根结点为R，其类型与串S的类型相同；若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。 Input 输入的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2^N的“01”串。 Output 输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 Sample Input

3 10001011

Sample Output

IBFBBBFIBFIIIFF

思路:递归创建完全二叉树。。。

直到现在我都不明白的是，为什么malloc之后还要自己赋值成NULL，难道不是默认分配的空间为空嘛？!我调式了一晚上，，，，突发奇想加个NULL，绿了。。。wc。。

//#include<bits/stdc++.h> #include <stdio.h> #include <iostream> #include<algorithm> //#include <map> //#include <set> //#include <vector> //#include <queue> //#include <stack> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <math.h> using namespace std; typedef long long ll; #define MAXN 10005 #define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll #define MALL (endtree *)malloc(sizeof(endtree)); char cc[MAXN/2]; typedef struct endtree { char sh; struct endtree *lc, *rc; }*Node; void creat(int f, int e, Node tree) { if(e == f) { if(cc[e] == '1') tree->sh = 'I'; else tree->sh = 'B'; return; } bool x=false, y=false; for(int i=f; i<=e; ++i) { if(cc[i] == '1' && !x) x = true; if(cc[i] == '0' && !y) y = true; if(x && y) break; } if(x && !y) tree->sh = 'I'; else if(y && !x) tree->sh = 'B'; else tree->sh = 'F'; int k = (f+e)/2; tree->lc = MALL; //不明白为什么要手动置空。。 tree->lc->lc = NULL; tree->lc->rc = NULL; tree->rc = MALL; tree->rc->lc = NULL; tree->rc->rc = NULL; creat(f, k, tree->lc); creat(k+1, e, tree->rc); return ; } void print(Node head) { if(head == NULL) return; print(head->lc); print(head->rc); cout << head->sh; } int main() { int n; cin >> n; scanf("%s", cc); Node head; head = MALL; head->lc = NULL; head->rc = NULL; int len = strlen(cc); creat(0, len-1, head); print(head); cout << '\n'; return 0; }

别急，下面还有一份代码（根据上一份代码想到的。。。）：

思路：也是递归构造二叉树，但是不同的是返回了结构体类型，，，由于最后数组被割分成了单独的一个，所以递归结束条件就不再是e == f，而要另外假设一个递归结束条件。

//#include<bits/stdc++.h> #include <stdio.h> #include <iostream> #include<algorithm> //#include <map> //#include <set> //#include <vector> //#include <queue> //#include <stack> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <math.h> using namespace std; typedef long long ll; #define MAXN 10005 #define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll #define MALL (endtree *)malloc(sizeof(endtree)); char cc[MAXN/2]; typedef struct endtree { char sh; struct endtree *lc, *rc; }*Node; Node creat(int f, int e) { if(e == INF)//这才是递归结束的条件，回扣上一层 return 0; if(e == f) { e=INF;//此时到了二叉树的最底层，但是递归还不能结束，因为还要构建最底层的叶子结点，所以给e加了特殊条件 Node head; head = MALL; if(cc[f] == '1') head->sh = 'I'; else head->sh = 'B'; head->lc = creat(f, e); //为了引出递归结束的条件 head->rc = creat(f, e); return head; } Node head; head = MALL; bool x=false, y=false; for(int i=f; i<=e; ++i) { if(cc[i] == '1' && !x) x = true; if(cc[i] == '0' && !y) y = true; if(x && y) break; } if(x && !y) head->sh = 'I'; else if(y && !x) head->sh = 'B'; else head->sh = 'F'; int k = (f+e)/2; head->lc = creat(f, k); head->rc = creat(k+1, e); return head; } void print(Node head) { if(head == NULL) return; print(head->lc); print(head->rc); cout << head->sh; } int main() { int n; cin >> n; scanf("%s", cc); Node head; head = MALL; int len = strlen(cc); head = creat(0, len-1); print(head); cout << '\n'; return 0; }

最后，灵感，总是在你东风无力时，不期而至。。。。枯了~~~