需求：数串由2^n个'0' '1'数串组成，对于一个数串，有01混合出现，则视为F，全0数串为B，全1数串为I。
将给定数串进行切割，如10010011可以用二叉树表示为
F(10010011)
/ \
F (1001) F(0011)
/ \ / \
F(10) F(01) B(00) I(11)
/ \ / \ / \ / \
I(1)B(0) B(0) I(1) B(0)B(0) I(1)I(1)
思路：由上述可以看出，FBI树是一棵满二叉树，可以使用逆向建树方法，以逐层建树的方法，先建立叶子节点层，然后生成其上层节点，如此类推，可以快速得到二叉树。
而且我们可以看到孩子的值与双亲的值的关系如下：
左/右孩子值 左/右孩子值 双亲值
F + F = F
F + B = F
F + I = F
I + B = F
B + B = B
I + I = I
由此确定双亲的值。
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> struct tree_node;
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
char key;
};
typedef struct tree_node treenode; void create_fbitree(treenode **T, char *num){
int numlen, k;
int levelcnt;
treenode *nodetemp, *levelnode, *levelnodekids; numlen = strlen(num);
levelcnt = numlen;
levelnode = (treenode*)malloc(sizeof(treenode)*levelcnt);
for(k=0; k<levelcnt; k++){
(levelnode+k)->lc = NULL;
(levelnode+k)->rc = NULL;
if(num[k]=='1')
(levelnode+k)->key = 'I';
else
(levelnode+k)->key = 'B';
}
levelcnt = levelcnt/2;
levelnodekids = levelnode; while(levelcnt){
levelnode = (treenode*)malloc(sizeof(treenode)*levelcnt);
for(k=0; k<levelcnt; k++){
(levelnode+k)->lc = levelnodekids+k*2;
(levelnode+k)->rc = levelnodekids+k*2+1;
if((levelnodekids+k*2)->key=='B'&&(levelnodekids+k*2+1)->key=='B')
(levelnode+k)->key = 'B';
else if((levelnodekids+k*2)->key=='I'&&(levelnodekids+k*2+1)->key=='I')
(levelnode+k)->key = 'I';
else
(levelnode+k)->key = 'F';
}
levelcnt = levelcnt/2;
levelnodekids = levelnode;
}
*T = levelnode;
} void pre_visit_tree(treenode *T){
if(T!=NULL){
printf("%c ", T->key);
pre_visit_tree(T->lc);
pre_visit_tree(T->rc);
}
else{
return;
}
} int main(void){
treenode *T;
char num[1000]; if(gets(num)==NULL)
return 0;
create_fbitree(&T, num);
pre_visit_tree(T); system("pause");
return 0;
}